That sounds great! But there is something wrong with the Web Arena. I can't log in. It's always saying: "Login time out. Please try again at later time."

If we do take part in the round using the Web arena and it crashes during the contest , Would we be at fault or would Topcoder make the round unrated for us if we provide them with a valid proof of the problem with the web Arena ?

I've just copied the implementation of Linking-Cutting Tree from my template. Seems everyone who solved it except Petr did the same thing.

SQRT-optimization, as usual :) The code turned out to be very simple.

I have a dynamic programming solution. Let's sort pairs <coordinate; number of stones>

Our state consists of position in the sorted array and additional flag, which can be 0 or 1.

If flag is 0, then we must try to merge current heap and some other consecutive heaps in one big heap.

If flag is 1, then we must try to split current heap and some other consecutive heaps in many heaps of size 1.

It's important to do the second operation only in the beginning or after the operation of the first type, because this guarantees, that we have at least T free cells to the left of our current heap.

Code

There's a greedy solution which results in very simple code (see tourist's for instance).

First sort the input by its coordinates and process the positions from left to right.

For each position we may or may not be able to separate all cats. If we are we should put them as far left as we can (to not bother the following positions). If we aren't able to do so, we should put them as far right as we can. Why? Well, we must pay 1 to put a position with >1cat so let's take as much profit as we can; now, it's a bin where we can just throw all cats for free. Therefore, for each position:

1. Check if the previous position is a free bin (>1 cat there) and we can get there in time. Yes? --> Throw them there :P

2. Check if we can separate them. Yes? --> Put them as far left as you can without touching the previous position and satisfying the time constraints.

3. We aren't able to separate them :( --> ++ans and put a free bin as far right as you can

I've solved it with DP.

Each state is represented by the current amount and the maximum power of 2 you have available. So you have dp[amount][maxpow].

At each state you can explore three posibilities:

• Ignore the coins with value 2^maxpow and go to rec(n, maxpow - 1)

• Take one coin of the kind 2^maxpow and go to rec(n - 2^maxpow, maxpow - 1)

• Take both coins of the kind 2^maxpow and go to rec(n - 2(2^maxpow), maxpow - 1)

The main problem you can find is that N can be so large, so you need to take into account two things:

• You cannot use a normal matrix since N can be 10¹². I've used a map with pair<long long, int> as key to store the states.

• If you iterate through all states just doing what I mentioned above you will find that all N numbers will be visited multiple times, so you will have a time and memory problem. The search can be pruned if even with taking all available coins you cannot get the current amount.For that, you need to compare the current amount you have with 2(2⁰) + 2(2¹) + .. + 2(2^maxpow) = 2^{maxpow + 2} - 2, which can be done quickly.

Yes, there was a problem with the tests. They have already been fixed and, according to this thread everything should be ok now.

It hasn't affected the round because the checkData (the validator for this problem) and the statement are correct.