MTRWY - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vasia Antoniuk
Tester: Hiroto Sekido
Editorialist: Kevin Atienza

DIFFICULTY:

EASY

PREREQUISITES:

union-find algorithms, disjoint-set forests, offline algorithms

PROBLEM:

Given an N × M grid, you need to support Q queries of the following four kinds:

  • 1 x y - build the wall between cells (x, y) and (x, y+1). If there is already exist a wall between them, this query is ignored.
  • 2 x y - build the wall between cells (x, y) and (x+1, y). If there is already exist a wall between them, this query is ignored.
  • 3 x1 y1 x2 y2 - check if cells (x1, y1) and (x2, y2) are connected.
  • 4 - You must answer the size of the largest connected component. A connected component is a set of cells such that every pair of cells in it are connected. The size of a connected component is a number of the cells in it.

QUICK EXPLANATION:

  • Collect all Q queries in an array.
  • Uniquify the 1 x y and 2 x y queries, i.e. only keep the first occurrence of a given 1 x y/2 x y.
  • Process the remaining queries in reverse, starting with a grid with some walls already existing, and then removing them and merging connected components. Use a really fast union-find structure for this, such as disjoint-set forests. Also, keep track of the sizes of each component, and the largest among them.
  • The sum of the results is the answer.

EXPLANATION:

Naïve solution

First of all, one can simply implement the given queries in a straightforward way. We only need to keep track of which walls have been added. Let’s see how they can be done:

  • 1 x y and 2 x y - simply set a flag that there is a wall between two given cells.
  • 3 x1 y1 x2 y2 - Start a breadth-first search/depth-first search from (x1,y1), and then check whether the cell (x2,y2) is visited or not.
  • 4 - Start a breadth-first search/depth-first search from all components, and output the largest one.

Type 1 and 2 queries can be done in O(1) time each, while type 3 and 4 queries the solution may takes O(NM) time in the worst case. Therefore, the solution runs in O(QNM) time overall. So a reasonable implementation can pass the first subtask, but will fail the others.

Union-find

If you are familiar with union-find algorithms, you might notice that this is somehow its reverse problem, where instead of adding edges, you remove them. There are popular and fast ways of doing implementing union-find, but it seems that there is no similar way to solve the reverse problem.

This problem graphs is called decremental connectivity, and common techniques for solving it efficiency is very complex, and might not even pass the tight time limits of this problem. It would really, really be nice if we can solve the reverse problem.

In fact, why not simply reverse the queries? There’s nothing stopping us from doing so, because all the queries are known in advance! The idea is simply to add all the walls from the queries, and then reverse the queries, but then we proceed removing walls instead of adding them. Now, we can use efficient union-find algorithms!

We will need to describe the details. First, the type 3 queries simply involve two find queries and checking whether they are equal. For type 4 queries, we will need to be able to access the size of the largest connected component so far. To do so, we need to augment the union-find structure to keep track of the sizes of each component. This is simple: you really just need to store the size of the component on each representative, and when merging two components, simply update this size as the sum of the sizes of the components to be combined. This can be done with no significant cost to the running time. Then to find the largest one, we simply need one variable to keep track of it, and update it when we merge components. This works because the largest component size is nondecreasing. (As a side note, suppose we were not processing the queries in reverse order, but are proceeding with decremental connectivity. We can’t use a single variable any more. Instead, we will need a priority queue containing the sizes of all components, and update it whenever we split a component.)

Finally, type 1 and 2 queries are simply union operations. However, remember that there can be duplicate 1 x y/2 x y queries! In those cases, only the first occurrence of each such distinct query is important, because the others are no ops. Therefore, find the duplicate queries and ignore them during the reverse processing. This can be done in O(NM) time at the beginning.

We can now see that the whole algorithm has an O(NM) preprocessing step, and O(\alpha(NM)) time per query, where \alpha is the inverse Ackermann function, so the whole algorithm runs in O(NM + Q\alpha(NM)) time. The \alpha comes from implementing union-find using disjoint set forests, with path compression and union by rank optimizations. Note that in this problem, both of these implementations are recommended, because omitting one will slow the query time to O(\log (MN)), while omitting both will slow it further to O(NM) in the worst case (not better than before!). Remember that the time limit is strict, so even O(\log (MN))-time queries might still take too long!

Additional read: decremental connectivity in planar graphs

Finally, we refer the reader to continue reading about decremental connectivity. For example, this link contains an efficient algorithm to handle decremental connectivity in the case of planar graphs. It is a really nice read, so we suggest you learn it!

Time Complexity:

O(NM+Q\cdot \alpha(NM)), where \alpha is the inverse Ackermann function

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

4 Likes

Processing the queries in reverse … That was the catch. Damn .

Processing the queries in reverse … That was the catch. Damn .

Processing the queries in reverse … That was the catch. Damn .

My solution was actually based on the presentation linked in the editorial. It did pass the tests with the slowest case taking 0.56s

http://www.codechef.com/viewsolution/6524341

2 Likes

Wait, am I missing something…?

It says above that

The idea is simply to add all the walls,
and then reverse the queries, but then we
proceed removing walls instead of adding
them

So initially, the size of the largest connected component will be 1 (because all walls exist), right?
Supposing there’s only one query of type 4, won’t this give a wrong answer (correct one being N*M)?

Help!?

We can say that all walls which weren’t added during queries were actually added after that. So you take field with all walls presented, delete all walls which aren’t presented in queries (and right now you have state which was reached after last query), and then start solving queries in reversed order, as editorial describes.

Hi , I am a noob… So , apologizing beforehand for silly question that I am going to ask.

In problem setter’s solution (x-1)*m + y index is taken while computing bfs . Can anyone please explain why it is done ?

Thanks in advance.

Terima kasih dan salam kenal.
Link

Link

Terima kasih dan salam kenal.
codechef Link

code Link

Great job!

I implemented the same as the Tester did, but I am getting TLE in sub-task 2 and 14. Please let me know where is the difference in the code of Tester and mine.
Mine : http://www.codechef.com/viewsolution/6865972
Tester : http://www.codechef.com/viewsolution/6865851

http://www.codechef.com/viewsolution/6866324 (100pts) and http://www.codechef.com/viewsolution/6865684 (15pts;TLE) differ just by two statements interchanged, and the TLE goes away.
Changing

fo(i,n-1) fo(j,m){ if(!bd[i][j]) Union(p,i*m+j,(i+1)*m+j);}

fo(i,n) fo(j,m-1){ if(!br[i][j]) Union(p,im+j,im+j+1);}

to

fo(i,n) fo(j,m-1){ if(!br[i][j]) Union(p,im+j,im+j+1);}

fo(i,n-1) fo(j,m){ if(!bd[i][j]) Union(p,i*m+j,(i+1)*m+j);}

Solved the TLE.

Me too getting TLE in sub-task 2 & 14 dunno where going wrong…

https://www.codechef.com/viewsolution/18876436

used BFS instead of recursive DFS and got AC for 100 points…

https://www.codechef.com/viewsolution/18876465