Utkarsh.25dec's blog

Invitation to CodeChef December Long Challenge 2021 (Rated only for Div 3) — 3rd — 13th December
By Utkarsh.25dec, history, 2 years ago, In English

We invite you to participate in CodeChef’s December Long Challenge, this Friday, 3rd December, 3 PM IST onwards.

The contest is open for 10 days, i.e, from 3 — 13 December. Please note, this month’s long challenge will be rated only for Div 3 participants.

Joining me on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

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

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I was the author of Yet Another Tree Problem. Would love to hear feedback on it.

Spoiler
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I just up-solved it now. It was awesome and very informative.

    BTW What is the relatively easier solution?

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

      Let's first see what are the steps required to solve this problem if there is only one query -

      • Sort all edges in increasing weight.
      • For each edge, $$$u,v$$$ and weight $$$w$$$ merge component of $$$u$$$ and component of $$$v$$$ and add w*(no of nodes in the query in the component of u)*(no of nodes in the query in the component of v) to the answer.

      Online virtual tree soln of $$$K$$$ nodes gives us $$$O(K)$$$ edges and then we can process this soln on these nodes.

      The folks who solved offline did the same just that they didn't have to find these O(k) edges.

      Instead of maintaining (no of nodes in the query in each component) what one can do is create a map and then maintain (no of nodes for query in each component). While merging the two components iterate over the one which has a smaller size (this often goes by the name "Small to large trick") and query for no of nodes in another component for the same map. You can refer to this implementation for more details.

      The complexity of this soln would also be $$$O((n+q) \log q)$$$

      You can google out what the "Small to large trick" is. There are way too many tutorials. What's difficult is proving that those loops work in $$$O(n log n)$$$ instead of $$$O(n^2)$$$. Try proving it on your own. If you can then ask again I will link a cf comment which helped me prove that.

      → Reply