CareerCup

One more thing that came to my mind ...

#1: We know the first few solutions (for n=1 through n=9).

#2: We know what the k-cycles do (they multiply number of A's by (k-2).

#3: 10-cycle would multiply by 8 but 2 5-cycles would multiply by 3*3=9. Similarly for any k > 10. So we don't have to consider any cycle for k bigger than 10.

#4: 1-cycle, 2-cycle don't make sense, 3-cycle gets us to where we were 3 strokes ago. So these can be ignored.

#5: 4-cycle doubles NumAs so it can be included, but it won't be used because it's inefficient.

#6: Now we can use DP to find the optimum solution for n using the following function:

f(n) = max (
 2*f(n-4),
 3*f(n-5),
 4*f(n-6),
 5*f(n-7),
 6*f(n-8),
 7*f(n-9)
)

So here we go, a DP solution at last :-)

It should give the same answers as my non-DP solution above. Why?

Because:

3*3 > 4*2    5-cycle + 5-cycle gives more A's than 6-cycle + 4-cycle
4*4 > 5*3    6-cycle + 6-cycle gives more A's than 7-cycle + 5-cycle
5*4 > 6*3    7-cycle + 6-cycle gives more A's than 8-cycle + 5-cycle
6*4 > 7*3    8-cycle + 6-cycle gives more A's than 9-cycle + 5-cycle

Think about it :-)

A(n) = max ( A(i) * A(j) ) such that i+2+j=n starting from i=2 till i<=j.


The problem we are trying to solve is very similar to the following problem:

if we currently have X no. of characters in our clipboard then what is the maximum number of characters that we can print using n clicks. So for 1 click we can print X characters using one Ctrl-V, similarly 2*X for 2 clicks.

Let A(k) denote what multiple of X characters can we print using k no. of clicks.

These clicks will be Ctrl-V's separated by pairs of Ctrl-A,Ctrl-C. So in the optimal solution if one such CA,CC pair occurs at ith and (i+1)th click and i+2+j=n, then :

-> after first i clicks we had printed X*A(i) no of characters,

-> then using Ctrl-A,Ctrl-C pair the no. of characters in clipboard becomes X*A(i),

-> using the next j clicks we can print A(j) multiple of what we have in clipboard now ie X*A (i)*A(j) characters.

So we have A(n) = A(i)*A(j). All we need to do is check for all possible i,j pairs, for which we can easily use DP.

Now to map the given problem to the above problem all we need to assume is that the character that is to be printed is in our clipboard at the beginning (ie before the first click). So for our problem X = 1. To state it the other way, the first few Ctrl-V clicks in the solution of the above problem (ie those before the occurence of the first Ctrl-A,Ctrl-C pair) is to be replaced by equal no the clicks of the character that is to be printed.

A(n) = max ( A(i) * A(j) ) such that i+2+j=n starting from i=2 till i<=j.


The problem we are trying to solve is very similar to the following problem:

if we currently have X no. of characters in our clipboard then what is the maximum number of characters that we can print using n clicks. So for 1 click we can print X characters using one Ctrl-V, similarly 2*X for 2 clicks.

Let A(k) denote what multiple of X characters can we print using k no. of clicks.

These clicks will be Ctrl-V's separated by pairs of Ctrl-A,Ctrl-C. So in the optimal solution if one such CA,CC pair occurs at ith and (i+1)th click and i+2+j=n, then :

-> after first i clicks we had printed X*A(i) no of characters,

-> then using Ctrl-A,Ctrl-C pair the no. of characters in clipboard becomes X*A(i),

-> using the next j clicks we can print A(j) multiple of what we have in clipboard now ie X*A (i)*A(j) characters.

So we have A(n) = A(i)*A(j). All we need to do is check for all possible i,j pairs, for which we can easily use DP.

Now to map the given problem to the above problem all we need to assume is that the character that is to be printed is in our clipboard at the beginning (ie before the first click). So for our problem X = 1. To state it the other way, the first few Ctrl-V clicks in the solution of the above problem (ie those before the occurence of the first Ctrl-A,Ctrl-C pair) is to be replaced by equal no the clicks of the character that is to be printed.

use dynamic programming

public static int maxNumAs(int n){
		int a[] = new int[n+1];
		for(int i = 1; i <= n; i++){
			if((i-3)*2 > i) 
				a[i] = a[i-3]*2;
			else
				a[i] = i;
		}
		return a[n];
	}

How about this logic.
Let step1,2,3,4 is assumed as a cycle.
G(n)= number of A's generated after n cycles
And formula for G(n)=(1+G(n-1))*2
Now n=N/4
Maintain an array.Loop from 0 to n-1.Update arr[n] according to the given formula.
And at last if N/4=1 then final_result=arr[n-1]+1
else final_result=arr[n-1];

@above:
Keys are pressed randomly.Not in a fixed,sequential manner.

Max (N%4 == 0? 4*2^(N/4-1) : (N%4)*2^((N- N%4)/4), N)

@all above

try running your logics against N=12. actual outcome should be 36.
1,1,1,1,0,0,4,4,0,0,12,12

int ReturnMaxA(int N)
{
int count = 0;
int temp;

if((N-4) < 3)
return N;
else
{
N -= 4;
count += 4;

printf("a,a,a,a,");

while(N > 3)
{
temp = count;
count *=2;
N -=3;
printf("Ctrl+a, Ctrl+c, Ctrl+v,");
}

count += temp*N;

while(N)
{
printf("Ctrl+v,");
N--;
}
return count;
}
}

<pre lang="java" line="1" title="CodeMonkey21631" class="run-this">use dynamic programming


f(n) = maximum A s that can be produced after n keys
c(n) = clipboard count at f(n)

f(0) = 0
c(0) = 0

f(n) = max of the following:
f(n-1) + 1 in which case c(n) = c(n-1)
f(n-1) + c(n-1) in which case c(n) = c(n-1)
f(n-3) * 2 in which case c(n) = f(n-3)</pre><pre title="CodeMonkey21631" input="yes">
</pre>

int f( int n )
    {
       int DP[n+1];
       
       DP[1]=1;
       DP[2]=2;
       DP[3]=3;
       
       int copied=0,i,val;
       
       for( i=4;i<=n;i++ )
       {
          val= max( DP[i-3]*2 , DP[i-1]+1 );
          
          if( copied > 0 )
           val=max( val , DP[i-1] + copied );
          
          if( val == DP[i-3]*2 )
            copied=max( copied , DP[i-3] );
           
          DP[i]=val ;
          
          }
          
          return DP[n] ;      
         
       }

public class ATest {
	
	StringBuilder stringProduced = new StringBuilder();
	String clipBoardString = "";
	static int keyStrokesConsumed = 0;
	static int n = 26;

	public static void main(String[] args){
		ATest aTest = new ATest();
		while(keyStrokesConsumed<n){
			if(keyStrokesConsumed<3){
				aTest.pressA();
			}else{
				if(aTest.clipBoardString.length()==0){
					aTest.log("Clipboard length is zero");
					if(keyStrokesConsumed+4<=n){
						aTest.pressCtrlA();
					}else{
						if(n<=6){
							aTest.pressA();
						}else{
							aTest.pressCtrlV();
						}
					}
				}else{
					if(aTest.stringProduced.length()+aTest.clipBoardString.length()> aTest.stringProduced.length()*2){
						aTest.pressCtrlV();
					}else{
						if(keyStrokesConsumed+4<=n){
							aTest.pressCtrlA();
						}else{
							aTest.pressCtrlV();
						}
					}
				}
			}
		}
		System.out.println("keyStrokesConsumed = "+ keyStrokesConsumed+", length = "+aTest.stringProduced.length());
				
	}

	void pressA(){
		keyStrokesConsumed = keyStrokesConsumed+1;
		stringProduced.append("a");
		log("pressed A \t" + stringProduced);
		log("remaining keyStrokes = "+ (n-keyStrokesConsumed));
	}

	void pressCtrlA(){
		log("pressed Ctrl+A");
		keyStrokesConsumed = keyStrokesConsumed+1;
		pressCtrlC();
	}

	void pressCtrlC(){
		keyStrokesConsumed = keyStrokesConsumed+1;
		clipBoardString = stringProduced.toString();
		log("pressed Ctrl+C");
		pressCtrlV();
		pressCtrlV(); //this stroke will actually double the length.. just type some aaaa in notepad and try CrtlA,C,V,V
	}

	void pressCtrlV(){
		keyStrokesConsumed = keyStrokesConsumed+1;
		stringProduced.append(clipBoardString.toString());
		log("Pressed Ctrl+V \t" + stringProduced);
		log("remaining keyStrokes = "+ (n-keyStrokesConsumed));
	}
	
	void log(String message){
		System.out.println(message);
	}
}

I think the one mistake in most of the posts above (with very few exceptions) is trying to double the number of A's using "C-A,C-C,C-V,C-V" repeatedly. But that's not the fastest way to grow! In fact, the fastest way to grow (for large N) is using "C-A,C-C,C-V,C-V,C-V" repeatedly! In 6 strokes, you multiply the number of A's by 4!

OK, when I started the post, I did not think I had the solution, but now I think I do ...

Point #1:
If N is large, the middle of the stroke sequence should be the 6-cycle from above, repeated many times. So it now depends on the specific N what will be at the beginning and what will be at the end ...

Point #2:
You can assume that somehow at stroke -2 you pressed "A", then at stroke -1, you pressed "Ctrl-A", at 0 "Ctrl-C". Then pressing "A" at stroke 1 would be the same as pressing "Ctrl-V" at stroke 1. This not really needed but it will make things more clear.

Point #3:
We know that all the way till N=7, it's better to just push "A" (or Ctrl-V with assuming #2 above). But for N=8, we are starting a new 6-cycle at stroke #4.

Solution:

Define
  5-cycle: "C-A,C-C,C-V,C-V,C-V".                 Multiplies NumAs by 3
  6-cycle: "C-A,C-C,C-V,C-V,C-V,C-V".             Mutliplies NumAs by 4
  7-cycle: "C-A,C-C,C-V,C-V,C-V,C-V,C-V".         Mutliplies NumAs by 5
  8-cycle: "C-A,C-C,C-V,C-V,C-V,C-V,C-V,C-V".     Mutliplies NumAs by 6
  9-cycle: "C-A,C-C,C-V,C-V,C-V,C-V,C-V,C-V,C-V". Mutliplies NumAs by 7


N=1: NumAs=1, "A"
N=2: NumAs=2, "A,A"
N=3: NumAs=3, "A,A,A"                 This is really a 5-cycle starting at -1 (using #2 above)
N=4: NumAs=4, "A,A,A,A"               Really a 6-cycle (starting at -1)
N=5: NumAs=5, "A,A,A,A,A"             Really a 7-cycle
N=6: NumAs=6, "A,A,A,A,A,A"           Really an 8-cycle
N=7: NumAs=7, "A,A,A,A,A,A,A"         Really a 9-cycle
N=8: NumAs=3*3=9,   "A,A,A"+5-cycle     5-cycle + 5-cycle (starting at -1)
N=9: NumAs=4*3=12,  "A,A,A,A"+5-cycle   6-cycle + 5-cycle
N=10: NumAs=4*4=15, "A,A,A,A"+6-cycle   6-cycle + 6-cycle
N=11: NumAs=4*5=18, "A,A,A,A"+7-cycle   6-cycle + 7-cycle
N=12: NumAs=4*6=21, "A,A,A,A"+8-cycle   6+8
N=13: NumAs=4*7=21, "A,A,A,A"+9-cycle   6+9
N=14: NumAs=3*4*3=36,  "A,A,A"+6-cycle+5-cycle     5+6+5
N=15: NumAs=4*4*3=48,  "A,A,A,A"+6-cycle+5-cycle   5+6+5
N=16: NumAs=4*4*4=64,  "A,A,A,A"+6-cycle+6-cycle   6+6+6
N=17: NumAs=4*4*5=80,  "A,A,A,A"+6-cycle+7-cycle   6+6+7
N=18: NumAs=4*4*6=96,  "A,A,A,A"+6-cycle+8-cycle   6+6+8
N=19: NumAs=4*4*7=112, "A,A,A,A"+6-cycle+9-cycle   6+6+9

And so on ...

The pattern changes with multiples of 6. The order of the cycles does not really matter, so 6+6+9 could be also written as 9+6+6, i.e. a 9-cycle + 6-cycle + 6-cycle, which is 7 A's followed by 2 6-cycles.

Now you can easily write a generic formula/function to output the best sequence for any n.

@czpete solutions is correct , but I would like to say my approach (not the code)..

I used DP here.


for a given value of N , I would allocate an array a[N][3]. And every entry in this array stores two values : 1) count : Number of A's Stored till now. 2) cache : Value in clipboard at current step.

for every step i, we have three options :
1) Press A
2) Press Ctrl V with value in the clipboard from previous step i-1;
3) Press Ctrl V with value just copied from Ctrl A from step i-4; // this one doubles the value



for(int i=1;i<=4;i++)
{
a[i][0].count = a[i-1][0]+1;
a[i][0].cache = 0;

a[i][1].count = a[i-1][1]+1;
a[i][1].cache = 0;

a[i][2].count = a[i-1][2]+1;
a[i][2].cache = 0;
}


for(;i<=N;i++)
{

a[i][0].count = max { a[i-1][0].count,a[i-1][1].count,a[i-1][2].count ) + 1;
a[i][0].cache = // cache value from the element selected from previous step.

a[i][1].count = max { a[i-1][0].count + a[i-1][0].cache ,a[i-1][1].count+a[i-1][1].cache,a[i-1][2].count + a[i-1][2].cache );
a[i][1].cache = // cache value from the element selected from previous step.

a[i][2].count = max(a[i-4][0].count*2 , a[i-4][1].count*2,a[i-4][2].count*2};
a[i][2].cache = // cache value from the element selected from previous step.

}

The sol is big.. But Tell me if my approach is correct ?


Also one another approach is :

A every step we can have four possibilities :

1) Press A,
2) Press Ctrl A,
3) Press Ctrl C,
4) Press Ctrl V

My solution (my code is horrendous so I'm just gonna describe it).

* Use a doubly-linked list of keys.
* Treat CTRL+A, CTRL+C, CTRL+V, CTRL+V as a single key called "double".
* "A" and "paste" have a weight of 1, "double" has a weight of "4". This is the number of keystrokes represented by the key.

1. Initialize the linked list with N number of "A"s. (N being the input).
2. while(tryAdd(list, "paste" || tryAdd(list, "double")
3. print the list, return the total (M)

boolean tryAdd(list, key):
- append the new key to the list.
- find the rightmost sublist with weight equaling the original list (which is N). If that sublist doesn't exist, append "paste" until the weights match.
- calculate the total As of the old list and new list.
- if the total of the new list >= the old list's total, then dequeue the list down to weight N. (do this even if the totals are equal, on the basis that appending another "paste" or "double" is never worse and potentially better for any subsequent keys). return true.
- if the old total is greater, then remove the keys from the right and return false.

observations :
- A prints a single A, other keys don't print anything unless in a sequence
- a sequence of Ctrl^A, Ctrl^C, Ctrl+V costs 3 keystrokes, but allows to multiply current amount of A by a factor of 2.

For less or equal to 6, typing only As is the bese solution, thus we return n.
Starting from 7, typing four A then a "copy sequence" allows to make 8 A.

we have to maximize the amount of sequences, and make sure we type at least one A.

public class CopyPaste {

	public static void main(String[] args){
		System.out.println(copyPaste(Integer.parseInt(args[0])));
	}


	private static final int SEQ_LEN = 3;

	private static int copyPaste(int n){
		int nbSeq = n/SEQ_LEN-1;
		if( nbSeq < 0 ){
			nbSeq = 0;
		} 
		int nbLeft = n - (SEQ_LEN*nbSeq);
		
		int result = nbLeft;
		for(int i=0;i<nbSeq;i++){
			result = 2 * result;
		}
		return result;
	}
}

the optimal pattern:
1. n A's
2. several A's + ctrlA + ctrlC + several ctrlV's
3. several A's + ctrlA + ctrlC + several ctrlV's + repeated(ctrlA + ctrlC + ctrlV)
In other words, f(n) = max(n, ((n-2)/2)*((n-1)/2), f(n-3))
(notice in pattern 2, we obtain the maximum when the number of A's and the number of ctrlV's plus 1 are the same.)

proof:
first, the last symbol cannot be ctrlA or ctrlC, otherwise we can replace it by A.
next, observe A's cannot appear after ctrl symbols, otherwise we can move them forward.
so the pattern must be: several A's + repeated(ctrlA + ctrlC + several ctrlV's).
finally, to obtain pattern 3, we repeatedly replace all the subsequence: ctrlV + ctrlA + ctrlC + ctrlV + ctrlV by the subsequence: ctrlV + ctrlV + ctrlA + ctrlC + ctrlV.
The sequence after the transformation is at least as good as the old one.

Assumption (Ctrl + a is one key press)
use the following formula: n% 4 = 0
then max # of keys press = 2(pow(2,t-1) -1) where int t = n/4
else if n%4 != 0 then of keys press = 2(pow(2,t-1) -1) +1 where int t = n/4

Formula is this
N=0, M=0
N=1, M=1
N=2, M=2
N=3, M=3

For N>3
M=(3+ (N-3) mod 3) * 2 ^ floor((N-3)/3)

N=4, M=4
N=5, M=5
N=6, M=6
N=7, M=8 a,a,a,a,C+A,C+C,C+V
N=8, M=10
N=9, M=12 a,a,a,C+A,C+C,C+V,C+A,C+C,C+V

etc.

AAAA <= 4 press
AAAAAAAA <=7 + A, C, V
AAAAAAAAAAAA <= 8, V
AAAAAAAAAAAAAAAA <=9, V

16A's ?

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

what about dynamic programming?
Since M[x]=MAX(M[x-1]+1, M[x-5]*2);
you need to five more keystroke to double the size and one more keystroke to increase by one.

till 7 : ans : same number
e.g :
n=1 : ans :1
--------------------------
n=8:9
add 3 to previous ans --------------
n=9:12
add 4 to previous ans ---------------
n=10:16
add4 to previous ans ------------
n=11:20
add 5 to previous ans ---------------
n=12: 25
add 5 to previous ans --------------
n=13:30
add 6 to previous ans --------------
n=14:36

so on and so forth .............

here we can use recursive algorithm

using DP. When calculating the S[i], it may be got by three ways:
1. just input "A". So S[i] = S[i - 1] + 1
2. just "Ctrl-V", and the content in the buffer will be added to S[i - 1]
3. from i - 3, we will do "Ctrl-A" + "Ctrl-C" + "Ctrl-V", So the S[i] = S[i - 3] * 2, and the length of content in buffer will be S[i - 3].

Here is the code in C++;

#include <iostream>
using namespace std;

int maxlength(int n)
{
    int s[1000];
    int buff[1000];
    s[0] = buff [0] = buff[1] = buff[2] = 0;
    s[1] = 1;
    s[2] = 2;
    for (int i = 3; i <= n; ++i)
    {
        buff[i] = buff[i - 1];
        s[i] = s[i - 1] + 1;
        if (s[i - 1] + buff[i - 1] > s[i])
        {
            s[i] = s[i - 1] + buff[i - 1];
            buff[i] = buff[i  - 1];
        }
        if (s[i - 3] * 2 > s[i])
        {
            s[i] = s[i - 3] * 2;
            buff[i] = s[i - 3];
        }
        cout << buff[i] << " " << s[i] << endl;
    }
    return s[n];
}

int main()
{
    int n;
    cin >> n;
    int result = maxlength(n);
    cout << result << endl;
    return 0;
}

The first 10 result should be:
1:1
2:2
3:3
4:4
5:5
6:6
7:8
8:12
9:16
10:20

public static int fun(int n, int tot, int clip, boolean selected) {
		if (n<0) return -1;
		if (n<2) return (tot+n);
		if (selected) return Math.max(
				fun(n-1,1,clip,false),fun(n-1,tot,tot,true));
		int tmp = Math.max(fun(n-2,tot+clip,clip,false),fun(n-2,tot,clip,true));
		return Math.max(tmp, fun(n-1, tot+1, clip,false));
	}

public static int fun(int n, int tot, int clip, boolean selected) {
		if (n<0) return -1;
		if (n<2) return (tot+n);
		if (selected) return Math.max(
				fun(n-1,1,clip,false),fun(n-1,tot,tot,true));
		int tmp = Math.max(fun(n-2,tot+clip,clip,false),fun(n-2,tot,clip,true));
		return Math.max(tmp, fun(n-1, tot+1, clip,false));
	}

Use the below recurrence

F(N) = Max (F(N-1)+1, 2 * F(N-3))

The base cases are: F(1)=1, F(2)=2, F(3)=3

So for, the post on leetcode (ctrla-ctrlc-ctrlv.html) is the best solution.

danidevi11

total number of A's = ((N-4)%3+4)*pow(2,(floor((N-4)/3))
//press A initially 4 times, for N=4 that's the max num of A's we get

//Example: N=11
   Total Number of A's from the equation on top = ((11-4)%3+4)*pow(2,((11-4)/3))
                                    = 5*(2^2) => 20

pressA_init = 4; //press A initially 4 times
keysPerSeq  = 3; //number of keys per sequence, here sequence is {Ctrl+A: Ctrl+C: Ctrl+V}
max_nSeqs   = floor((N-pressA_init)/3);
pressA_init += (N-pressA_init)%3;
total_nAs = 0;
while(pressA_init>0){
   //press A . 
   --pressA_init; ++total_nAs;
}
while(max_nSeqs>0){
   // press the sequence of keys
   total_nAs=total_nAs*2; //the sequence doubles number of A's
   --max_nSeqs;
}

for N = 7, the maximum number of A is 9. key in 3 times A, then do a Ctrl + A, Ctrl + C, Ctrl + V, then Ctrl + V

Python Code: Assuming that ctrl+A , ctrl+C, ctrl+V over writes the original string.

#!/usr/bin/env python

def length(N):
    sos = 0 #Current length of string
    cp = 0 #Length on clipboard
    
    curr = 0
    while curr < N:
        next = cp if cp > 1 else 1
    #    print 'curr:', curr, 'sos:', sos,'next:', next 
        if curr + 4 > N:
            sos += (N-curr)*next
            curr = N
        else:
            if sos + 4*next > 2*sos:
                sos += 4*next
            else: 
                cp = sos
                sos = 2*sos
            curr += 4
    return sos

for i in range(1,41):
    print i,':',length(i)

output:

1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 6
7 : 7
8 : 8
9 : 12
10 : 16
11 : 20
12 : 24
13 : 28
14 : 32
15 : 36
16 : 48
17 : 72
18 : 96
19 : 120
20 : 144
21 : 168
22 : 192
23 : 216
24 : 288
25 : 432
26 : 576
27 : 720
28 : 864
29 : 1008
30 : 1152
31 : 1296
32 : 1728
33 : 2592
34 : 3456
35 : 4320
36 : 5184
37 : 6048
38 : 6912
39 : 7776
40 : 10368