CTRL+A, CTRL+C, CTRL+V

January 4, 2011 in Uncategorized

Imagine you have a special keyboard with the following keys:

  1. A
  2. Ctrl+A
  3. Ctrl+C
  4. 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 As that you can produce).

This question seemed like a brand new interview question from Google. Someone posted this problem on a discussion board, and it generated a lot of discussions, which unfortunately none of them is really helpful in solving this problem. Here, I discuss my approach and solution to this problem, and just like those other tricky questions from a typical Google interview — the common pitfalls you might fall into.

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 }.

You might ask why all A’s are typed before the sequence of { CTRL+A, CTRL+C, CTRL+V } operations.

Assume that we could insert A’s at the back of some sequence of { CTRL+A, CTRL+C, CTRL+V } and yield a maximum sequence. If we take all the A’s from the back and insert it at the front, this modified sequence must yield a larger number of A’s, since the number of A’s is multipled from the beginning. Therefore, by contradiction, all A’s must always be inserted at the front to yield the maximum number of A’s. Similar for the case where A’s are inserted in the middle of the sequence.

Before we proceed further, we introduce the 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 (a1 . a2ak),

where
a
1 + a2 + … + ak = n – 2(k-1)

To obtain M = MAX (a1 . a2ak),
it is necessary that the below condition must be met:

i, j ∈{ 1, 2, … , k } : MAX ( | aiaj | ) = 1.

To obtain M, we can first divide a1 + a2 + … + ak 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.

Below is the C++ code for my solution. It is pretty straightforward to output the sequence S. Given N, the function f() returns the maximum value of M.

VN:F [1.9.22_1171]
Rating: 4.8/5 (21 votes cast)
CTRL+A, CTRL+C, CTRL+V, 4.8 out of 5 based on 21 ratings

85 responses to CTRL+A, CTRL+C, CTRL+V

  1. Is it possible to use DP to solve the problem?

    Let M(i, j) denote the maximum number of A we can get by pressing A for i times and using totally j keys (i <= j). Then the recursion is as follows:

    M(i, j) = max_{k<=j}{i*M(i,k-3)*(j-k+1)}, 1<=i<=N, N-i<=j<=N.

    Correct me if I'm wrong.

    VA:F [1.9.22_1171]
    +1
    • could someone please explain why does i*M(i,k-3)*(j-k+1) mean?
      i stands for A is pressed i times, M(i, k-3) means max number of a by pressing A for i times and using totally k-3 keys, . then what the heck is j-k+1? and why do you need to multiple them together?

      VA:F [1.9.22_1171]
      0
    • A DP solution is not correct because you have to take into account how many A’s are in the clipboard

      VN:F [1.9.22_1171]
      0
    • I really doubt the DP works for this problem, since DP only works when current decision is based on the next decision. But when current decision affect the previous ones, I don’t know whether there is a way for that.

      VN:F [1.9.22_1171]
      0
  2. My solution using DP. The O(n^3) complexity is not so good though.

    int max_key_A(int n) {
    if (n <= 7) return n;

    int *M = new int[n+1];
    for (int i = 0; i <= n; i++)
    M[i] = 0;

    int maxa = 0;
    for (int i = 1; i <= n; i++) {
    M[i] = i;
    for (int j = i; j <= n; j++) {
    for (int k = i+3; k <= j; k++) {
    if (M[j] < (j-k+1)*M[k-3])
    M[j] = (j-k+1)*M[k-3];
    }
    }
    if (M[n] > maxa) maxa = M[n];
    }

    delete[] M;
    return maxa;
    }

    VA:F [1.9.22_1171]
    0
  3. @Anonymous:
    Awesome!
    I haven't thought of using DP, will study your solution later.

    I have tested your code and so far it matches my output for N=1 to N=87 (just change your return type from int to unsigned int to avoid overflow).

    For N=88, my output is different than yours. What I'm suspecting is my code might have overflow problem in the line:
    pow(t, (double)power);
    caused by findMaxK() function.

    VA:F [1.9.22_1171]
    0
  4. How about using { Ctrl+A, Ctrl+C, A, Ctrl+V } instead of { Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V }

    VA:F [1.9.22_1171]
    0
  5. This definitely does not work:
    { Ctrl+A, Ctrl+C, A, Ctrl+V }

    Because when you do CTRL+A, you are doing a select all. After the copy operation, all text are still being selected. When you type A, all text would then be replaced with a single A.

    VA:F [1.9.22_1171]
    0
  6. A DP running in O(n^2):

    int kcount(int n)
    {
    int* s = new int[n+1];
    for(int i = 1; i <= n; ++i)
    {
    s[i] = i;
    }

    for(int i =1; i <= n-4; ++i)
    {
    int val = 2*s[i];
    if(s[i+4] < val)
    {
    s[i+4] = val;
    }
    int delta = s[i];
    for(int j = i+5; j <= n; ++j)
    {
    val += delta;
    if(val > s[j])
    {
    s[j] = val;
    }
    }
    }
    int result = s[n];
    delete[] s;
    return result;
    }

    VA:F [1.9.22_1171]
    0
  7. Interesting post!

    Because longer sequences of #D are dominated by repeated sequences of smaller counts (8D < 3D3D, but has same number of keystrokes) it is possible to use O(N) DP to solve it efficiently.

    In fact, I suspect that because for longer runs 4D repeated is the most efficient, that it is possible to run in O(1) time, with a fixed amount of slop at the beginning and end to have sequences that are more efficient for a particular non multiple length of 4D4D4D… However I'm not sure how big that fixed slop is (it is probably pretty large).

    VA:F [1.9.22_1171]
    0
  8. Can you please explain in more details why for N =7, {A, A, A,CTRL+A, CTRL+C, CTRL+V,CTRL+V } do not work to produce 9'A but for N=8, {A, A, A,CTRL+A, CTRL+C, CTRL+V,CTRL+V , CTRL+V} it works and produces 9 A's. I am confused why repeated CTRL+V works for N=8 but for not N=7.

    VA:F [1.9.22_1171]
    +1
  9. @Anonymous1:
    Yup, you are right. It is possible to solve using DP in O(N). And you are also right about the possibility to run in O(1) time, and someone from the mitbbs forum had discussed about this upper bound you mentioned. I will update my post later with the overall conclusions.

    VA:F [1.9.22_1171]
    0
  10. @Anonymous2:
    Think carefully. To double the previous text, you need to do {CTRL+A, CTRL+C, CTRL+V, CTRL+V}. Two CTRL+V's are needed. Therefore, for the example you gave in N=7, it only produces 6A's.

    VA:F [1.9.22_1171]
    +1
    • I still do not get why ctrlA + ctrlC + ctrlV does not double the existing text.

      What does the following set of operations result in ?
      { A, CTRL+A, CTRL+C, CTRL+V}

      What does the following set of operations result in ?
      { A, A, A, CTRL+A, CTRL+C, CTRL+V}

      VA:F [1.9.22_1171]
      +1
      • Try that out in a text editor like notepad. { A, CTRL+A, CTRL+C, CTRL+V} should yield “A”. { A, A, A, CTRL+A, CTRL+C, CTRL+V} should yield “AAA”. This is because CTRL+V replaces the selected text by CTLR+A. Anyway, this is not the heart of discussion. The main idea should not be affected by this rule.

        VN:F [1.9.22_1171]
        +2
        • Oops, it indeed replaces the selected text. Yes, it does not affect the main idea. It was however disturbing me. Thanks for the clarification.

          VA:F [1.9.22_1171]
          0
        • then It is better to highlight and clarify this confusing assumption at the beginning of post , because the original question doesn’t mention you can not move cursor.

          VA:F [1.9.22_1171]
          0
          • You only have a keyboard that has CTRL, A, C, V. You definitely don’t have arrows.

            VA:F [1.9.22_1171]
            0
  11. Here is my solution for reference:
    using DP:
    M[n] = max{ 1+ M[n-1], (n-k-3)*M[k] + M[k] }

    Code:

    #include
    #include
    #include

    using namespace std;

    int main (int argc, char const* argv[])
    {
    int n = atoi(argv[1]);
    int *M = new int[n];

    M[0] = 1;
    for( int i = 1; i < n; i += 1)
    {
    int maxi = 0;
    maxi = maxi > (1+M[i-1])? maxi:(1 + M[i-1]);
    for(int k = 0; k <= i-4; k++)
    {
    int temp = M[k] + (i-k-3) * M[k];
    maxi = maxi > temp? maxi: temp;
    }
    M[i] = maxi;
    }
    cout << "result:" << M[n-1] << endl;

    delete[] M;

    return 0;
    }

    VA:F [1.9.22_1171]
    0
  12. I think N = 8, S = { A, A, A, CTLA, CTLC, CTLV,, CTLV, CTLV }, M = 12

    SO HOW ABOVE DESCRIBE ALGORITHM IS CORRECT.

    VA:F [1.9.22_1171]
    0
    • Yes, I agree with you. I found many mistakes with the given solution.. for N=7, I got M=8.(A, A, A, ctrlA, ctrlC, ctrlV, crtlV) => gives M=9; I think this solution is wrong.

      VA:F [1.9.22_1171]
      0
    • this gives 9 i think

      VN:F [1.9.22_1171]
      0
  13. I solved it using DP taking O(n^2). I put my code here : http://ideone.com/tucp4. It shows the sequence of keys to get the max number of As printed.

    VA:F [1.9.22_1171]
    0
  14. @buried.shopno – could you explain the M[i-j] * (j-2)?

    VA:F [1.9.22_1171]
    0
    • @dwight: To double the sequence it needs 4 key press (CTRL+A, CTRL+C, CTRL+V, CTRL+V), to triple the sequence it needs 5 key press (CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V), so on.

      So, when j = 4, M [i-4] has the value of max. number of A’s sequence using (i-4) chars, and (j-2) which is 2 gives “number of times” M[i-4] will be repeated by a sequence of CTRL+A, CTRL+C, CTRL+V, CTRL+V.

      For next iteration, j = 5, hence (j-2) gives 3 times of M[i-5]. Hope you get it now.

      VA:F [1.9.22_1171]
      0
  15. There is a concise DP solution. :-) FYI.
    http://tanliboy.wordpress.com/2011/05/01/some-interesting-google-interview-problems/

    1: 1
    2: 2
    3: 3
    4: 4
    5: 5
    6: 6
    7: 7
    8: 9
    9: 12
    10: 16
    11: 20
    12: 25
    13: 30
    14: 36
    15: 48
    16: 64
    17: 80
    18: 100
    19: 125
    20: 150
    21: 192
    22: 256
    23: 320
    24: 400
    25: 500
    26: 625
    27: 768
    28: 1024
    29: 1280
    30: 1600
    31: 2000
    32: 2500
    33: 3125
    34: 4096
    35: 5120
    36: 6400
    37: 8000
    38: 10000
    39: 12500
    40: 16384
    41: 20480
    42: 25600
    43: 32000
    44: 40000
    45: 50000
    46: 65536
    47: 81920
    48: 102400
    49: 128000
    50: 160000
    51: 200000
    52: 262144
    53: 327680
    54: 409600
    55: 512000
    56: 640000
    57: 800000
    58: 1048576
    59: 1310720
    60: 1638400
    61: 2048000
    62: 2560000
    63: 3200000
    64: 4194304
    65: 5242880
    66: 6553600
    67: 8192000
    68: 10240000
    69: 12800000
    70: 16777216
    71: 20971520
    72: 26214400
    73: 32768000
    74: 40960000
    75: 51200000
    76: 67108864
    77: 83886080
    78: 104857600
    79: 131072000
    80: 163840000
    81: 204800000
    82: 268435456
    83: 335544320
    84: 419430400
    85: 524288000
    86: 655360000
    87: 819200000
    88: 1073741824
    89: 1342177280
    90: 1677721600
    91: 2097152000
    92: 2621440000
    93: 3276800000
    94: 4294967296
    95: 5368709120
    96: 6710886400
    97: 8388608000
    98: 10485760000
    99: 13107200000
    100: 17179869184

    VA:F [1.9.22_1171]
    0
    • I don’t think this output is right:
      For example N=10: A A A A A CTRL+A CTRL+C CTRL+V CTRL+V CTRL+V the output should be 20!

      VN:F [1.9.22_1171]
      -2
      • A A A A A CTRL+A CTRL+C CTRL+V CTRL+V the result is 10,you may have a try.

        VN:F [1.9.22_1171]
        0
      • Wrong, your sequence only gets you 15 As. The answer of N=10, M=16 is correct. The CORRECT sequence is A A A A CTRL+A CTRL+C CTRL+V CTRL+V CTRL+V CTRL+V

        VA:F [1.9.22_1171]
        0
  16. Suppose the last time you press Ctrl+A is after n-k, then F(n) = F(n-k) * (k-2).
    F(n) = max(F(n-4)*2, F(n-5)*3, F(n-6)*4, F(n-7)*5, F(n-8)*6, F(n-9)*7).
    This can be easily done in O(n) using DP and the code should be very simple.

    There’s no need to consider k >= 10, because F(n-4)*2 = F(n-4-(k-4)) * (k-4 – 2) = F(n-k) * 2 * (k-6) already >= F(n-k) * (k-2) for k >= 10.

    As mentioned earlier, O(1) might be possible but it will be harder to prove.

    VA:F [1.9.22_1171]
    0
  17. The concise DP solution quoted by tanliboy is O(n^2). The DP solution using Haitao’s formula is O(n) time and O(1) space (using a ring buffer). They seem to give the same results.

    However the code in the original post gives different results for some inputs. For example f(33) = 3072 while both DP solution give 3125. 3125 = 5*f(26) is clearly more correct than 3072. Is it a logic error or just FP rounding error in the original post?

    VA:F [1.9.22_1171]
    0
    • I think you got the second DP solution wrong. It also gives 3072 as the result for N = 33. So 3072 is the right result.

      VA:F [1.9.22_1171]
      0
      • Ignore my last reply. Just found a small glitch in my code. Anonymous is right, it does give 3125 instead of 3072.

        VA:F [1.9.22_1171]
        +1
  18. N – Number of A’s

    1 – 1
    2 – 2
    3 – 3
    4 – 4
    5 – 5
    6 – 6 (Use 4th,5th,6th key for Ctrl-A,C,V)
    7 – 8 (Use 5th,6th,7th key for Ctrl-A,C,V)
    8 – 10(Use 6th,7th,8th key for Ctrl-A,C,V)
    9 – 12 (Use 4t,5th,6th AND 7th,8th,9th key for Ctrl-A,C,V)

    It can be solved by recursion:
    if (n<6)
    T(n) = n;
    else
    T(n) = (num – 3)*2

    int findAs(int numKeys)
    {
    if(numKeys < 6)
    return numKeys;
    else
    return( 2* findAs(numKeys-3) );
    }

    VA:F [1.9.22_1171]
    -1
    • Correction in above solution:

      When n is 7 we can also press ctr-V key and get number of A’s to be 9 instead of 8.

      So little modification in recursion function:

      if(n= T2(n) )
      ….{ T(n) = T1(n)
      ………copiedAs = T(n-3)
      ….}
      ….else
      ….{ T(n) = T2(n)
      ….}
      }

      1 – 1
      2 – 2
      3 – 3
      4 – 4
      5 – 5
      6 – Max(6,5) = 6, CopiedAs= 3
      7 – Max(8,9) = 9, CopiedAs= 3
      8 – Max(10,12) = 12, CopiedAs= 3
      9 – Max(12,15) = 15, CopiedAs= 3
      10- Max(18,18) = 18, CopiedAs= 9 (Chose T1 over T2 when equal and change copiedAs)
      11- Max(24,27) = 27, CopiedAs= 9
      12- Max(30,36) = 36, CopiedAs= 9
      13- Max(36,45) = 45, CopiedAs= 9
      14- Max(54,54) = 54, CopiedAs= 27 (CopiedAs changed)
      .
      .
      .
      .

      int findAs(int nKeys)
      { static int copiedAs = 0;
      ….if(num= result2)
      ……..{ copiedAs = temp;
      ………….return result1;
      ……..}
      ……..else
      …………return result2;
      ….}
      }

      VA:F [1.9.22_1171]
      -1
      • int findAs(int nKeys)
        { static int copiedAs = 0;
        ….if(num= result2)
        ……..{ copiedAs = temp;
        ………….return result1;
        ……..}
        ……..else
        …………return result2;
        ….}
        }

        VA:F [1.9.22_1171]
        0
      • Not able to post complete code…

        int findAs(int nKeys)
        { static int copiedAs = 0;
        ….if(num= result2)
        ……..{ copiedAs = temp;
        ………….return result1;
        ……..}
        ……..else
        …………return result2;
        ….}
        }

        VA:F [1.9.22_1171]
        0
        • Correction: N=7 M=7 is correct. Open a notepad and try it. For N=7, it’s impossible to get M=8 or 9.

          VN:F [1.9.22_1171]
          0
  19. I have the following idea, correct me if I am wrong
    ================================================================
    Since we have a chain of keystrokes like this:
    k “A”s ->(3 keystrokes, i.e., Ctrl-ACP)->2k “A”s ->(3 keystrokes)->4k “A”s ->(3 keystrokes)->….->2^n “A”s
    we use totally (k+3*n = N) keystrokes and produce k*2^n “A”s.
    Define the function f(k) = k*2^{(N-k)/3} as the number of consecutive “A”s produced, where 1 <= k <= N is a variable — by knowing the exact value of k, we will be able to see the maximum.
    It is clear that f(k) is monotonically increase before it reaches the maximum and monotonically decrease after that. View this function as an array with index [0,...,N-1]. Hence, we could use a (modified) binary search algorithm to identify the maximum of f(k), which is the solution to this problem.

    If the above is true, the algorithm works with O(log N) time.

    VA:F [1.9.22_1171]
    0
  20. this question can be done in O(1).
    the strategy should be like this:
    for N, we type ‘A’ k times, and then we do “ctrl-A, ctrl-C,ctrl-V,ctrl-V,…ctrl-V”

    now we can see M = max { max{ k(N-2-k) for k = 1,…,N-3 } , N }

    to make k(N-2-k) max, we can choose k that nearest to N-2-k, assume k = N-2-k, we get k=(N-2)/2; adopt this k, we calculate max k(N-2-k), then we get max M.

    no iterative, no recursive, no other space!

    correct me, if i am wrong~!

    VA:F [1.9.22_1171]
    +1
  21. I have an dp method with the same results as someone post before. O(n^2) time complexity and O(n) space complexity

    find a position for the last c+a, c+c, c+v, then after that all c+v.
    for(i = 8; i 0; k–){
    long long len = s[k] * ( i – (k-2));
    if(len > s[i]) s[i] = len;
    }

    VA:F [1.9.22_1171]
    0
    • long long len = s[k] * ( i – (k-2));
      should be

      long long len = s[k] * ( i – (k+2)); check the code

      VA:F [1.9.22_1171]
      0
  22. #include
    #include
    using namespace std;
    int main()
    {
    int N;
    while(cin>>N)
    {
    long long int arr[N+1];
    arr[0]=0;
    for(int i=1;i<8;i++)
    {
    arr[i]=i;
    }
    for(int i=8;i<=N;i++)
    {
    long long int max = -1;
    for(int k=1;kmax)max = mul;

    }
    arr[i] = max;
    }

    cout<<arr[N]<<endl;
    }
    }

    VA:F [1.9.22_1171]
    0
    • copy paste didnt work.. Retrying.

      #include
      #include
      using namespace std;
      int main()
      {
      int N;
      while(cin>>N)
      {
      long long int arr[N+1];
      arr[0]=0;
      for(int i=1;i<8;i++)
      {
      arr[i]=i;
      }
      for(int i=8;i<=N;i++)
      {
      long long int max = -1;
      for(int k=1;kmax)max = mul;

      }
      arr[i] = max;
      }

      cout<<arr[N]<<endl;
      }
      }

      VA:F [1.9.22_1171]
      0
  23. Hi,
    I was trying to understand the solution proposed by 1337c0d3r for this problem

    He has mentioned a statement :
    Let’s generalize the above:

    M = MAX (a1 . a2 … ak),
    where
    a1 + a2 + … + ak = n – 2(k-1)
    To obtain M = MAX (a1 . a2 … ak),

    Can sb please, let me know :
    1- What are a1, a2…ak ?
    2- What is ’k’ and how a1 + a2 + … + ak = n – 2(k-1) ?

    VN:F [1.9.22_1171]
    0
  24. Attached my code in Java, Time O(n), Space O(1)

    VA:F [1.9.22_1171]
    0
    • correction:
      it’s not “//aAxD”, it’s //aAaD–(a+1)D(a+1)D, there are (k-x) times a, (k) times a+1

      VA:F [1.9.22_1171]
      +1
  25. Hi guys:
    I think this problem can be converted to
    find the max product of the sequnence a1*a2*…*an, with ai takes (ai+2)step and the total step is n.

    Here is my DP code :

    int maxCtrlDp(int n){
    //number of factor can get from x1Dx2D…xkD in n step
    vector xDtable(n+1,1);

    for(int i=1;i+2<=n;i++){
    xDtable[i+2]=i;
    }
    //find the max factor in n step
    for(int x=2;x+2<=n;x++){
    for(int i=2+x;i<=n;i++){
    xDtable[i]=max(xDtable[i],xDtable[i-2-x]*x);
    }
    }

    int maxA=0;
    for(int i=1;i<=n;i++){//number of A
    maxA=max(maxA,i*xDtable[n-i]);
    }
    return maxA;
    }

    VA:F [1.9.22_1171]
    0
  26. Using greedy strategy

    #include
    #include

    using namespace std;

    int findMax(int N)
    {
    int i=0;
    int M=0;
    int copy=0;
    while (i<N)
    {
    if (i<3)
    {
    M++; i++; cout<=N)
    {
    if (!copy)
    { M++; i++; cout<<"A ";}
    else
    { M+=copy; i++; cout< M)
    { M += 3*copy; i+=3; cout<= 3)
    { copy=M; M+=copy; i+=3; cout<<"ctrl+A ctrl+C ctrl+V ";}
    else
    { M++; i++; cout<<"A ";}
    }
    }
    cout<<endl;
    return M;
    }

    main(int argc, char **argv)
    {
    int m = findMax(atoi(argv[1]));
    cout<<m<<endl;
    }

    VN:F [1.9.22_1171]
    0
  27. DP O(n^2)
    int kcount(int n)
    {
    int* s = new int[n+1];
    for(int i = 1; i <= n; ++i)
    {
    s[i] = i;
    }

    for(int i =4; i <= n; ++i)
    {
    for(int j = 0; j s[i])
    {
    s[i] = val;
    }
    }
    }
    int result = s[n];
    delete[] s;
    return result;
    }

    VA:F [1.9.22_1171]
    0
  28. I come up with a O(n) solution with O(1) space.
    The key points are:
    1) it can be proved that “A” sould be entered at the beginning (proof by controdiction)
    2) it can be proved that for X<N, if X-1 yeilds smaller number of A than X does, then all numbers previous to X can no longer be helpful yeilding more A's.

    So I use a deque to maintain the number of A yeilded from X to N-1 to compute that value for N. I do not know how to prove the O(1) space, but I print out the size of my deque and it is always <10.

    VN:F [1.9.22_1171]
    0
  29. Hey, the solution is really easy if you found the rule here.
    It’s simple O(n) and O(1) dp

    4D is the most efficient because it takes 6 strokes, and get 4 times of the original text, which is the best you can get from 6 strokes after any certain stroke. there’s no other possibility for 6 strokes, because it can’t be 2D2D since it takes 8 strokes.

    so you get max[n]=4*max[n-6] // if (4*max[n-6]>n), really simple right?!
    so simply traverse the array and apply the rule.
    you can check the result post by @tanliboy in the comment above

    VA:F [1.9.22_1171]
    0
  30. static int f(int keys, int copies)
    {
    if (copies == 1)
    return keys;
    else
    {
    int x = (keys – 2 * (copies – 1)) / copies;
    return x * f(keys – x – 2, copies – 1);
    }
    }

    static int f(int keys)
    {
    int oldCount = 0;
    int count = keys;
    int split = 1;
    while (oldCount < count)
    {
    split++;
    oldCount = count;
    count = f(keys, split);
    }

    return oldCount;
    }

    VN:F [1.9.22_1171]
    0
  31. mark,very interesting. most early answers seem to be uncorrect

    VN:F [1.9.22_1171]
    0
  32. Hi

    I found a little bug for your algorithm. For example:

    N = 33, S = { 5A5D5D5D5D }, M = 3125. But your output is : S = { 3A4D4D4D4D4D }, m = 3072.

    here is my code:

    VN:F [1.9.22_1171]
    0
  33. Below is the recursive algo for simplicity.

    int f(int n)
    {
    return re(n, 0, 0);
    }

    // n1: the strokes left
    // cCopied: copied As
    // c: the count of As already generated
    int re(int n1, int cCopied, int c)
    {
    if(n1==0)
    {
    return c;
    }

    int t1 = re(n1-1, cCopied, c+1); // if the next stroke is A
    int t2 = re(n1-1, cCopied, c+cCopied); // if the next stroke is ctrl-v
    int t3 = INT_MIN;

    if(n1>3) // if the next strokes are ctrl-a, ctrl-c, ctrl-v, ctrl-v
    {
    t3 = re(n1-4, c, 2c);
    }

    return max(t1, t2, t3);
    }

    VA:F [1.9.22_1171]
    0
  34. The solution is wrong. For N=7, it should be 8. The key sequence is:
    [A, A, A, A, CTRL+A, CTRL+C, CTRL+V]

    VA:F [1.9.22_1171]
    0
  35. Yet another DP in O(n^2)

    VA:F [1.9.22_1171]
    0
    • Hmm, some parts were not copied correctly:

      VA:F [1.9.22_1171]
      +1
  36. Ah, duh, it was the xml tag, sorry >.<"


    int max_keys(int strokes)
    {
    assert(strokes >= 0);
    if (strokes < 3)
    return strokes;

    int* solutions = new int[strokes];
    solutions[0] = 1;
    solutions[1] = 2;
    solutions[2] = 3;

    for (int stroke_index = 3; stroke_index < strokes; stroke_index++)
    {
    solutions[stroke_index] = 1 + solutions[stroke_index - 1];

    for (int copied_index = stroke_index - 4; copied_index >= 1; copied_index--)
    solutions[stroke_index] =
    max(
    solutions[stroke_index],
    (stroke_index - (copied_index + 2)) * solutions[copied_index]);
    }

    int max = solutions[strokes - 1];
    delete[] solutions;

    return max;
    }

    VA:F [1.9.22_1171]
    +1
  37. hum… 9 maps to 16 as my result as code below:

    private static int calculateMaxAs(int n) {
    if (n 3) {
    return (int) Math.pow(2, condition) * (1 + (n – 1) % 3);
    } else if (condition > 1 && condition <= 3) {
    return (n – 7) * 4 + 8;
    } else {
    return n;
    }
    }

    VA:F [1.9.22_1171]
    +1
    • The paste is wrong:( see below and hope that it is going to be paste right:

      private static int calculateMaxAs(int n) {
      if (n 3) {
      return (int) Math.pow(2, condition) * (1 + (n – 1) % 3);
      } else if (condition > 1 && condition <= 3) {
      return (n – 7) * 4 + 8;
      } else {
      return n;
      }
      }

      8-12
      9-16

      VA:F [1.9.22_1171]
      0
  38. VA:F [1.9.22_1171]
    0
  39. VA:F [1.9.22_1171]
    0
    • second half….

      VA:F [1.9.22_1171]
      0
  40. >>>>>>>>>>>>>>>>
    Actually there is a tricky answer for this question, (still need to code as above eventually:)). First the answer will be only click on A key…N times… N is the max … Reason is that if there is no mouse involved, which I mean after Ctrl+A the focus doesn’t move to next space, whatever you paste or click would always replace what you have….

    VA:F [1.9.22_1171]
    0
  41. paths:

    VA:F [1.9.22_1171]
    0
    • VA:F [1.9.22_1171]
      0
      • if n>7 && n<13, let's say 9… A A A A Ctrl+A Ctrl+C Ctrl+V Ctrl+V Ctrl+V

        VA:F [1.9.22_1171]
        0
        • if n>=13, let’s say 14… A Ctrl+A Ctrl+C Ctrl+V Ctrl+A Ctrl+C Ctrl+V Ctrl+A Ctrl+C Ctrl+V Ctrl+A Ctrl+C Ctrl+V Ctrl+V

          VA:F [1.9.22_1171]
          0
  42. I think this is a indirect DP problem with two parts. The first part is calculate the times array, the second part is using the times array to compute the maximum.
    The times array is that: given a string with length k, how many times longer we can get using index operations. For example times[i] = t indicates that using i operations we can get t*k length strings.
    Then this problem transform to find the times array and using it to compute maximum.
    How to get times array? Actually, I found that C-A C-C C-V get 1*original string, C-A C-C C-V C-V get 2*original string etc. So we need to use these sequence to cover at most n slots. So my formula is times[i] = max{ 1*times[i-3], 2 *time[i-4], 3*times[i-5] ….(j-2)*times[i-j].}
    Then we just make continuous x As at the beginning with following times. Of course, n <= 7, best = 7.
    Totally, time complexity is O(n^2)

    VN:F [1.9.22_1171]
    0
  43. 12345678910

    VA:F [1.9.22_1171]
    0
  44. Here is my solution with code at stackoverflow.com. It also prints the sequence of keystrokes.

    http://stackoverflow.com/questions/4606984/maximum-number-of-characters-using-keystrokes-a-ctrla-ctrlc-and-ctrlv/22542395#22542395

    VA:F [1.9.22_1171]
    0
  45. ctrl+ v

    VA:F [1.9.22_1171]
    0
  46. ctrl+A,CTRL+C,CTRL+V

    VA:F [1.9.22_1171]
    0
  47. xyz said on May 25, 2014

    int MaxCopy(int n){
    int *table=(int *)malloc(sizeof(int)*(n+1));
    memset(table,0,sizeof(int)*(n+1));

    for(int i=0;i<=n;i++){
    table[i]=i;
    }
    for(int i=0;i<=n;i++){
    for(int j=i+4;j<=n;j++){
    table[j]=max(table[j],table[i]*(j-i-2));
    }
    }
    int res=table[n];
    free(table);
    return res;
    }

    VA:F [1.9.22_1171]
    0
  48. O(n) solution in C including printing of key sequence:

    http://gatecse.in/wiki/Printing_A

    VA:F [1.9.22_1171]
    0
  49. I think there should be something wrong with the answer…
    E.g. n=7, m =9; n =8, m =12(aaa, aaa(ctrl a, c, v), aaa(ctrl v), aaa(ctrl v))

    VN:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.