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

How to solve this graph problem from codechef July cook off?
Автор aditya_sheth, история, 5 лет назад, По-английски

Problem. I checked various solutions. I could see DSU and Dynamic programming in most of them. Any hint or full solution would be helpful.

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

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

Here's a very similar problem on an Educational round. I would recommend understanding the solution based on centroid decomposition (even though it isn't strictly required here), since it is much more general and can solve a variety of problems of this kind, i.e., obtaining information about all paths in a tree.

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

    It's actually the SAME problem. Shame on the codechef author :(

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      Funnily enough, I actually ACed the Educational Round problem before the CodeChef contest, but kept TLEing on the CodeChef version of the problem (I never thought to check my old CF submissions during contest :( ).

      The decrease of the TL from 4.5 seconds to 3.0 seconds in addition to there being 10 testcases v.s. 1 testcase in an input is highly annoying, as it required several relatively hacky optimizations (e.g. precomputing the GCD >= 1 case) to make a modification of the Educational Round solution pass (and still doesn't make it qualify as a unique problem).

      /endsalt

      Is there a better complexity solution that CodeChef expected?

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
$$$n = \sum_{d|n} \phi(d)$$$
→ Ответить