There was a contest by Codenation today (13th Nov, 2016) and there were 3 questions to be solved in 1.5 hours.

Q1) Given a string s, 2 players can remove a single character turn by turn where player 1 starts first. But the condition to remove is that each player can remove a character which is at an index >= the index which was removed previously, and the string gets re indexed after each turn. In the 1st turn player 1 can remove any character. If the final string is lexicographically greater than the original string s, player 1 wins, else player 2 wins. We had to tell who will be the winner.

Constraints :

number of tests cases <= 10

length of string <= 100

I couldn't come up with a complete logic during the contest. How can we solve this question?

Q3) We are given n points on a straight line : a0, a1, ...., a(n — 1) (a[i] > 0). Also, there is a starting point, s = 0, and an ending point t (> a[n]). Out of the n + 2 points, we have to choose K + 2 points such that the minimum distance between any 2 consecutive points from the chosen ones is maximum. Also, s and t are always chosen, so essentially we have to choose K out of the n points a[0....n — 1].

For this, I thought of a dp solution :

First I added 0(the starting point) at a0, and shifted the rest by 1 place. Then,

Let dp(i, j, k) = min. dist. b/w any 2 consecutive points by using up to the ith point, with jth point being the previous one, and choosing k points so far.

And the base condition will be that to choose exactly 1 point when i >= 1 and j >= 0, dp[i][j][1] = a[1]. I calculated this dp in iterative manner.

Then, I keep track of answer as :

ans = INFINITY;

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

    for (int j = 0; j < i; j++)

        ans = min(ans, dp[i][j][K]);

Constraints :

1 <= n <= 600 1 <= k <= 100 1 <= t <= 11000 1 <= a[i] < t

But this could clear only 2 out of 3 sample cases. Can someone tell me what's wrong with this logic?

Thank You.