
Match Editorials 
TCHS SRM 43Tuesday, 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 wouldbe 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.
TraditionalMarriage
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 {a_{1}, a_{2}, … , 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 wellknown technique to speed up this approach.
Let's partition our set into two subsets A1 = { a_{1},…, 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 precalculations 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) – s1) 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