Zeardoe's blog

What is "The Method of Four Russians"?
By Zeardoe, history, 5 years ago, In English

In Chinese CSP-S1 today morning, there was a question to use "The Method of Four Russians" to solve RMQ problem. Can anyone do me a favor to teach me what it is? Thank you!

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

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

You don't need to learn it now.CCF just had water in it's mind.Don't pay too much attention on that F*** problem

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

    Haha. But the contest is good, I think. I've found that even in Codeforces this Russian website there are few explanations about TMoFR.

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

You can see that here. (Maybe unfriendly to people unfamiliar to Chinese

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

In a word, I think it's quite not proper to put an Russian alorgithm in a Chinese exam :D

Maybe "The Method of some numbers of Chinese" should be put in.

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

One of the things you DON'T need to know.

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

The Method of Four Russians is a very general technnique, and not just limited to the RMQ. It roughly has to do with "precomputing" the answers for small parts of the problems, and use some other more general structure for the larger parts of the problem.

For instance, in RMQ with The Method of Four Russians, you essentially try to make a sparse table on the range-minima of blocks of small size, and precompute the answers for all small blocks. However, just doing a brute force doesn't work for all small blocks, so rather than solving this for the original problem, we try to find the position of the minimum in equivalence classes of small blocks (which are $$$C_s$$$ in number, where $$$s$$$ is the size of blocks, and $$$C_s$$$ is the $$$s$$$-th Catalan number), which are few in number, and recognize which block each small array corresponds to.

For a more detailed explanation, you can consider reading https://web.stanford.edu/class/cs166/lectures/01/Small01.pdf

→ Reply