Two even leagues
A chess tournament between cities is divided into two leagues, each with an equal number of cities, n/2. The organisers want the leagues to be equal in population too: the total population of the cities of the first league should differ as little as possible from that of the second. One of the tests is the 36 largest cities of the world according to GeoNames.
Find the smallest possible difference between the leagues’ populations.
Input
The first line holds an even number n (2 ≤ n ≤ 36). The second holds n numbers w1, …, wn, the populations of the cities (1 ≤ wi ≤ 1012).
Output
One number: the smallest difference between the total populations of two leagues of n/2 cities each.
Examples
Example 1
6 10 1 1 1 1 6
4
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
There are about 9 billion ways to choose 18 cities out of 36. The numbers go up to 1012, so a table of “which sums are reachable” will not fit either. What does the limit n ≤ 36 hint at?
2Hint 2
Without the requirement of “equal numbers of cities” this is the problem from the article on meeting in the middle: two halves of 18 cities, all sums of each, binary search. Try its solution on the example: it answers 0, the city with population 10 against the other five. But then the leagues have one and five cities. What is missing from the key of the meeting?
3The idea
If c cities from the left half are taken into a league, exactly n/2 − c must be taken from the right. So split the sums of each half by the number of cities taken: Lc is the sums of subsets of the left half of c cities, Rc of the right. Only Lc and Rn/2−c meet. Within a pair of groups it is an ordinary meeting: R is sorted, and for each sum a on the left binary search looks for the one closest to s/2 − a.
4Walkthrough
Sums and sizes are conveniently built together by doubling: start with the lists [0] and [0] and for each city append to the list of sums a copy of itself plus the population, and to the list of sizes a copy of itself plus one. Then split the sums by size and sort the groups of the right half.
To avoid halving an odd sum, compare doubled numbers: the difference between the leagues is |s − 2(a + b)|, and for a given a the b for which 2b is closest to s − 2a is needed. The first b with 2b ≥ s − 2a and the one before it are the two candidates, as in the article.
The general trick: if the answer is made of the halves under some condition, the condition becomes part of the key of the meeting. Here it is the size; it may be a remainder modulo something, a colour, the last vertex of a path.
4+Solution
5Complexity
2 · 2n/2 sums, sorting the groups and a binary search for each left sum: O(2n/2 · n). With n = 36 that is about 260 thousand sums per half. The memory is the same 2n/2 numbers.
6Common mistakes
- Forgetting the size of the leagues. Meeting in the middle without groups by size answers a different problem and gives an answer smaller than the correct one: 0 instead of 4 on the example.
- Greed. Hand out cities in decreasing order to the league with fewer people and room left. Fast, but the difference comes out larger than the smallest already on random tests.
- Halving. If b is sought around (s − 2a) / 2 by integer division, the closest candidate may be lost with an odd sum. Doubled comparisons do not know this trap.
- Overflow. The sum of populations reaches 3.6·1013, which does not fit in a 32-bit type.