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

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

here's example problems.

https://www.codechef.com/START21B/problems/MSUB121

https://atcoder.jp/contests/abc219/tasks/abc219_g

is there any tag or name for n*sqrt(n) problems? or are they just ad-hoc? i can't even approach to these type of problems during the contest. i wanna practice but i don't know what to search.

Q : is there any tag or category for type of problems above? or any tutorial blogs for those

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

It's a type of sqrt decomposition technique, generally we can solve such problems by taking 2 cases (heavy and light), for eg. if we classify vertices in a graph based on it's degree we can see that as the number of edges is bounded by M (say), we know that there won't be many (at most sqrt(M)) heavy vertices with degree more than or equal to sqrt(M), and we can use brute force for the light vertices. You can watch the tutorial video by Errichto.