COOK99 - Problem Discussion

copy paste

Hey guys!!

Lets share our approaches for the problems here while editorials for problems come out (at this moment none n̶o̶t̶ ̶a̶l̶l̶ of them are out)? Got any interesting approach which you cant wait to share? The wait is over :slight_smile:

So, which was your favourite problem? I struggled with Power Tree.

Let the discussion begin!

/copy paste

I really loved Power Tree! Here is my solution for it:

Click to view

First of all the size of PT(X) is 2^X. It can be shown pretty easily based on the recursive formula. As a result, if N isn’t a power of 2 then the answer is -1. Otherwise we can always remove edges to get PT(log(N)).

Notice, that PT(X) can be constructed by taking two PT(X-1)-s and connecting their roots. The direction of the edge between the two roots obviously don’t matter. Because we have a tournament (complete directed graph) we will always find such an edge between the two roots.

We can construct PT(log(N)) using the following algorithm. Let’s have a vector V containing roots of power trees. Initially we will have N PT(0)-s, so V = \{1,2,\ldots,N\}. In each step pair up the elemnts of V and merge the two power trees. We can do this by finding the direction of the edge between the two roots. This will make V contain power trees of degree one higher than previously and the size of V will be halved. Since N is a power of 2 we can make these steps until we are left with only 1 element in V the root of a PT(log(N)). We can store the used edges during the merging, and print out the remaining \frac{N(N-1)}{2}-(N-1) edges as the answer.

Here is my code.

1 Like

You are going to love the editorial even more. :stuck_out_tongue: Make sure to read editorialist’s idea. :wink:

Love the idea of making and merging. You have very well used the fact that given edges are n*(n-1)/2, something which I was leaving behind.

Beautiful implementation problem which I think is not common on CC. Kudos to the author.

1 Like

I had same idea, though i didn’t quite understand what happens with multiple possible power trees with same root, i.e. some of them have mutual children with other, and they can’t merge, how we keep track of that?

Can anyone explain his solution for ADASHOP ? It’s not yet available as editorial.

Thank you.

//