Zeardoe's blog

What is "The Method of Four Russians"?
By Zeardoe, history, 3 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

»
3 years ago, # |
  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
  • »
    »
    3 years ago, # ^ |
      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
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

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

    And CCF says this algorithm is $$$\Theta(N+Q)$$$ , but OI-wiki says that it should be $$$\Theta(N\log\log N+Q)$$$ ! I think CCF is wrong.

    UPD:I didn't see clearly. It should be $$$\Theta(N+Q)$$$

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

      That's a $$$+1/-1$$$ RMQ problem because the depths of adjacent nodes in the euler sequence only can be differ by one. So this algorithm is $$$\Theta (N+Q)$$$.

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

        Oh yes I didn't see that clearly.

        Sorry!

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

    Great, is this blog from you? That's nice.

    → Reply
»
3 years ago, # |
  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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Sure. I even don't know what the Cartesian tree is about.

    → Reply
»
3 years ago, # |
  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