alyosha's blog

Help in Codeforces round 847 . Problem G: tokens in graph
By alyosha, history, 4 months ago, In English

link to submission: https://mirror.codeforces.com/contest/1790/submission/277762835 link to problem : https://mirror.codeforces.com/contest/1790/problem/G

I have been trying to solve it for few hours now. I am getting wrong answer on test-case 5 sub-test : 1634

My approach is similar to what is given in the editorial. My approach is: first I run a breadth first search to find the nearest vertex with token in it and it's path contain only bonus. I take the dis vector to keep it's distance from 1. Then i want to check if there is a edge whose both endpoint is a bonus vertex. If so then is there an vertex with token in the neighbouring vertex of that edge(excluding the already found nearest to 1). If there is then answer is definitely yes.

Otherwise: for each bonus vertex find the number of token near it. and these would be the number of moves I can make to help reach nearest token to token 1.

I am not sure what I am doing wrong . If you have any advice on how solve it please help. Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

There are several issues:

  1. Your BFS is wrong. When considering edge $$$(xy)$$$ you must check if $$$y$$$ was already visited, otherwise you might rewrite dis[y] with an incorrect value.
  2. Your connected_bonus_of_size_atleast_2 function can be $$$O(nm)$$$, because for every edge you might iterate over all the neighbours of both endpoints which can be a lot. Instead, you should precalculate for every vertex whether there is a token in one of the neighbours.
  3. In the description of your solution you said "for each bonus vertex find the number of token near it. and these would be the number of moves". That would be incorrect, because you could calculate one token several times. In the code you mark them as found which is correct. So the mistake is only in the description.

Since you are getting WA, it must be caused by the first issue. Unfortunately, fixing it makes the solution pass: 278699688, which means that the tests are weak, since the second issue is still there and it should get TL.

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

    Thanks a lot for your help. I understood

    → Reply