_Enigma__'s blog

By _Enigma__, history, 3 years ago, In English

A. Equal Distribution


Solution

B. Smallest String


Solution

C. Xor Zero


Hint 1
Hint 2
Solution

D. Counting Stars


Hint 1
Hint 2
Solution

E. The Antique Store


Hint 1
Hint 2
Hint 3
Solution

F. Triangles on Lattice


Solution
  • Vote: I like it
  • +58
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I see many people (more than half AC submissions) passed E with $$$O(N\sqrt{N}logN)$$$ :(

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    That is unfortunate. Even more so because I do have an AC on this one :(

    Luckily, the solution complexity is better here.

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

I had a different $$$O(Q \sqrt{N})$$$ solution for The Antique Store. I noticed the need for point update and range sum data structure along with Mo's algorithm. But since Mo's can have $$$O(Q \sqrt{N})$$$ updates, a data structure supporting update in $$$O(\log{N})$$$ won't be enough.

This suggests a need for a data structure which has faster updates but slightly slower queries. So, I used square root decomposition (on the array, not Mo's) for point update and range sum as updates are $$$O(1)$$$ and queries are $$$O(\sqrt{N})$$$. Since there are only $$$O(Q)$$$ queries, overall complexity is $$$O(Q \sqrt{N})$$$.

Code