CHEFARC - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Mugurel Ionut Andreica
Editorialist: Praveen Dhinwa

DIFFICULTY:

Easy

PREREQUISITES:

breadth first search (bfs)

PROBLEM:

You are given a n \times m size grid. Some of the cells of the grid are blocked. There are two robots one standing at (1, 1) and other at (n, m). In a single move, a robot can move from a cell (i, j) to cell (x, y) such that |x - i| + |y - j| \leq K, where K is fixed a constant (it can be different for robots, i.e. K_1, K_2). Both the robots make moves simultaneously, find out minimum number of moves required so that both the robots meet at some common cell. If it is not possible for them to meet, print -1.

EXPLANATION:

What if the grid was not blocked
Note that if the grid would not have any blocked cells, then this turns into a greedy problem. Both the persons can make move greedily towards each other.

With blocked grid cells
Now, some of the grid cells might be blocked. You might think of finding whether there is a cell (i, j) which is reachable from both (1, 1) and (n, m) in exactly some i moves, where i can go up to n * m. You can check whether it is possible to reach cell (i, j) in k moves by a dp solution. Let dp(i, j, k) denote whether it is possible to reach cell (i, j) from cell (1, 1) or not. Note that dp(i, j, k) = min(dp((i, j, j), dp(x, y, k - 1) + 1, where |x - i| + |y - j| \leq K. Base case will be when k = 0, i.e. whether (i, j) is same cell as that of (1, 1) or not.

Unfortunately, this solution is quite slow. We need to think of something faster.

An interesting observation
Notice that the operations are in such a way that one can stay at its cell in an operation. Consider a cell (i, j), if the minimum number of steps required to reach cell (i, j) from (1, 1) be S_1 and that from (n, m) be S_2. Then, in max(S_1, S_2) steps, both the robots can meet at cell (i, j). It is simply due to the fact that the robot with the smaller distance to cell (i, j) will reach at the cell and will just stay their in its next remaining operations. The other robot will keep on moving meanwhile.

So, we need to find shortest distance of each robot to reach each cell (i, j). For that, we can do a bfs from cell (1, 1) and (n, m). The vertices of the graph will be all the cells of the grid. There will be an edge between two cells (i, j) and (x, y) of weight 1 if it is possible to reach from cell (i, j) to cell (x, y). Notice that if we can reach from cell (i, j) to cell (x, y) in a single step, then we reach from cell (x, y) to cell (i, j) in a single step too. This guarantees that our graph will be undirected. Finding shortest distance between a fixed node with other nodes in an unweighted (i.e. weight = 1) undirected graph can be done using breadth first search algorithm.

Time Complexity
Time complexity of breadth search algorithm is \mathcal{O} (V + E), where V denotes number of vertices and E denotes number of edges in the graph. In our graph, there are total \mathcal{O}(N * M) vertices. Number of edges in our graph will be \mathcal{O} (N * M * K * K).

So, overall time complexity will be \mathcal{O} (N * M * K_1 * K_2).

Tester’s Solutions:

Tester’s solution

2

In the editorial, it should be (1,m) not (n,m) as the second robot was standing on the first row, last column.

2 Likes
3

What is qli and qls in the tester’s solution?

4

in some solutio in bfs , while traversing why we traverse corner cell?? why not adjacent cell??

5

Can someone explain what this piece of code does in the Tester’s solution (lines 32-35) :

if (A[ii][jj] == 0 && d[i][j] + 1 < d[ii][jj]) {
				d[ii][jj] = d[i][j] + 1;
				qls++;
				q[qls][0] = ii; q[qls][1] = jj;
}

Also, i get that the array ‘d’ or ‘dist’ stores the distances or shortest path calculated by BFS, but what is the purpose of the ‘q’ array and variables qli and qls ???

Sorry if this seems trivial. I am new to graph based algorithms…

6

@teja_734
qls is used to insert elements into the queue(“q[][]”) whereas qli is used to process them in FIFO order as happens in bfs.