p__ce1052's blog

Is there any name for this kind of method?

By p__ce1052, history, 3 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

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.

→ Reply