Forum
19.05.2009  # 1 
CodeFu 2009 Round 2  Problem 300
300. Last Character
This is the problem where most of the competitors didn't take into consideration the large constraints for N. Most of the submitted solutions were concatenating the input string N times, and then were simulating the character removal, until there is only one character left. For the worst case scenario (s.length() = 100, and N = 1.000.000) this solution need much more than the 5 seconds time limit. We needed some more sophisticated solution that will run under the time limit. In the following table, you can see a simulation, that shows which characters (their indexes) are removed in the each of the four steps.
We can see that after the ith iteration, all indexes which are divisible by 2^(i1), and not divisible by 2^i are removed. This means that the last remaining character will be on a position that has most twos as its prime divisors. So, first find the position of the last remaining character in the long string, and then using simple modulo arithmetic, find which character of the input string will be on that position.
See the atanasko's solution http://www.codefu.com.mk/ProblemSolutionResult.do?competitorid=741&problemid=622 for a different approach. 

Please login to post reply.