I have been trying this e-olymp ( Way via mountains - Problems - Eolymp ) 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.
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.
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?
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