peltorator's blog

Video in English: Everything you need to know about MEX operation
By peltorator, 3 years ago, translation, In English

Hi!

Here goes another video! And now it's in English! This topic is experimental for my channel. I'm talking about everything you need to know about the MEX to solve problems involving this operation. I hope you find this video helpful.

Link to the video

In the future, I'm going to translate my other videos into English. So stay tuned!

You can check out my previous videos on my channel

Contest on mex (and others) is here

Also, there's the Russian version of this video if you speak Russian here

P.S. I'm definitely not fluent in English but I hope you'll understand everything. I see some problems in my English but I'd appreciate it if you said what you found weird in my speech or text.

  • Vote: I like it
  • +266
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

I love these types of explanations with added visual enhancements on it. Keep adding more videos like this!

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Great work!Thanks

→ Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I thought the English was good, I could understand everything that you said. I really liked the video. Thanks!

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

This is top-notch stuff!! Please make more videos like this in English.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I'm gonna translate my old videos to English in the nearest future. Thanks!

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Great stuff! Looking forward to more tutorials!

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

In Mo's algorithm with range mex queries and point updates in $$$O(n^{\frac{5}{3}})$$$, how can you make transitions (add an element, remove an element, find mex) work in $$$O(1)$$$? Don't they require $$$O(\log n)$$$ (using a set)?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    EDIT: lemelisk pointed out that we can use sqrt decomposition instead of a set.

    And also you can check out the pinned comment. There's a $$$O(n \log^2 n)$$$ solution!

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 5   Vote: I like it +27 Vote: I do not like it

    Mex always will be $$$\le n$$$, so instead of set we can use fenwick/segment tree built on array $$$0 \ldots n$$$ — add/remove will be point updates and lifting for find mex. This substitution already improves constant factor by a lot.

    Further, let's replace this trees by sqrt decomposition built on the same array. Then lifting will become $$$O(\sqrt{n})$$$, but update will be $$$O(1)$$$. Since we make only $$$q$$$ liftings and a lot of updates, it will improve our time to $$$O(n^{5/3} + q \sqrt{n})$$$.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

That's great!! One more request : You can add practice problems as well.
EDIT : The link to the contest was already there in the description of the video.
LINK : https://codeforces.com/group/1rv4rhCsHp/contest/321292

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Oh, yeah. I should've added it to this post too.

    P.S. Done.

    → Reply