Proof Consider overshooting \(t\) by \(2^{n}-1\), where \(n\) is the smallest integer that overshoots the target. We would like to prove considering a jump \(2^{n+1}-1\) is not going to yield a shorter set of actions. Note that \(t\) is in \([2^{n-1},2^n-2]\), so from point A we have a remaining distance in \([2^n+1, 3(2^n)-1]\). Again if we consider the possible jumps from A, either we jump to \(2^{n}-1\) or \(2^{n+1}-1\). Of course we will not take \(2^{n+1}-1\) because that would mean we arrive back at the beginning.

It is easy see that if you start in a spot in the diagonal, you can get back to the diagonal in two moves. Say E-NE followed by N-NE, where I am using the the North, South, East and West conventions. Similarly for a knight at the x-axis you can get back to the x-axis with E-NE followed by E-SE. Let’s take a look at the diagonal section of 4,4,4 (pink), since I can get back to the diagonal in two moves, the next section has 6,6,6 (beige).

Analysis of lee215’s solution Lee already explained fairly well how to get the 1D dp. I just want to expound a little bit because there is a heavy dose of intuition that I believe is very beneficial for other problems. Intuition One of the first things that one tries when playing with this problem is figuring out when the second finger comes into the picture. I applaud the earlier posts in assuming a special starting position for both fingers, so that there is nothing special about when it transitions from one finger to two fingers.

Requirements O(1) insertion requires O(1) getting the least frequently used Suggested data structures f: a map from frequency to a tuple containing the head and tail of a portion of a double linked list kv: a map from key to a node in the double linked list dll: a double linked list where the least frequent item is at the head of the list node: element of dll, containing frequency info, as well a prev, next, value, the usual stuff put(a,v) find corresponding node via kv[a] delete head of double linked list and update f accordingly delete node from its current position and insert it at the head of the next frequency, i.

Acknowledgement Taken from fun4leet’s My Calendar II wonderful article tl;dr A max segment tree, with an incremental update function is sufficient for this problem. Max is used because such tree allows quick query of the max number of bookings given a range. Incremental update is useful because each time book is called, one needs to increment the bookings in a particular range. Data structure 4 things: a range \([l,r]\), data, lazy flag

Notes on solution to Leetcode 920 Let’s take the example from the article, songs: \(\left\{abcde\right\}\), playlist: \(abacabdcbaeacbd\), \(\bar{x} = (1,2,4,7,11)\) For \(\bar{x}\), each number in the n-tuple indicates a position in the playlist for the first occurrence of a particular unique song. The article uses 1-indexing so I will use the same to be consistent. As an example for the \(\bar{x}\) above, consider the playlist family: \(p_l = (1_1,2_2,c_3,3_4,c_5,c_6,4_7,c_8,c_9,c_{10},5_{11},c_{12},c_{13},c_{14})\) Here I have used the numbers (characters) \(1-5\), to indicate a song number, instead of the \(a-e\) in the article.