aditya_sheth's blog

How to solve this graph problem from codechef July cook off?
By aditya_sheth, history, 5 years ago, In English

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

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

»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      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?

      → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it
$$$n = \sum_{d|n} \phi(d)$$$
→ Reply