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

Mo's Algorithm on trees
Автор virus_1010, история, 7 лет назад, По-английски

I did the problem COT2(http://www.spoj.com/problems/COT2/) using Mo's Algorithm on trees....Wondering if a solution faster than n*sqrt(n) exists?

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

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

Good day to you!

Well I've done that with MO and it passed (AC).

For MO, follow this tutorial.

Then for each "move" (i.e. increase/decrease boundary of array) you shall be constant [O(1)]. The same is possible for answers.

A very good manner might be to "rename" all numbers so they will fit to 0<= Ai <= N (just sort them and rename them to indices), so you can simply operate over array.

Next thing is to choose good SQRT. Even though I guess any "normal" would do so, I've solved it with "(222)"

So the final complexity was O(Nsqrt(N)) [i.e. no maps, and no other logarithmic operations during MO]

Good Luck & Have Nice Day!

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

    Sorry for a bit confusing language, I was asking if a solution faster than n*sqrt(n) exists or not.. Sorry for inconvenience :)

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

      Oh I'm sorry (misunderstood that Nsqrt(N) was not enough)

      Well don't know about any :'(

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

Auto comment: topic has been updated by virus_1010 (previous revision, new revision, compare).

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

Am I wrong that you are asking a question related to this problem that is one of problems from a running contest (CodeChef February Challenge 2017)?

→ Ответить