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

what is square-order tree DP?
Автор Sanat, история, 5 месяцев назад, По-английски

I was practising a question from Atcoder abc287 f, while reading the editorial for this problem, I encountered something called "square-order tree DP" due to it, by doing a process, which seems O(n^3) at first glance is actually O(n^2) they had linked a blog about it, but it is in Japanese, and I wasn't able to find a relevant resource related to it, in English, if someone, can help me find a relevant resource, or explain why the process is O(n^2) it would be very helpful.

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

»
5 месяцев назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

"Sqrt Tree — Algorithms for Competitive Programming" https://cp-algorithms.com/data_structures/sqrt-tree.html This may help, although I understand nothing from this but I get it that it square roots the number of operations or something like that. Check it out

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    thanks for your effort, but it is unrelated to what I asked

    → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

One of the first problems most people saw with this technique is probably https://mirror.codeforces.com/contest/815/problem/C. Also, https://usaco.guide/adv/comb-sub has a brief explanation and a set of problems with using this.

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Thanks!!! I read the reason, it is indeed very elegant why it is O(n^2), no heavy calculations and only simple reasoning to arrive at it

    → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

If I understand it correctly, then an English resource is here (section 7).

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Thanks!!!, it is very useful, I was looking for something like this, nice explanation, I also found some more interesting things related to it in comments of your blog.

    → Ответить