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!!!
Its valid if the distance b/w them is not greater than R. Were you asking something else?
I know that I was asking about-
“the bridge can’t go underground (so it shouldn’t form a tunnel in the mountain)”
How to determine whether the bridge is forming a tunnel or not?
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.
I already tried that but got WA
Why do you think the WA was due to that part only? Anyways, where is the code?
Code- https://ideone.com/Qpq3b0
dp[i][j]- the minimum distance to reach vertex i from vertex 1 using j bridges
You are keeping dp[][] of long long type.
ll stands for long double
(it should be ld but sorry)
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?
I just can’t understand anyone’s code except mine. Will try to implement it tomorrow and then match it with yours. Gotta sleep now
Ok I hope we will solve it tomorrow.
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.
1 of these 2 students was me. What did you do to determine whether a bridge is forming a tunnel or not in your code
I tried submitting in that link but it passed in only 13 testcases out of 50. So still our solution is wrong
still unsolved!!!
I saw ur comment just now. Let me get my account verified. Will try then.
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