Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### techgig0's blog

By techgig0, 7 months ago, ,

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

• +4

 » 7 months ago, # | ← Rev. 2 →   +6 did the contest end ? (it's written in scoreboard "It's ongoing contest")
•  » » 7 months ago, # ^ |   0 There must be a bug. The contest has ended 1 hour ago.
 » 7 months ago, # |   0 Any hints for P3 , the tires problem ? I am thinking it to be dp but cannot think of the states .
•  » » 7 months ago, # ^ |   0 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))$
•  » » 7 months ago, # ^ |   0 I have used the same logic for 3. You can check out the code here.How to solve 2?
•  » » » 7 months ago, # ^ |   +1 For 2 I use disjoint sets union. Rather than removing the nodes from graph build the graph from last.
 » 7 months ago, # | ← Rev. 2 →   +30 this problem is identical to Subsequence Reversal
 » 7 months ago, # |   +1 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.
 » 7 months ago, # |   0 Anyone please share the approach for the 1st problem?
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ | ← Rev. 3 →   0 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?
•  » » » » 7 months ago, # ^ |   0 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.
•  » » » » » 7 months ago, # ^ |   0 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.
•  » » » » » » 7 months ago, # ^ |   +13 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 thatThe intended solution is using markov chain(some gauss elimination).
•  » » » » » » » 7 months ago, # ^ |   +3 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$?
•  » » » » » » » 7 months ago, # ^ |   0 What is the intended solution? You can't have n*m number of variables i guess. Can you share the complete approach.
•  » » » 7 months ago, # ^ |   +3 LOL. So, why they gave this year as well ;P
•  » » » » 7 months ago, # ^ |   +3 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.
•  » » » » » 7 months ago, # ^ |   +3 Exactly! It should be removed I guess. Actually, it doesn't matter xD
 » 7 months ago, # |   0 please! answer the subsequence reverse problem . i am not able to get the solution
 » 7 months ago, # |   0 you can look for the code to a similar USACO problem here.Problem
 » 7 months ago, # |   0 Solution for Subsequence Reversal: http://www.usaco.org/current/data/sol_subrev_platinum_jan17.html
•  » » 7 months ago, # ^ |   -8 can anyone explain me the approach.thanks! in advance.
•  » » » 7 months ago, # ^ |   -11 for the subsequence reversal problem Approach?