Hi, Is anyone else also facing the issue where in Problemset[Last Unsolved], problems that we had a wrong submission for earlier, but solved it later on, are still shown?

MikeMirzayanov, could you look into the issue please?

Thank you.

Upd [23/04/2018] : The bug still exists. Upd 2 [23/04/2018] : FIXED! Thank you Mike! :D

I was trying to solve this problem. Found it under the DP category on a2oj. But, after trying for a long time, I couldn't come up with any solution to the problem.

Could someone please help? Thanks.

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.

I was trying this question and this is the solution I came up with, but it timed out as it doesn't use memoization.

But I'm not getting the idea about how to memoize this solution. And I can't even find any good explanation for the question anywhere. Can someone please help?

Thanks.

I was trying to learn Mo's Algorithm from here and this was one of the suggested problems. But, I'm getting TLE verdict with Java, while my code is very similar to the one that the tutorial's author has written, in C++.

Can someone please tell me what am I doing wrong(slow)? Thanks.

UPDATE : Sorry, forgot to post a link for my code

I was wondering why does codeforces have registration for contests, unlike some other sites like codechef, hackerearth allowing participants to participate even in ongoing competitions.

I was solving this question on dp and I use Java as my preferred language for programming.

But, I got a stack overflow error when I submitted the solution in Java, while the same code when converted into C++, ran perfectly fine.

Here is the Java submission : link
and here is the C++ submission : link

So, I searched on the internet and found out that Java's stack space is very less. :/
So, is there any way I could solve this question recursively in Java? I don't want to switch to C++ as I am very comfortable with Java and really like to code in it.

Java users, do you always implement an iterative version of an algorithm which could be solved recursively?