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

Ntimes (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 isM(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 (

*a*

_{1}.

*a*

_{2}…

*a*),

_{k}where

a_{1} + *a*_{2} + … + *a*_{k} = *n* – 2(*k*-1)

To obtain *M* = MAX (*a*_{1} . *a*_{2} … *a*_{k}),

it is necessary that the below condition must be met:

*i*,

*j*∈{ 1, 2, … ,

*k*} : MAX ( |

*a*–

_{i}*a*| ) = 1.

_{j}To obtain *M*, we can first divide *a*_{1} + *a*_{2} + … + *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*.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <cmath> #include <cassert> using namespace std; int findMaxK(int n) { int power = 2; double max = 0.0; int maxK = 0; while (n > 0) { n -= 2; double t = (double)n/power; double r = pow(t, (double)power); if (r > max) { maxK = power; max = r; } power++; } return maxK; } unsigned int f(int n) { if (n <= 7) return n; int k = findMaxK(n); int sum = n - 2*(k-1); unsigned int mul = 1; while (k > 0) { int avg = sum/k; mul *= avg; k--; sum -= avg; } assert(sum == 0); return mul; } |

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.

+4could 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?

-1A DP solution is not correct because you have to take into account how many A’s are in the clipboard

+1Hurray!!

I got the DP solution for this code………………….

int main(int argc,char *argv[]){

int n=30,max,mul,i,j;

int dp[30]={0,1,2,3,4,5,6,7};

for(i=8;i=0;j–){

if( dp[j]*mul>max )

max=dp[j]*mul;

mul+=1;

}

dp[i]=max;

}

for(i=0;i<n;i++){

printf("%5d",dp[i]);

}

}

0I 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.

0My 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;

}

0@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.

0How about using { Ctrl+A, Ctrl+C, A, Ctrl+V } instead of { Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V }

-1This 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.

0A 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;

}

0Interesting 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).

0Can 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.

+2@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.

0@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.

+2I 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}

+2Try 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.

+2Oops, it indeed replaces the selected text. Yes, it does not affect the main idea. It was however disturbing me. Thanks for the clarification.

+1then 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.

+2You only have a keyboard that has CTRL, A, C, V. You definitely don’t have arrows.

-1Here 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;

}

+1I think N = 8, S = { A, A, A, CTLA, CTLC, CTLV,, CTLV, CTLV }, M = 12

SO HOW ABOVE DESCRIBE ALGORITHM IS CORRECT.

+1Yes, 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.

+1this gives 9 i think

+1I 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.

+1@buried.shopno – could you explain the M[i-j] * (j-2)?

+1@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.

+1There 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

-1I 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!

-2A A A A A CTRL+A CTRL+C CTRL+V CTRL+V the result is 10,you may have a try.

0Wrong, 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

0123wafo

0Suppose 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.

+2The 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?

0I think you got the second DP solution wrong. It also gives 3072 as the result for N = 33. So 3072 is the right result.

0Ignore my last reply. Just found a small glitch in my code. Anonymous is right, it does give 3125 instead of 3072.

+1N – 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) );

}

-1Correction 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;

….}

}

0int findAs(int nKeys)

{ static int copiedAs = 0;

….if(num= result2)

……..{ copiedAs = temp;

………….return result1;

……..}

……..else

…………return result2;

….}

}

0Not able to post complete code…

int findAs(int nKeys)

{ static int copiedAs = 0;

….if(num= result2)

……..{ copiedAs = temp;

………….return result1;

……..}

……..else

…………return result2;

….}

}

0Correction: N=7 M=7 is correct. Open a notepad and try it. For N=7, it’s impossible to get M=8 or 9.

0I 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.

0this 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~!

0I 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;

}

0long long len = s[k] * ( i – (k-2));

should be

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

0#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;

}

}

0copy 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;

}

}

0Hi,

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) ?

0Attached my code in Java, Time O(n), Space O(1)

0correction:

it’s not “//aAxD”, it’s //aAaD–(a+1)D(a+1)D, there are (k-x) times a, (k) times a+1

+1Hi 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;

}

0Using 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;

}

0DP 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;

}

0something missing due to display error, retype it

for(int i =4; i <= n; ++i)

{

for(int j = 0; js[i])

s[i] = val;

}

}

0retry:

for(int j =0; j s[i]) s[i] = val;}

0the display really sucks. give up

0I 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.

0Hey, 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

0static 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;

}

0mark,very interesting. most early answers seem to be uncorrect

0Pingback: http://leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html | daniel6hz

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:

0Yes. I think you are right.

0Below 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);

}

0The solution is wrong. For N=7, it should be 8. The key sequence is:

[A, A, A, A, CTRL+A, CTRL+C, CTRL+V]

0My comment is wrong. Sorry

0Yet another DP in O(n^2)

0Hmm, some parts were not copied correctly:

+1Ah, 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;`

}

+1hum… 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;

}

}

+1The 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

000second half….

0>>>>>>>>>>>>>>>>

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

0paths:

00if n>7 && n<13, let's say 9… A A A A Ctrl+A Ctrl+C Ctrl+V Ctrl+V Ctrl+V

0if 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

0I 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)

012345678910

0Here 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

0ctrl+ v

0ctrl+A,CTRL+C,CTRL+V

0CTRL+V

0int 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;

}

0O(n) solution in C including printing of key sequence:

http://gatecse.in/wiki/Printing_A

0I 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))

0There is O(1) solution :

http://oeis.org/search?q=1%2C2%2C3%2C4%2C5%2C6%2C7%2C9%2C12%2C16%2C20%2C25%2C30%2C36&language=english&go=Search

0The formula to have the max A is f(x) = (N – 3x)*2^x , x in (0,N/3).

0O(1) code in Java:

Explanation:

1. As illustrated by the author, there won’t be any “A” keys once we have any Ctrl+A+C+V combinations, because if there is, that A can be moved before the Ctrl+A+C+V to generate at least the same number of characters or more.

2. That means, the sequence will always look like aAbDcDdDeD…

3. The total number of characters in the above sequence is: a*b*c*d*e…

4. The total number of keystrokes in the above sequence is: a + (b+2) + (c+2) + (d+2) + (e+2) + …

That means, the problem can be rephrased as:

Given a number N, find the optimum cuts C, such that we get (C + 1) positive numbers that add up to (N – 2C), whose product is the largest.

For example:

If N is 8, we can cut it into [3, 3], and the max product is 9;

if N is 20, we can use 2 cuts to get [5, 5, 6], and the max product is 150.

Key observations:

1. These cuts are commutative and associative, just like normal multiplication.

2. In the optimal cut, the numbers differ at most by 1. Otherwise, assume there are two unequal numbers A and B where A > B + 1, we can prove that (A – 1) * (B + 1) = A*B + A – B – 1 > A * B.

3. In the optimal cut, there can’t be a number equal or larger than 8. Because if there is, we can always cut it in half. In case of 8, we spend two extra characters to cut it into [3, 3], and the product becomes 9, bigger than 8.

4. In the optimal cut, there can’t be a number equal or smaller than 2. Because if there is any 2, we can combine it with another 2 or 3. Because by saving one cut, we save two keystrokes, the end result is bigger.

With that in mind, we have only a few possibilities to explore:

1. [3, 4] keystrokes between each Ctrl+A+C.

2. [4, 5] keystrokes between each Ctrl+A+C.

2. [5, 6] keystrokes between each Ctrl+A+C.

2. [6, 7] keystrokes between each Ctrl+A+C.

Since we know each cut costs two extra keystrokes (Ctrl+A+C), we can derive a formula to calculate the total number of cuts, given the number of keystrokes we want between each Ctrl+A+C, as seen in getCacvGroups().

And once we have the number of groups, we can easily calculate how many *effective* keystokes are left to generate the max product: (N – 2C).

Once we have that, the problem is reduced to a simpler one:

Given a number N, how do you divide it into C+! smaller numbers, with the max product?

It’s actually simple math question: just try to keep all the numbers round the average. That is, if N is 9 with 2 cuts, the optimal result is 3 * 3 * 3. The proof is similar to the one we did above: no two numbers in the optimal cut can differ more than 1, because otherwise we can move both 1 step toward the average and the product becomes larger.

In the end, we loop 5 times, and each loop body is an O(1) operation.

+1Correction:

The code should also check small inputs where N 7 * 7.

+1I wonder how you arrive at

I can only get a range for the group number for pair(a, a+1)

which is (ceiling((n – a – 1)/(a + 3)) + 1, floor((n – a)/(a + 2)) + 1).

Could you elaborate a little more?

0My code is here:

Same as JY’s except that I can only reach a range for the group number: suppose the minimum number we use is a, then a * groupNumber = (N + 2) / a; for the same reason we got groupNumber <= (N + 2) / b; we know a == 3, b == 7 as explained by JY.

Overall, the algorithm is O(n) only

0Somehow the text was modified when submitted. Here it is again

Same as JY’s except that I can only reach a range for the group number: suppose the minimum number we use is a, then a * groupNumber <= N – 2 (groupNumber – 1), so groupNumber = (N + 2) / b; we know a == 3, b == 7 as explained by JY.

Overall, the algorithm is O(n) only

0The initial assumption that for N M=N is wrong! Consider why this is so?

Input: N = 7

Output: 9

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

Input: N = 11

Output: 27

We can at most get 27 A’s on screen by pressing

following key sequence.

A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A,

Ctrl C, Ctrl V, Ctrl V

0Maximum Number of A’s with 1 keystrokes is 1

Maximum Number of A’s with 2 keystrokes is 2

Maximum Number of A’s with 3 keystrokes is 3

Maximum Number of A’s with 4 keystrokes is 4

Maximum Number of A’s with 5 keystrokes is 5

Maximum Number of A’s with 6 keystrokes is 6

Maximum Number of A’s with 7 keystrokes is 9

Maximum Number of A’s with 8 keystrokes is 12

Maximum Number of A’s with 9 keystrokes is 16

Maximum Number of A’s with 10 keystrokes is 20

Maximum Number of A’s with 11 keystrokes is 27

Maximum Number of A’s with 12 keystrokes is 36

Maximum Number of A’s with 13 keystrokes is 48

Maximum Number of A’s with 14 keystrokes is 64

Maximum Number of A’s with 15 keystrokes is 81

Maximum Number of A’s with 16 keystrokes is 108

Maximum Number of A’s with 17 keystrokes is 144

Maximum Number of A’s with 18 keystrokes is 192

Maximum Number of A’s with 19 keystrokes is 256

Maximum Number of A’s with 20 keystrokes is 324

0Here’s a function that will brute through it. It looks at the possible number of ways to cut the string and stops once it finds the product to decrease. For example, for n = 7, it checks 0 cuts = 7, 1 cut = 3*3 or 9, 2 cuts = 1*2*2 = 4, then stops and returns m=1 and the corresponding string. I’m kinda an amateur programmer, so this might not be very elegant. Also, I have an argument passing into the makeList function that determines what it returns, which may be unconventional. Anyway, I feel good about this solution. The final lines of code will iterate through the first 50 numbers. I’ve included the output on the bottom.

def turnToString(var):

string = ‘A’*var[0]

for z in var[1:]:

string += “SC” + “V”*z

return string

def sumList(inputs):

total = inputs[0]

for a in inputs[1:]:

total *= a+1

return total

def makeList(slices, number, funtype):

parts = slices + 1

final = number – 2*slices

a = final/parts

b = final%parts

number = [a]*parts

for z in range(b):

number[z] += 1

if funtype == ‘each’:

return number

elif funtype == ‘sum’:

return sumlist(number)

elif funtype == ‘as’:

return turnToString(number)

def findBest(opt):

for a in range(opt):

if makeList(a, opt, ‘sum’) – makeList(a+1, opt, ‘sum’) > 0:

return a

return 0

for a in range(50):

print a, findBest(a), makeList(findBest(a), a, ‘as’), makeList(findBest(a),a,’sum’)

0 0 0

1 0 A 1

2 0 AA 2

3 0 AAA 3

4 0 AAAA 4

5 0 AAAAA 5

6 1 AASCVV 6

7 1 AAASCVV 9

8 1 AAASCVVV 12

9 1 AAAASCVVV 16

10 1 AAAASCVVVV 20

11 2 AAASCVVSCVV 27

12 2 AAASCVVVSCVV 36

13 2 AAASCVVVSCVVV 48

14 2 AAAASCVVVSCVVV 64

15 3 AAASCVVSCVVSCVV 81

16 3 AAASCVVVSCVVSCVV 108

17 3 AAASCVVVSCVVVSCVV 144

18 3 AAASCVVVSCVVVSCVVV 192

19 3 AAAASCVVVSCVVVSCVVV 256

20 4 AAASCVVVSCVVSCVVSCVV 324

21 4 AAASCVVVSCVVVSCVVSCVV 432

22 4 AAASCVVVSCVVVSCVVVSCVV 576

23 4 AAASCVVVSCVVVSCVVVSCVVV 768

24 4 AAAASCVVVSCVVVSCVVVSCVVV 1024

25 5 AAASCVVVSCVVVSCVVSCVVSCVV 1296

26 5 AAASCVVVSCVVVSCVVVSCVVSCVV 1728

27 5 AAASCVVVSCVVVSCVVVSCVVVSCVV 2304

28 5 AAASCVVVSCVVVSCVVVSCVVVSCVVV 3072

29 5 AAAASCVVVSCVVVSCVVVSCVVVSCVVV 4096

30 6 AAASCVVVSCVVVSCVVVSCVVSCVVSCVV 5184

31 6 AAASCVVVSCVVVSCVVVSCVVVSCVVSCVV 6912

32 6 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVV 9216

33 6 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 12288

34 6 AAAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 16384

35 7 AAASCVVVSCVVVSCVVVSCVVVSCVVSCVVSCVV 20736

36 7 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVSCVV 27648

37 7 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVV 36864

38 7 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 49152

39 7 AAAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 65536

40 8 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVSCVVSCVV 82944

41 8 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVSCVV 110592

42 8 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVV 147456

43 8 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 196608

44 8 AAAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 262144

45 9 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVSCVVSCVV 331776

46 9 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVSCVV 442368

47 9 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVV 589824

48 9 AAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 786432

49 9 AAAASCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVVSCVVV 1048576

-Ben

0Hurray!!

I got the DP solution for this code………………….

int main(int argc,char *argv[]){

int n=30,max,mul,i,j;

int dp[30]={0,1,2,3,4,5,6,7};

for(i=8;i=0;j–){

if( dp[j]*mul>max )

max=dp[j]*mul;

mul+=1;

}

dp[i]=max;

}

for(i=0;i<n;i++){

printf("%5d",dp[i]);

}

}

0To embed your code, please use

.

0