Forum

Post 19.05.2009   # 1
Subject 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.

index             1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20    description 
---------------------------------------------------------------------------------------------------------------------------------
first removal X 2 X 4 X 6 X 8 X 10 X 12 X 14 X 16 X 18 X 20 odd indexes are removed
second removal x X x 4 x X x 8 x X x 12 x X x 16 x X x 20 indexes that are divisible by 2, but not with 4
third removal x x x X x x x 8 x x x X x x x 16 x x x X indexes that are divisible by 4, but not with 8
fourth removal x x x x x x x X x x x x x x x 16 x x x x indexes that are divisible by 8, but not with 16

We can see that after the i-th iteration, all indexes which are divisible by 2^(i-1), 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.

public class LastCharacter {
public String findLast(String s, int N) {
int n = s.length() * N;
int pow = 1;
while (n > 1) {
n /= 2;
pow *= 2;
}
int index = (pow - 1) % s.length();
return "" + s.charAt(index);
}
}

See the atanasko's solution http://www.codefu.com.mk/ProblemSolutionResult.do?competitorid=741&problemid=622 for a different approach.

bilievsk is offline Reply

Please login to post reply.