FILLMTR - Editorial

editorial
, , , ,
21

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

22

@dpraveen Thanks! Added to the editorial.

23

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
24

Facepalmā€¦ This problem has so many solutions and Editorialists should describe all them in detailsā€¦

5 Likes
25

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:

26

@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
27

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
28

Can you tell some test cases where it may fail.

29

It didnā€™t actually work :-(.

30

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
31

PLEASE ELABORATE. thanks

32

It is already added dear.

33

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.

34

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

35

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ā€¦

36

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

37

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ā€¦

38

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

39

Glad it helped :slight_smile:

40

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.