TWOFL - Editorial

@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

You can optimise the code. Obvious things are reducing function calls, replacing Math.max() etc. by ternary operator. Also, remember that usually, constant associated with hashing is high. You can have a look at my code for reference.

1 Like

I was talking about akamoha’s test case, the one which is mentioned in the comment above.

We perform one DSU per edge and reset only those values that have been affected when processing a set of edges.

Yeah, you are right.