Hello everyone,

I was trying to solve INOI 2019 Problem 2 - Interesting Sequences. I have tried the DP solution.

My approach -

1) Sort array and check for elements with same values and store the maximum answer possible.

2) LIS type DP to check the maximum answer.

3) Print the maximum of answers obtained from 1 and 2.

My approach is giving WA. I have tried to understand other's solutions and I have noticed they are something like binary search + DP. I cant understand it. Please help.

Here is the link to the problem - https://www.codechef.com/INOIPRAC/problems/INOI1902

I implemented a simple BFS for this problem, which should give the shortest path in this case, but got only 3 test cases correct.

My solution: http://pastebin.com/thVPJZbK

When I looked at the test data from this page: All INOI contest problems, the test outputs seemed to be having a non-optimal path (probably using DFS) from the source to the destination.

The problem description states that if multiple routes are possible, print any one of them. But it seems the server doesn't find my solution to be correct.

Please help.

For those of you who haven't solved this problem, this is one of the best problems from which you can learn how limitations of memory and time can make an easy problem, difficult to solve!

Just when I obtained the accepted sign after several trials, I was quite disappointed that I got a worst case running time of 1.98 s . So I headed over to Keshav's github repository and when I tried out the solution posted, it gave me a worst case running time of 0.024 s. Wow! Now that's a huge improvement. I really wanted to upgrade my arsenal with the procedure that had been used, but to my dismay I couldn't understand how it actually works. It would be great if someone posted the technique and procedure employed in solving the problem in the link attached above!

Note: The test-cases in the server has a bug (missing output file I think). One of the solvers figured out a workaround. If the answer is 34443, do not output anything.