Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

virus_1010's blog

Mo's Algorithm on trees
By virus_1010, history, 10 years ago, In English

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?

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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!

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

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

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

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

      Well don't know about any :'(

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

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

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

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

→ Reply