The problem is to find the number of standing hamsters. If it is less than half, we should make the required number of hamsters standing. Otherwise we should make some hamsters sitting.
We can sort all the cities by their distance to the Tomsk city di. After that we are to find the smallest index t for which the total population p0 + p1 + ... + pt > = 106. In such case the answer is dt. We can sort all cities in O(NlogN) and find the value of t in O(N). Limits for N allow O(N2) sorting or any other O(N2) solution.
Consider the following formulas:
Let . Lets compute the following function for each i (0 ≤ i ≤ n). One can do it in O(n) using .
Lets transform ci:
That means, if n / i is odd, , otherwise — . ci can be computed in O(1), that's why the complexity of the whole solution — O(n).
Due to the time limit for Java some of O(N4) solution got Accepted. The authors solution has complexity O(N3·logN). The main idea is to fix the top-border and bottom-border. Then, using some abstract data type, for each right-border we can find the most suitable left-border in O(logN) time. For example we can use set in C++ and its method lower_bound. For better understanding lets have a look at the following figure:
For such rectangle we fix the upper-border as row number 2 and bottom-border as row number 5. Also, we fix right-border as column number 6, and now we are to find some left-border. Now we can split the time value for any rectangle for two summands. One of them depends only on left-border and another one — on the right-border.
With the blue color the summand that depends only on the right-border is highlighted. With the red and yellow color — the other summand is highlighted. The red-colored value should be subtracted and the yellow-colored should be added. For any blue right-border's value we are to find the closest red-yellow left-border. That is the problem to be solved with the help of STL Set or any other similar abstract data type.
A classical DP-problem on finding expected number.
Lets define some function F(S) for some state — the expected number of minutes to finish the game from this state. For each color we can compute the probability of showing this color by the simple formula , where c — the number of dice's faces of this color. Now we are to find the probability PL to stay in this state for the next minutes. That is the probabilty of showing black color plus the probabilities of showing colors with no blocks of that color to be removed from the tower. Now we can find the value via the following formula:
The only problem is to find how to encode the state. To reduce the number of states we can assume that there is only 18 different type of levels, but not 27. For better time-performance it is better to use hashing. The solution for this problem requires good understanding of DP and quite good implementing skills.