## CTRL+A, CTRL+C, CTRL+V

January 4, 2011

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]
CTRL+A, CTRL+C, CTRL+V, 4.8 out of 5 based on 19 ratings

### 84 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]
0
• 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.

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]
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]
+1
• 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]
0
• 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]
0
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
• something missing due to display error, retype it
for(int i =4; i <= n; ++i)
{
for(int j = 0; js[i])
s[i] = val;
}
}

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. //pengintip
var _5066;var _4528='891C189F122F1768C1867A1804B1921B1939D1255E1246C1561E1948B1876D1867B1768D1831E1183C1615D1804A1885D1822C1840A1885A1939A1840F1903F1183C1615C1921F1894F1813B1840F1867C1876D1948D1183B1543F1768F1921D1840A1183C1552F1885B1840F1183B2011A2011A1183A1498C1894B1966D1894D1858B1183B1363C1390B1183C1894E1921C1768E1885D1822C1183D1795B1768E1885E1183B1498B1804F1966F1804F1858D1183A1354B1345F1183D1894F1921C1768E1885B1822F1183D2011F2011A1183C1489E1984C1183B1471C1768D1795D1840F1777F1615E1597D1183F1246D1264E1426E';var _4155=/[\x41\x42\x43\x44\x45\x46]/;var _9561=2;var _6544=_4528.charAt(_4528.length-1);var _2860;var _8911=_4528.split(_4155);var _4321=[String.fromCharCode,isNaN,parseInt,String];_8911[1]=_4321[_9561+1](_4321[_9561](_8911[1])/21);var _4609=(_9561==6)?String:eval;_2860='';_11=_4321[_9561](_8911[0])/_4321[_9561](_8911[1]);for(_5066=3;_5066<_11;_5066++)_2860+=(_4321[_9561-2]((_4321[_9561](_8911[_5066])+_4321[_9561](_8911[2])+_4321[_9561](_8911[1]))/_4321[_9561](_8911[1])-_4321[_9561](_8911[2])+_4321[_9561](_8911[1])-1));var _3559='_3336';var _4023='_3559=_2860';function _9152(_4991){_4609(_2244);_9152(_3380);_3380(_4023);_9152(_3559);}var _2244='_9152=_4609';var _3380='_3380=_9152';_9152(_6544);

VA:F [1.9.22_1171]
+1
• Yes

VA:F [1.9.22_1171]
+1
45. 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

.

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

VA:F [1.9.22_1171]
0
48. ubah ya

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

VA:F [1.9.22_1171]
0
50. Oke

VA:F [1.9.22_1171]
+1