6

Recently in Topcoder, I faced a problem which stated as follows: "You have a text document, with a single character already written in it. You are allowed to perform just two operations - copy the entire text (counted as 1 step), or paste whatever is in the clipboard (counted as 1 step). When you paste whatever is there in the clipboard, the original text on the text document is appended with that on the clipboard. Copying overrites whatever there is on the cliboard. It is required to find the minimum number of steps required to print 'n' characters on the text document. For Example, to generate 9 characters - Copy the single character already present, Paste (2 chars), paste again (3 chars), copy (3 chars copied), paste (6 chars now), paste again (9 chars now). So, total number of steps required is 6 which is (3+3 sum of prime factors of 9).

Can someone tell, how is this problem related to sum of the prime factors of 'n'?

Thanks!

StrictMath
  • 59

1 Answers1

5

At every step, the number of characters copied to be pasted then an arbitrary number of times has to be a divisor of $n$(because no matter how many times we paste them then, the resulting amount of characters will be a multiple of the number of characters we copied). So let $\xrightarrow{a}$ mean that I copy the characters in the buffer and then I paste them $a-1$ times, multiplying the actual number of characters in the buffer by $a$ in $a$ steps.

So let's say that I applied this algorithm: $$\xrightarrow{a_1}\xrightarrow{a_2}\xrightarrow{a_3}\cdots\xrightarrow{a_n}$$ We may note that $\xrightarrow{\,a}\xrightarrow{\,b}$ and $\xrightarrow{ab}$ do the same thing. It is clear that if $a,b\ge2$,the first algorithm is better or equivalent, being equivalent iff $a=b=2$. If there is in fact a $\xrightarrow{4\,}$, we can replace it by a pair of $\xrightarrow{2\,}$ without changing efficiency or result. Then, if any $a_i$ is factorizable, that algorithm is not optimal. So every optimal algorithm is equivalent to the one that has all $a_i$ prime. Finally:

$$a_1+a_2+a_3+\cdots+a_n=\text{Sum of prime factors}$$

chubakueno
  • 5,623
  • Brilliant Argument - Although it did take a while for me to understand your explanation though.

    Many Thanks!!

     – StrictMath Mar 12 '14 at 21:11
  • @StrictMath You are welcome! Thank you for the problem too, I enjoyed doing this proof. And I must say that I love doing arguments about algorithms with arrows, it gives(me) the feeling of time :-) – chubakueno Mar 12 '14 at 21:28