CTRL+A, CTRL+C, CTRL+V

Problem

Imagine you have a special keyboard with the following keys:

    A
    Ctrl+A
    Ctrl+C
    Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.

If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.

That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of A's that you can produce).

Solution

One common strategy in problem solving is to always begin with small examples.
It is trivial to notice that for N <= 6, M = N. But how about the case where N = 7?

Here is where the most common pitfall that most people would fall into (myself included).

Most people reason that for N = 7, the answer is M = 8, because the sequence S = { A, A, A, A, CTRL+A, CTRL+C, CTRL+V } produces a total of 8 A’s.
Wait, the copied text is still in the buffer after a paste operation. We could have applied CTRL+V twice to double the previous text, sweet!
How about S = { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V } which produces a total of 9 A’s?
Unfortunately, both of the above answers are incorrect, as the correct answer for N = 7 is M = 7. This is simply because the sequence of { CTRL+A, CTRL+C, CTRL+V } does not double the previous text. Why? Take a moment to let this to sink into your brain.
Answers for N up to 7 is easy, which is M = N. But how about N = 8?
For N = 8 the answer is M = 9, where S = { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V }.
For N = 9 the answer is M = 12, where S = { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V, CTRL+V }.
Now lets following notation:

• Define 4A as a sequence of { A, A, A, A }. Therefore, 5A would then mean { A, A, A, A, A }.
• Define 2D as a sequence of CTRL+A, CTRL+C, CTRL+V, CTRL+V, which simply means double the previous text. Note that 3D does not double the previous text, it actually triples the previous text.

With this notation in place, it is much easier to work with this problem. Using the above notation, we rewrite our answer for N = 8 and N = 9.
N = 8, S = { 3A3D }, M = 9.
N = 9, S = { 3A4D }, M = 12.
The value of M could be obtained simply by multiplying the numbers, isn’t that neat?
Working our way up:
N = 10, S = { 4A4D }, M = 16.
N = 11, S = { 5A4D }, M = 20.
As you can see, the pattern here is pretty obvious, let’s summarize as follow:

• The solution so far for N > 7 is to find integers a and b such that ab yields the largest product, subjected to the condition where a+b = N-2.
• Both a and b are easy to find, as the largest product is found when the difference of a and b is less than or equal to one.

Similarly,
N = 12, S = { 5A5D }, M = 25.
N = 13, S = { 5A6D }, M = 30.
N = 14, S = { 6A6D }, M = 36.
Be extra cautious for N = 15.

When N = 15, does the sequence { 6A7D } yields the maximum where M = 42?
Imagine if you have a very large number of keystrokes to enter, does pressing CTRL+V forever gives you the maximum sequence? Remember, you can redo the entire { CTRL+A, CTRL+C, CTRL+V } operations again and potentially maximizes the sequence.
For N = 15, the maximum sequence should be:
{ 3A4D4D }, which yields M = 48.
Similarly,
N = 16, S = { 4A4D4D }, M = 64.
…
N = 21, S = { 3A4D4D4D }, M = 192.
…
N = 25, S = { 4A5D5D5D }, M = 500.
N = 26, S = { 5A5D5D5D }, M = 625.
N = 27, S = { 3A4D4D4D4D }, M = 768.
Let’s generalize the above:

M = MAX (a₁ . a₂ … a_k),where
a₁ + a₂ + … + a_k = n – 2(k-1)

To obtain M = MAX (a₁ . a₂ … a_k),
it is necessary that the below condition must be met:

∀ i, j ∈{ 1, 2, … , k } : MAX ( | a_i – a_j | ) = 1.

To obtain M, we can first divide a₁ + a₂ + … + a_k by k to obtain the average as a reference, and the rest should be straightforward.
Now the final problem lies in how to obtain the value of k efficiently. I am pretty sure this could be solved easily using Number Theory, but so far, my best solution is to use a brute force method to obtain k.

Here is a solution using DP

public static int maxChar(int n) {
    int[] dp = new int[n];
    for (int i = 0; i < n; ++i) {
  dp[i] = i + 1; // type A
    }
    for (int i = 0; i < n; ++i) {
  for (int j = i + 4; j < n; ++j) {
   dp[j] = Math.max(dp[j], dp[i] * (j - i - 3)); // using Ctrl + V
  }
    }
    return dp[n - 1];
}

References

• http://www.careercup.com/question?id=7184083 
• http://leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html
• http://shawnxublog.blogspot.in/2013/03/ctrla-ctrlc-ctrlv.html