Блог пользователя Zeardoe

What is "The Method of Four Russians"?
Автор Zeardoe, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    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)$$$

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      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)$$$.

      → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

→ Ответить