shas20's blog

USP 2015 tryouts problem D : Random walk in Thailand
By shas20, history, 8 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shas20 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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

Test 2

UPD: There is no nice format to display a test here, the previous is better to you, this is better for everyone else :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply