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

Автор _Enigma__, история, 2 года назад, По-английски

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
  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

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

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

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

    Luckily, the solution complexity is better here.

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

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