ROBO2 - Editorial

editorial
, , , ,
23

Help me with this -

Why are we checking for this -
if(grid[0][1] == ‘#’ || grid[1][0] == ‘#’ || grid[n-1][m-2] == ‘#’ || grid[n-2][m-1] == ‘#’) for unavailability of path.

Instead of this -
if(grid[0][1] == ‘#’ || grid[1][0] == ‘#’ || (grid[n-1][m-2] == ‘#’ && grid[n-2][m-1] == ‘#’))

Let’s consider a case -
n = 3 m = 3;
grid = . . #
. # #
. . .
In this case, the answer should be 6, the robot 1 will follow the path of - (0,0)->(1,0)->(2,0)->(2,1)->(2,2) and robot 2 will follow - (0,0)->(1,0)->(0,0)->(1,0)->(2,0)->(2,1)->(2,2) so the answer should be 6 in this case. But the solution its accepting returns -1 for this case.
We should only have to check for the starting position because on the first time we move, the robots should be on different cells but for destination we have to check for at least an adjacent open cell of destination cell.

24

Hello.
I think the way used by the Author’s code to greedily find two non-intersecting shortest paths might be incorrect.

You can check the issue using the following test:

1
7 8
....####
.##.####
..#.####
#.#.#...
......#.
.######.
........

The expected answer should be 15 as it is possible to find two non-intersecting shortest paths (see picture below).

Instead the author’s code outputs 17. That’s because the code constructs

  • the first path (green) by always moving upward. And if not possible it moves, in order, toward the left, toward the right and finally downwards.
  • the second path (red) by always moving downward. And if not possible it moves, in order, toward the right of the grid, toward the left and finally upward.

For this reason, the two shortest paths computed by the code intersect.

Expected VS obtained paths

comparison

I suppose one possible way to fix the issue would be to navigate the grid “in first person” like a maze and construct the first path by “always turning at your left” and the second path by “always turning at your right”.

I hope I didn’t miss anything and I was able to give you an idea of the issue and possible fix. I’m willing to elaborate if required.

25

Yes, the authors code is wrong.
But I think it can easily be fixed by the following:

  • the first path (green) by always moving upward. And if not possible it moves, in order, toward the left, toward the right and finally downwards.
  • the second path (red) by always moving downward. And if not possible it moves, in order, toward the left of the grid, toward the right and finally upward.

Can someone debunk my solution?
https://www.codechef.com/viewsolution/1125655635

26

I think the testcases are incorrect for this question, the part of having both grids next (n,m) empty seems incorrect as there still maybe a path.
Example:
3 3
…
…
##.
Correct output: 6
Submission output: -1
I made the following submission Submission#1126180978 with the following snippet added and it gets accepted.

  if (grid[n - 2][m - 1] == '#' || grid[n - 1][m - 2] == '#') {
    cout << "-1\n";
    return;
  }
27

You are not understanding the problem , it says that the robot need to reach simultaneously , so when the correct output is -1 and not 6 , because if the 1st robot reaches (3 , 3) at that instant the robot 2 should be at (2 , 2) or (3 , 1) , but in either of the cases , the robot1 would have no square and would be forced back to (2 , 3) and since robot 2 wants to chose the optimal path as well , it would come to (2 ,3) as well , which contradicts the problem statement , as it mentions that both robots should not be on same square except for (n , m) , so as a conclusion there should always be a spare(waiting) square for robot 1 in case robot 2 does not have a disjoint shortest path to (n , m). I hope you understand , else we can discuss more over this.

28

The answer can’t be 6 , check the bottom most comment , i just replied to some other user who addressed the same issue.

29

The problem says the have to be “at (N,M) simultaneously” not “reach simultaneously”.

From the above editorial when answer is (T+2):

Otherwise, robot 1 can follow the shortest path, while robot 2 can first move away from (1, 1) to the other cell, then move back to (1, 1), and then follow the shortest path

This also implies that they do not have to reach simultaneously.

30

You are still missing the point, the problem does say that they have to REACH at (N,M) simultaneously and not be there simultaneously. The answer can be T + 2 because when the first robot reaches it at time = T, the second robot is still 2 steps away from (N, M) and now the robot 1 plays a waiting move while robo 2 takes a step towards (N, M) , at this instant time = T + 1 . And exactly at time = T + 2 , both the robots REACH the destination simultaneously.

31

the problem does say that they have to REACH at (N,M) simultaneously and not be there simultaneously

The question literally says “be at (N,M) simultaneously”:

Your goal is to find the minimum time needed for both the robots to be at (N,M) simultaneously.

On further retrospection I found out that it is not possible for them to arrive out of sync, so in this case being their simultaneously also means reaching there at the same time.

1 Like