Match Editorials

Match summary

This match gathered 81 coders, 15 of them were newcomers. The contestants faced a fairly straightforward easy problem, although its success rate rather far from 100%. The medium and hard problems were somewhat harder and as an effect of this, the most of submissions of them were successfully challenged or failed system tests.

Zuza took the lead due to his very solid performance on all the problems and 6 successful challenges. ahyangyi got the second place with all three problems solved and being boosted up by 5 successful challenges. Having "only" 3 successful and 2 unsuccessful challenges, the would-be winner neal_wu finished third.

The Problems

Value	250
Submission Rate	61 / 73 (83.56%)
Success Rate	47 / 61 (77.05%)
High Score	mirosuaf for 249.06 points (1 mins 45 secs)
Average Score	195.36 (for 47 correct submissions)

Because of the rather low constraints, this problem can be solved using brute force. Just do what the problem statement asks you to do. Please, check this solution of RuslanSM for a clean implementation. One interesting thing about this problem is during each step of the transformation process, you can safely choose any pair with the minimal difference and result will never differ from the one where you always choose the pair with the minimal sum. I won't go deeper into the details saying that this can be proved by induction.

Value	500
Submission Rate	48 / 73 (65.75%)
Success Rate	19 / 48 (39.58%)
High Score	fpavetic for 487.02 points (4 mins 39 secs)
Average Score	384.56 (for 19 correct submissions)

Let's notice that we never need to take more than four items. So, if we have n items then the total number of variants we need to consider in the worst case is C(n,1) + C(n,2) + C(n,3) + C(n,4). Which is only 251175 for n = 50. Here C(n.k) is a binomial coefficient (n choose k). So, we can iterate through all these variants and choose the best weight. For a reference, see Zuza's solution.

Value	1000
Submission Rate	16 / 73 (21.92%)
Success Rate	6 / 16 (37.50%)
High Score	neal_wu for 797.10 points (15 mins 9 secs)
Average Score	670.70 (for 6 correct submissions)

In this problem you were given a set of integers {a₁, a₂, … , a_n} and two numbers L and H. The problem was to find a number of subsets which arithmetic mean is between L and H, inclusive.

Since the total number of subsets in the worst case is 2^36 = 68719476736, simple iterating through all of them will easily timeout. But we can use a well-known technique to speed up this approach.

Let's partition our set into two subsets A1 = { a₁,…, a_n/2} and A2 = { a_n/2+1,…, a_n}. Now each subset contains not more than 2^18 = 262144 elements. Iterate through all subsets of A1 and for each subset calculate two values: a number of its elements k and a sum of its elements s. Add each s to the list halfSums[k]. After that, sort all lists halfSums[i], for all i from 0 to n/2.

Why have we done that? Because now, if someone asks us how many subsets in A1 with exactly k elements have sum less than or equal to s, we can easily answer in O(log(2^(n/2))) = O(n) time, using binary search. Let's denote this query as count(k,s).

All pre-calculations are done, and we can move straight to the getting the answer to the main problem.

Iterate through all subsets of A2 just like we did with A1. For each subset with k elements and sum s we iterate through the number of elements in subset in A1 t and add the value of count(t,H*(t+k) - s) - count(t,L*(t+k) – s-1) to the answer. All of the correct submissions are based on the similar idea. See neal_wu's solution as an example of very clean implementation. It's really amazing that it's also the fastest submission of the hard problem.