Imagine you have a special keyboard with the following keys:
Key 1: (A): Print one 'A' on screen.
Key 2: (Ctrl-A): Select the whole screen.
Key 3: (Ctrl-C): Copy selection to buffer.
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
Example 1:
Input: N = 3 Output: 3 Explanation: We can at most get 3 A's on screen by pressing following key sequence: A, A, A
Example 2:
Input: N = 7 Output: 9 Explanation: We can at most get 9 A's on screen by pressing following key sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Note:
Explanation
\nWe either press \'A\', or press \'CTRL+A\', \'CTRL+C\', and some number of \'CTRL+V\'s. Thus, there are only two types of moves:
\n1): Add 1k+1): Multiply by k, where k >= 2.In the following explanations, we will reference these as moves.
\nIntuition and Algorithm
\nSay best[k] is the most number of \'A\'\'s possible after k moves. If the last move was adding, then best[k] = best[k-1] + 1. If the last move was multiplying, then best[k-(x+1)] = best[k-(x+1)] * x for some x < k-1.
Taking the best of these candidates lets us find best[k] in terms of previous best[j], j < k.
Complexity Analysis
\nTime Complexity: . We have two nested for-loops, each of which do work.
\nSpace Complexity: , the size of best.
Intuition
\nIf we multiply by 2N, paying a cost of 2N+1, we could instead multiply by N then 2, paying N+4. When N >= 3, we don\'t pay more by doing it the second way.
Similarly, if we are to multiply by 2N+1 paying 2N+2, we could instead multiply by N+1 then 2, paying N+5. Again, when N >= 3, we don\'t pay more doing it the second way.
Thus, we never multiply by more than 5.
Algorithm
\nOur approach is the same as Approach #1, except we do not consider k-x-1 > 5 in our inner loop. For brevity, we have omitted this solution.
Complexity Analysis
\nTime Complexity: . We have two nested for-loops, but the inner loop does work.
\nSpace Complexity: , the size of best.
Explanation
\nAs in Approach #2, we never multiply by more than 5.
\nWhen N is arbitrarily large, the long run behavior of multiplying by k repeatedly is to get to the value . Analyzing the function at values , it attains a peak at . Thus, we should expect that eventually, best[K] = best[K-5] * 4.
Now, we need to make a few more deductions.
\nWe never add after multiplying: if we add c after multiplying by k, we should instead multiply by k+c.
We never add after 5: If we add 1 then multiply by k to get to (x+1) * k = xk + k, we could instead multiply by k+1 to get to xk + x. Since k <= 5, we must have x <= 5 for our additions to not be dominated.
The number of multiplications by 2, 3, or 5 is bounded.
\nEvery time we\'ve multiplied by 2 two times, we prefer to multiply by 4 once for less cost. (4^1 for a cost of 5, vs 2^2 for a cost of 6.)
\nTogether, this shows there are at most 5 additions and 9 multiplications by a number that isn\'t 4.
\nWe can find the first 14 operations on 1 by hand: 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81. After that, every subsequent number is achieved by multiplying by 4: ie., best[K] = best[K-5] * 4.
Complexity Analysis
\nAnalysis written by: @awice.
\n