I have been trying this e-olymp ( https://www.e-olymp.com/en/problems/5852 ) problem lately. I got an O(n^2k) dp solution for it but I am getting trouble in determining whether a bridge from vertex i to vertex j is valid or not. Can anyone please help me with it.

Code- https://ideone.com/Qpq3b0 dp[i][j]- the minimum distance to reach vertex i from vertex 1 using j bridges

EDIT: This problem is still unsolved please help!!!

You can form bridge b/w two nodes if there is no node which is in between them and has higher y-coordinate than any of them. You can precompute the maximum y co-ordinate b/w all possible node pair in O(n^2). Suppose its maxy[i][j]. Then, while trying to build a bridge, check if maxy[i][j] < y[i] and y[j] or not.

Sorry…Didn’t read the define part. But again something which I found - you are printing dp[N][k] as your answer. It may be optimal to use lesser number of bridges though.

Tried printing min dp[n][i] for i=0 to k but still WA
Its giving WA in all the 50 testcases. So i think the problem is in the way i am determining a bridge is forming a tunnel or not?

The judging of this site for this problem seems to be faulty. When I got WA, I couldn’t believe it. So, I searched for a solution on Google (to clarify if I was not understanding the problem), I got to this blog of codeforces. The last comment on it suggests the same. He also gave a link to alternate judge on which we can submit the problem (I didn’t get the verification email so I couldn’t submit).

Just one more thing – Was this problem suggested in IOI Training Camp or what? Two more students have asked for help on this problem on Codeforces.

Hey himanshu you don’t need to wait for verifying your account. E-Olymp is fixed now see in that blog now i am getting 22% correct by the maximum y between i and j approach and 56% correct by my own another approach but still not full AC

Hey himanshu you don’t need to wait for verifying your account. E-Olymp is fixed now see in that blog now i am getting 22% correct by the maximum y between i and j approach and 56% correct by my own another approach but still not full AC