Wednesday, October 8, 2008 Match summaryTCHS 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 ProblemsCorruptMagesUsed as: Division One  Level One:
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 ith 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. EquilibriumPointsUsed as: Division One  Level Two:
In order to solve the problem, let's first identify N1 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[N1]], 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 < N1. Let P be a point between these two points and its coordinate be x_{0}. Denote the total value of gravitational forces directed to the left from P as L(x_{0}) and the total value of gravitational forces directed to the right from P as R(x_{0}). In order for P to be an equilibrium point we should have L(x_{0}) = R(x_{0}) or, equivalently, L(x_{0})  R(x_{0}) = 0. Let's investigate the behaviour of functions L and R. When x_{0} 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_{0}) is a monotonically decreasing function, and similarly R(x_{0}) is a monotonically increasing function. When x_{0} tends to x_{i} from the right, the distance between P and the ith point tends to +0 and therefore L(x_{0}) tends to positive infinity. The same argument shows that R(x_{0}) tends to positive infinity when x_{0} tends to x_{i+1} from the left. If we sum up all these properties, we'll see that L(x_{0})  R(x_{0}) is a monotonically decreasing function, which tends to positive infinity when x_{0} tends to x_{i}+0 and tends to negative infinity when x_{0} tends to x_{i+1}0. This means that equation L(x_{0})  R(x_{0}) = 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 1e9), but not after the value of L(x_{0})  R(x_{0}) becomes less than 1e9. 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. AuxanometerUsed as: Division One  Level Three:
The natural question one could ask after reading a problem statement is: «How many numbers in range [1...10^9] form a nondecreasing 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 nondecreasing 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[n1][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 nondecreasing 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. 
