This paper proves that you can, in fact, use randomized union rather than union by rank, and will still get same amortized time complexity.
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.
Facepalmā¦ This problem has so many solutions and Editorialists should describe all them in detailsā¦
Editorialistās solution is what I majorly followed . But I must say, I learnt a lot of terminologies from editorial. Reminds me that I still have a long way to goā¦
@r_64 just my opinion
Although you do explain things in considerable detail, which Iām sure I will appreciate when going through the WEASELSC editorial
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.
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
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 FILLMTR - Editorial - #2 by taran_1407 - editorial - CodeChef Discuss
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
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.