saurabhyadavz's blog

Everything on Mo's Algorithm
By saurabhyadavz, 6 years ago, In English

Possibly, someone called "MO" once used the trick in a local contest, and the name stuck and later got popular. I have never encountered the name "Mo's algorithm" outside of competitive programming.

The technique, or the term "Mo's Algorithm" ("莫隊算法" in Chinese) was originally thought of and popularized by 莫涛 (Mo Tao) and his teammates. It was first used to tackle a problem from 2009 China IOI Camp: 小Z的袜子(hose) — authored by 莫涛 himself. The problem was: given a sequence of integers, for any given interval, calculate the probability of choosing any 2 numbers and the 2 numbers are equal.

Now let's start. I have here compiled the tutorial, some articles written by me, and problems on Mo's algorithm.

Tutorials:

Basic problems:

I have written some basic articles on Mo's algorithm which has been published on Geeksforgeeks.

List of problems:

Edit:

Thanks for the upvotes! It means a lot to me

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

Comments Comments (26)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

great research saurabhyadavz.

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

There must be a bookmark option to save such blogs .

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

Mo is someone's name, writing "Mo's algorithm" makes more sense, no capital O. Where did that come from anyway?

→ Reply
»
6 years ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

I remember a time when I was stuck in a question in Codechef Long Challenge. This blog is really gonna help all.

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

Hey dude, nice blog! Thanks a lot.
Just wondering what made you think the part you have written after edit!

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

For MO's Algo on trees, how to find the LCA of two nodes??

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

The page https://blog.anudeep2011.com/mos-algorithm/ doesn't load for me. Does this work for someone else?

→ Reply
»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

One more problem based on Mo's Algorithm 221D - Little Elephant and Array

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

need an idea on how we can use this to find the distance between the first occurrence and last occurrence of any element in a given range for multiple queries? Any help appreciated!

→ Reply
  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Let's denote the given array as a. Solve for each value in the array separately. You can maintain an array of vectors ind[x] = {i | a[i] = x}. You could've solved it using binary search on ind, but you can also solve it using Mo's algorithm.

    → Reply
  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    With Mo you just keep an array of deques representing indices of the same value. Then when incrementing L you push_front, when incrementing R you push_back, when decrementing L you pop_front and when decrementing R you pop_back.

    → Reply
»
11 months ago, hide # |
 
Vote: I like it +32 Vote: I do not like it

I've never encountered Mo's algorithm outside of "We tried to cut solutions using Mo's algorithm, but unfortunately some ended up passing."

→ Reply
»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Great effort. It is nice to learn about this. I never knew this concept had a name or could be useful anywhere, but sometimes it works. Thank you for the blog and the work.

For anyone facing issues with anudeep2011’s blog not opening, you can try this workaround. It should work: Here you go!!

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

exactly, in Chinese mo's algorithm means "莫队算法" not "莫隊算法"

→ Reply