Get Time
high_school  Match Editorials
Wednesday, October 8, 2008

Match summary

TCHS SRM 59 turned out to be both rather easy and quite unpredictable. The winner was bbi5291, who managed to solve all 3 problems in half an hour. Two former green coders 7ania7 and litwin also showed excellent performance and grabbed second and third place, respectively.

The Problems

CorruptMages rate it discuss it
Used as: Division One - Level One:
Value 250
Submission Rate 113 / 119 (94.96%)
Success Rate 97 / 113 (85.84%)
High Score Zrinka for 247.83 points (2 mins 40 secs)
Average Score 221.74 (for 97 correct submissions)

This is a rather standard problem which can be solved using the greedy approach: we should give bribes to the mages with the largest power. Note, that paying the i-th mage decreases the number of active spells by power[i]+1 (or less, if the number of active spells is small already). Now it is clear that the best group of size K is the group containing K most powerful mages. So we should find the minimal K for which the total power of K most powerful mages plus K is not less than the total number of spells. The easiest way to achieve this is to sort the mages by their powers and start paying them one by one, starting from the most powerful mage, until their total power is big enough. See Kankuro's solution for exact implementation of this approach.

EquilibriumPoints rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 56 / 119 (47.06%)
Success Rate 31 / 56 (55.36%)
High Score gnocuil for 467.36 points (7 mins 36 secs)
Average Score 345.10 (for 31 correct submissions)

In order to solve the problem, let's first identify N-1 segments on which each of the equilibrium points is located. It's not hard to see that no equilibrium point P is located to the left of all input points, because all input points would force such a point P to the right and no points would force it to the left. By similar reason, no equilibrium point is located to the right of all input points. This means, all equilibrium points are located within the segment [x[0], x[N-1]], where N is the number of elements in x.

Note that input points are sorted in ascending order of their coordinates and this is actually a small hint. Consider some two adjacent points x[i] and x[i+1], 0 ≤ i < N-1. Let P be a point between these two points and its coordinate be x0. Denote the total value of gravitational forces directed to the left from P as L(x0) and the total value of gravitational forces directed to the right from P as R(x0). In order for P to be an equilibrium point we should have L(x0) = R(x0) or, equivalently, L(x0) - R(x0) = 0.

Let's investigate the behaviour of functions L and R. When x0 is increased, the distances between P and each of the input points located to the left of P are increased and therefore all gravitational forces between P and these points are decreased. Therefore L(x0) is a monotonically decreasing function, and similarly R(x0) is a monotonically increasing function. When x0 tends to xi from the right, the distance between P and the i-th point tends to +0 and therefore L(x0) tends to positive infinity. The same argument shows that R(x0) tends to positive infinity when x0 tends to xi+1 from the left.

If we sum up all these properties, we'll see that L(x0) - R(x0) is a monotonically decreasing function, which tends to positive infinity when x0 tends to xi+0 and tends to negative infinity when x0 tends to xi+1-0. This means that equation L(x0) - R(x0) = 0 has exactly one root on the segment [x[i], x[i+1]], i.e. there's exactly one equilibrium point between each pair of adjacent input points. As usual in cases when we should find the root of a monotonically increasing/decreasing function, binary search can be used to do the job. If you're not familiar with binary search, this tutorial will surely help you to fill in this gap.

The most popular error made by contestants was early search termination. Note that you can safely terminate the search either after sufficiently large number of iterations (for example, 100) or when the searched segment length becomes sufficiently small (i.e. less than 1e-9), but not after the value of |L(x0) - R(x0)| becomes less than 1e-9. For more information regarding this, please check the following thread.

For clean implementation of the described approach, please check the fastest correct submission on this problem by JongMan.

Auxanometer rate it discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 41 / 119 (34.45%)
Success Rate 20 / 41 (48.78%)
High Score Kankuro for 912.51 points (8 mins 58 secs)
Average Score 613.08 (for 20 correct submissions)

The natural question one could ask after reading a problem statement is: «How many numbers in range [1...10^9] form a non-decreasing sequence of digits?» The answer is suprisingly small: there are only 48619 such numbers. The competitors could either believe in this fact and start coding or calculate this number to be sure. For example, it can be obtained using the following dynamic programming approach. Let DP[n][s] be the number of non-decreasing digit sequences of length n with the first digit s. Then DP[1][1] = … = DP[1][9] = 1. DP[n][s] can be calculated as the sum of DP[n-1][k] for all ks. The required number is the sum of all DP[n][s] for 1 ≤ n, s ≤ 9 (the number must contain up to 9 digits and start with any digit except zero).

So, the quantity of «good» numbers is small enough and we can generate all of them, for example by the recursive procedure which takes number n with last digit d and tries to append it with all digits not less than d. Now we can calculate the answer for the problem during the recursion: check if the current good number lies on the right scale, calculate the corresponding number on the left scale and check if their concatenation forms a non-decreasing digit sequence. See bbi5291's solution as a reference to this approach. Another way is to generate all «good» numbers and put them into set. Now for all «good» numbers on the left scale we should check if the corresponding number on the right scale also lies in the set and if the last digit of the left number is not greater than the first digit of the right number. See litwin's short and elegant implementation of this approach.

By Alexus
TopCoder Member