Hi guys, As I got time from footaball I was practicing competitive coding. I was doing this problem from Gym contest.
ThisLink to problem.
I came to know that there is no way to see test cases in Gym contest.
I want to know What mistake I am making also I will appreciate any other solution.
This is my code which fails on second test. My approach is first run dijkstra from n'th city and find shortest path theough boat for each city. Then for each city we can choose between Average+k or its original shortest path. So I try to minimize the average and find minimum value for first vertex.
Auto comment: topic has been updated by shas20 (previous revision, new revision, compare).
I don't know what exactly do you mean by average, but if you are calculating expected value correctly you should get full score. One thing to notice is that if you sort cities by distance to the target, then you will move through boats on a prefix of the cities and try to move random (on a plane) on a suffix. If you fix the break point you can easily calculate the expected value of moving on a plane. This value needs te be higher than the last city on the prefix (otherwise you prefer to move randomly on this city) and lower of the first city of the suffix (otherwise you prefer to move through the shortest path in boat). Be aware of corner cases like those where the graph is not conex.
Here goes test 2. Your mistake is in the second case, and I think is here. BTW, I check out your code and you were doing what I mention earlier except for checking the correctness of the break point, you took the smallest Expected value breaking at all points and probably thats the mistake. Good luck
20 6 6 7 3 4 5 1 6 6 6 4 4 5 3 4 3 1 5 2 4 5 10 8 1 3 8 1 6 7 9 2 3 9 1 10 5 2 7 3 6 1 7 8 9 9 10 5 1 6 8 9 1 3 8 2 6 1 3 2 6 6 4 3 4 2 8 6 1 4 5 1 9 2 5 9 8 10 6 3 2 8 2 7 8 7 6 3 7 4 7 4 3 2 6 4 8 6 2 8 1 7 1 8 5 6 7 5 7 7 6 8 7 2 9 5 7 3 5 2 1 3 6 5 2 6 2 2 4 3 8 7 3 1 3 8 8 3 7 7 1 7 4 2 8 5 4 4 2 8 2 4 8 2 7 7 3 2 3 5 3 6 5 6 7 7 4 5 1 5 2 4 5 6 7 5 1 5 7 6 4 5 3 2 7 4 8 2 7 9 1 2 8 3 7 7 4 5 7 10 6 7 8 6 5 7 8 4 3 1 5 5 1 3 2 7 5... Participant's output 6.000000000000000 3.666666666666667 4.000000000000000 14.000000000000000 0.000000000000000 6.800000000000000 13.333333333333334 10.166666666666666 0.000000000000000 0.000000000000000 7.000000000000000 3.000000000000000 0.000000000000000 7.000000000000000 0.000000000000000 8.000000000000000 7.000000000000000 3.000000000000000 5.000000000000000 0.000000000000000 Jury's answer 6.0000000000 5.0000000000 4.0000000000 14.0000000000 14.5000000000 8.2000000000 13.3333333333 12.2000000000 26.8000000000 10.0000000000 7.0000000000 3.0000000000 17.0000000000 7.0000000000 7.5000000000 8.0000000000 7.0000000000 3.0000000000 5.0000000000 4.0000000000 Checker comment wrong answer 2nd numbers differ — expected: '5.00000', found: '3.66667', error = '0.26667'
UPD: There is no nice format to display a test here, the previous is better to you, this is better for everyone else :)
Thanks a lot man!!!! This problem was killing me. Actually The mistake was I assumed that the graph will always be connected and it was always possible to get in boat to any possible city. The correctness checking as you said is not required. Since, If at a point this is not correct situation then definitely we will have even smaller answer hence it will never influence the answer.So that checking is not required. I hope I could give infinite upvotes for your help.