Since the problems of the contest were pretty good, I think it needs a dedicated blog for post contest discussions. Please share the problems in comments as I haven't read all the problems(or provide screenshots).
One of the most interesting problem was: Given an array of $$$A$$$ of size $$$n$$$, you are allowed to reverse a subsequence atmost one time. You have to output maximum non-decreasing subsequence in the final array.
Constraints : $$$1 \leq n, A[i] \leq 50$$$
| Sample Input | Sample Output |
| 5 45 28 45 3 48 | 5 |
did the contest end ? (it's written in scoreboard "It's ongoing contest")
Any hints for P3 , the tires problem ? I am thinking it to be dp but cannot think of the states .
I did like, $$$dp[i][j]$$$ means starting from $$$i$$$ and covering $$$j$$$ holes continuously what is the minimum length I need. Try to think about it this way. My solution Time complexity was $$$O(n^2mlog(n))$$$
I have used the same logic for 3. You can check out the code here.
How to solve 2?
For 2 I use disjoint sets union. Rather than removing the nodes from graph build the graph from last.
this problem is identical to Subsequence Reversal
Interviewbit has one of the shittiest coding environment, also I have seen their most contests have questions picked from different contests over the internet. Nothing good about them.
Anyone please share the approach for the 1st problem?
AFAIK, It was the last problem from the last year's codersbit, which no one managed to solve last year. But people did manage to get partial points, using Markov Chains or something.
I came up with an observation that the paths of length more than 25 will not contribute much to the answer because the accuracy required is $$$1e-5$$$. Now we can use dp to get the probability of a particular recruiter to reach a cell after some x (<= 25) steps. But I didn't manage to debug this code. Does this seem right?
I left the contest after solving 1 problem. So, I have no idea whether anyone solved it this year or not. But last year, no one solved it completely and the editorials weren't released either.
No one solved it completely this year also. But many managed to get some partial points using some logic. It would be nice if someone can share the logic of their partial points.
I solved using dp to get partial points... dp[i][j][k] is probability to reach (i,j) after k steps from a recruiter.. Just did k upto 300, it gets tle after that
The intended solution is using markov chain(some gauss elimination).
Every path of length k will have a probability of $$$\frac{1}{4^{k}}$$$ isn't it? If so, why is length up to 200 even required when the required accuracy is only $$$1e-5$$$?
What is the intended solution? You can't have n*m number of variables i guess. Can you share the complete approach.
LOL. So, why they gave this year as well ;P
Because no one solved it completely last year xD. And considering no one solved it this year as well. They will probably give it next year too xD. But, I think that should've provided advantage to the people who got high partial scores on it the last time.
Exactly! It should be removed I guess. Actually, it doesn't matter xD
you can look for the code to a similar USACO problem here.
Problem
Solution for Subsequence Reversal: http://www.usaco.org/current/data/sol_subrev_platinum_jan17.html