FILLMTR - Editorial

This paper proves that you can, in fact, use randomized union rather than union by rank, and will still get same amortized time complexity.

@dpraveen Thanks! Added to the editorial.

Isn’t this the same as editorialist’s solution?
Although I agree that the editorial makes the problem seem way more complex that it is.

1 Like

Facepalm… This problem has so many solutions and Editorialists should describe all them in details…

5 Likes

Editorialist’s solution is what I majorly followed :stuck_out_tongue: . But I must say, I learnt a lot of terminologies from editorial. Reminds me that I still have a long way to go…:slight_smile:

@r_64 just my opinion :stuck_out_tongue:
Although you do explain things in considerable detail, which I’m sure I will appreciate when going through the WEASELSC editorial

1 Like

Well, to say the truth, i didn’t even read the solution line to line but only after seeing the PREREQUISITES, it was apparent to me that the solution discussed here would appear far more complex than it actually is!!!
Which, i believe, is never appreciable.

@meooow my solution resembles the editorial one considerably, but not in finer details as well as complexity as i think.

1 Like

Can you tell some test cases where it may fail.

It didn’t actually work :-(.

You only considered cycles of length <= 3. Try this:

1

5 5

1 2 1

2 3 0

3 4 1

4 5 0

5 1 1

1 Like

PLEASE ELABORATE. thanks

It is already added dear.

The editorial seems actually very long. But its good as it is detailed.
I have summarized the tutorial in my short ~10 min video here : https://www.youtube.com/watch?v=6qWg7-O4Fmg

You can refer this for complete list of video tutorials for SEP17 including WEASTELX.

Yeah, but was not visible at that moment. Fixed now.

I have used the same approach

Explanation https://discuss.codechef.com/questions/109357/fillmtr-editorial/110997

A link to code is given alongwith…

Feel free to ask anything…
Upvote…

Well, You ought to go for vertex 2-coloring instead of bipartite graph testing…

You might like to have a look at my approach with explanation

https://discuss.codechef.com/questions/109357/fillmtr-editorial/110997

Feel free to ask anything…

Please upvote

Well, i dont code in C language, so i can’t understand your code…

But, You might like to have a look at my approach with explanation

https://discuss.codechef.com/questions/109357/fillmtr-editorial/110997

Feel free to ask anything…

Please upvote…

Thanks man! Couldn’t be explained in a more better way. Loved the simplicity of your solution!

Glad it helped :slight_smile:

Done without use of DSU. The main idea is to color the bipartite graph. If color can’t be done then the answer is “no”. Here is the implementation.