JOIN
 Match Editorials
TCHS SRM 43
Tuesday, October 23, 2007

## 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

TransformArray
Used as: Division One - Level One:
 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.

Used as: Division One - Level Two:
 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.

ArithmeticalMean
Used as: Division One - Level Three:
 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 {a1, a2, … , an} 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 = { a1,…, an/2} and A2 = { an/2+1,…, an}. 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.

By it4.kp
TopCoder Member