pandey_04's blog

By pandey_04, 2 months ago, In English

Link to problem: problem Link to editorial: editorial

Problem B — Bad boy

I got the idea given in editorial but can anyone tell me how the distance will always be 2*(n — 1) + 2*(m — 1) when putting the two yoyos in corners which form a diagonal. And, won't the distance be larger if we put the yoyos on the diagonal which is farther from the position of Riley than the one which is closer ?? How the largest distance is always same irrespective of position of Riley. All comments are highly appreciated.

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

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The important thing here is that Riley's (or Anton's) position does not matter.
The distance can be maximized if Riley needs to travel along both the length and the width of the room twice.

This can be easily accomplished by placing the yoyos in 2 opposite corners ((1,1 and n, m) or (1,m and n,1)).

If both the yoyos are placed in such a manner, no matter where Riley is, he will always need to travel the maximum distance; because if he ends up closer to one of the yoyos, the distance between him and the second yoyo will become greater, and vice-versa...

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

No matter where he stands, he will have to atleast travel the entire perimeter(extra distance if he is inside the grid and not on the perimeter) if we keep yo-yos at ANY PAIR OF OPPOSITE DIAGONALS.
I'll explain with an example.
1->yoyo

0->empty

2->Anton

Path he travels is in bold

Anton at any corner
Anton inside the grid
Anton on the perimeter and not on a corner

And, won't the distance be larger if we put the yoyos on the diagonal which is farther from the position of Riley than the one which is closer ?? -> Observe that the position of the yo-yos do not matter. You can make your own grid and try it out yourself. The optimal ans will always be the same.

ALWAYS DRY RUN YOUR CODE.

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

    Great explanation, really appreciate the efforts. Thank you.