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?
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?
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 145 |
Name |
---|
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!
Sorry for a bit confusing language, I was asking if a solution faster than n*sqrt(n) exists or not.. Sorry for inconvenience :)
Oh I'm sorry (misunderstood that Nsqrt(N) was not enough)
Well don't know about any :'(
Auto comment: topic has been updated by virus_1010 (previous revision, new revision, compare).
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)?