TWOFL - Editorial

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.

My submission is at CodeChef: Practical coding for everyone

Corrected.

@smartnj, you are correct. My implementation would give TLE, because I traverse each component the number of elements it has in it. Thus the test case provided above have similar idea where a lot of 1's are clustered close to each other.