PROBLEM LINK:Author: Vasia Antoniuk DIFFICULTY:EASY PREREQUISITES:unionfind algorithms, disjointset forests, offline algorithms PROBLEM:Given an N × M grid, you need to support Q queries of the following four kinds:
QUICK EXPLANATION:
EXPLANATION:Naïve solutionFirst 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:
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. UnionfindIf you are familiar with unionfind 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 unionfind, 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 unionfind 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 unionfind 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 unionfind 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 graphsFinally, 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:
This question is marked "community wiki".
asked 15 Mar '15, 23:23

My solution was actually based on the presentation linked in the editorial. It did pass the tests with the slowest case taking 0.56s answered 20 Mar '15, 11:03

Processing the queries in reverse ... That was the catch. Damn . answered 17 Mar '15, 13:49

Processing the queries in reverse ... That was the catch. Damn . answered 17 Mar '15, 13:49

Hi , I am a noob.. So , apologizing beforehand for silly question that I am going to ask. In problem setter's solution Thanks in advance. answered 01 May '15, 22:50

Answer is hidden as author is suspended. Click here to view.
answered 02 May '15, 12:00

Answer is hidden as author is suspended. Click here to view.
answered 02 May '15, 12:00

I implemented the same as the Tester did, but I am getting TLE in subtask 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 answered 09 May '15, 18:06
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,n1) fo(j,m){ if(!bd[i][j]) Union(p,im+j,(i+1)m+j);} fo(i,n) fo(j,m1){ if(!br[i][j]) Union(p,im+j,im+j+1);} to fo(i,n) fo(j,m1){ if(!br[i][j]) Union(p,im+j,im+j+1);} fo(i,n1) fo(j,m){ if(!bd[i][j]) Union(p,im+j,(i+1)m+j);} Solved the TLE.
(09 May '15, 18:25)

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