TWOFL - Editorial

I did not use BFS/DFS - just DSU for the set of all the cells in the field along with subset sizes. First, join all same type pairs of neighbors and save a copy of the resulting data. Then do the following - break the set of all the (unordered) pairs of different neighbor types into subsets in such a way that no two pairs in a subset have a common type. For each subset maintain a hash set of all the types in it and a list of index pairs of neighbors. Maintain a hash map mapping a pair of types into a subset. For each pair of different type neighbors add their indices to the corresponding list. The first time a pair of types is encountered find a subset that contains neither of the two types. If no such subset exists create a new one.

For each of the resulting lists perform union of all the pairs in it restoring to the saved state before processing each list. Maintain the maximal size when performing unions.

Here is python (PyPy) solution.

UPDATE.

This solution got AC, but it will be slow for a case when there is a type with a large number of different neighbor types. Instead we can simply maintain a hash map of separate lists for each pair of neighbor types, and at each DSU iteration restore only those elements that have been changed, as described in the editorial.

Solution.

1 Like

I used just dfs and it fetched me 80 points…i was getting tle in one of the test cases of 2nd subtask.
In dfs , what i did was…i just fixed one number and counted the connecting components of all other numbers ansd the fixed number connected to it which are greater (maintaining each ones count in a map) …thus i was able to count each pair’s connected component in just one dfs run . Also i have used many optimisations to prevent tles … but still i was getting one tle .
However , finally using some conditions (which i thought could have been the reason for the tle )…i was able to get 100 points (though i am not satisfied by my approach).
But still i want to know why i was getting tle in the 2nd subtask’s 3rd test case …if anyone could help :slight_smile:

Here is my solution .

1 Like

I formed the components as in the author’s solution and then used the edge base graph traversal instead of dsu.The edges here are the edges of the component graph.I feel in this way we can guarantee the bound to be O(8*N*M) what was tried to achieve in the editorialist’s solution.

2 Likes

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

I need help. Actually I don’t know it is due to StackOverflow and I can’t resist to avoid it.

@likecs: I think there should be a correction in the pseudo code given for the first subtask. I think it should be:

if vis[i][j] or (a[i][j] != c1 and a[i][j] != c2):

Correct me if I’m wrong. But I think this is correct.

3 Likes

Can anyone please explain how did we calculate the time complexity of “DSU + sorting map” solution since it has loops and we have to reset values evertime after we perform union find on components?

TIA!

for (auto &vec : ed) {
vector < int > changed;
for (auto &it : vec.second) {
int x = it.first, y = it.second;
changed.push_back(x);
changed.push_back(y);
int xx = getWho(x), yy = getWho(y);
if (xx == yy) {
continue;
}
if (rand() & 1) {
swap(xx, yy);
}
who[xx] = yy;
sz[yy] += sz[xx];
ans = max(ans, sz[yy]);
}
for (auto &it : changed) {
sz[it] = sizes[it];
who[it] = it;
}
}

**can someone explain how this DSU part works in author’s solution??

In short , what is use of getWho() function and who[] array??**

Being new to competitive programming, and knowing nothing about the methods described here (or at least not by the abbreviations used), I developed a completely different method based on my previous experience of flood-filling. This scored me 100 points, completing in 1.66 seconds. If anyone is interested please see my submitted solution (in C#), or ask me to explain it further here.

1 Like

@codeislifenluv: Have a look here: Need some help in TWOFL - general - CodeChef Discuss

I think there’s another way to look at the question , I’ve traversed the matrix blocks (of two unique numbers) only once , I don’t really know bfs or dfs so here’s a simple approach .
Here’s my solution link.

Example, in a matrix

1 2 3
2 4 5

The traversal is like :

1-2
|
2

2-3

2
|
4

3
|
5

2-4

4-5

There’s only repeated traversal of those which form more then one block.

For single number blocks I’ve defined a simple separate function.

P.S. - It’s my first post so please excuse if my approach is not clear to you guys.

I didn’t do anything special to handle such a case, and when I tested my solution on a test case constructed like this with N and M both in the order of 1000, it ran for more than two minutes and I had to quit it eventually… So I’m pretty sure my solution is N^2*M^2. Yet, it passed with 100 points in the contest which may mean the test cases were weak?

agree… I found it medium…

Update: You are correct @akamoha. The test cases were weak. Thanks for a similar test case. Have updated the editorial with a warning too.

can you share the input file ? (like on a G drive or dropbox)

This pointed out in the editorial. Please check again.

ya, seen that, thank you!!

I will have to ask the Codechef team and author to share the counter test case.

Union-find algorithm works in amortised O(n) only if it is implemented by “Rank” algorithm, i.e. merging smaller sets to larger ones. But in practice, even random merging works fine and it is tough to generate a test case against it.

2 Likes

i converted editorialist’s solution to java Code… but in java same code is giving TLE… Here is link:- CodeChef: Practical coding for everyone

You may want to check out my code xD