Match Editorials

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

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.

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 x₀. Denote the total value of gravitational forces directed to the left from P as L(x₀) and the total value of gravitational forces directed to the right from P as R(x₀). In order for P to be an equilibrium point we should have L(x₀) = R(x₀) or, equivalently, L(x₀) - R(x₀) = 0.

Let's investigate the behaviour of functions L and R. When x₀ 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(x₀) is a monotonically decreasing function, and similarly R(x₀) is a monotonically increasing function. When x₀ tends to x_i from the right, the distance between P and the i-th point tends to +0 and therefore L(x₀) tends to positive infinity. The same argument shows that R(x₀) tends to positive infinity when x₀ tends to x_i+1 from the left.

If we sum up all these properties, we'll see that L(x₀) - R(x₀) is a monotonically decreasing function, which tends to positive infinity when x₀ tends to x_i+0 and tends to negative infinity when x₀ tends to x_i+1-0. This means that equation L(x₀) - R(x₀) = 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(x₀) - R(x₀)| 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.

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 k ≥ s. 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.