22

Educational Codeforces Round 119 Editorial

 2 years ago
source link: http://codeforces.com/blog/entry/98061
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Educational Codeforces Round 119 Editorial

1620A - Equal or Not Equal

Idea: BledDest

Tutorial
Solution (Neon)

1620B - Triangles on a Rectangle

Idea: BledDest

Tutorial
Solution (awoo)

1620C - BA-String

Idea: BledDest

Tutorial
Solution (awoo)

1620D - Exact Change

Idea: adedalic

Tutorial
Solution (adedalic)

1620E - Replace the Numbers

Idea: Neon

Tutorial
Solution 1 (Neon)
Solution 2 (Neon)

1620F - Bipartite Array

Idea: BledDest and Neon

Tutorial
Solution 1 (Neon)
Solution 2 (Neon)

1620G - Subsequences Galore

Idea: BledDest

Tutorial
Solution (BledDest)

22 hours ago, # |

In my opinion, I think that the positions of E and D should have been swapped.

22 hours ago, # |

In the problem E-Replace the Number, alternate solution mentions the small to large method. Can anyone explain how it has complexity of O(n log n)? Any resource added would also be helpful.

  • 22 hours ago, # ^ |

    With small to large method you want to take the smaller set and add it the larger one. When you do this if you had an element in the smaller set, now it is, for sure, in a set with size at least twice the one beforehand. So you can move each element at most log(n) times since the set can't become more than the number of elements.

    Here in the task you can keep them in vectors and if needed just swap the vectors after adding the smaller one to the larger.

    Hope that explains it.

  • 21 hour(s) ago, # ^ |

    When you merge a smaller set into a larger set, the size of the generated set is at least twice of the smaller one. So the set-size will exceed N in no more than log(N) merges.

  • 17 hours ago, # ^ |

    ← Rev. 2 →  

    0

    So the worst came comes when both x and y have same number of occurrences which comes at 2, 4, 8, 16... . This means at each power of 2 indexes we will merge and total merge complexity will be O(n) So at each log(n) we do O(n) operation which makes it O(nlog(n)).


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK