Editorial for Baltic OI '08 P6 - Gloves
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us denote by the set of all considered colours, i.e.:
For any , let us denote by the number of all left gloves of colours from the set , and by the number of all right gloves of colours from the set . Formally:
By , we will denote the total number of left gloves, and by , we will denote the total number of right gloves.
We will call a pair acceptable if and only if we can take left gloves and right gloves (i.e. and ), and taking left gloves and right gloves guarantees that we have taken at least one pair of equally-coloured gloves. We say that pair dominates pair iff and , or and .
Model Solution
Let be a subset of and let . For any and , choosing gloves from the first drawer and gloves from the second drawer does not guarantee getting one pair of equally-coloured gloves. On the other hand, if we take left gloves and right gloves from respective drawers, and for every and we have:
then we have taken at least one pair of equally-coloured gloves. To prove it, it is enough to consider any choice of left gloves and right gloves, which does not contain any equally-coloured pair and observe that for the partition of (where denotes the number of gloves of colour taken from the first drawer) the condition (1) is not satisfied.
Based on the above observation, we can design the following algorithm: Let us consider all the subsets . For each such , we compute the numbers and . We can view a rectangle on the plane , representing all the points that do not satisfy (1). We can generate all such rectangles by considering all subsets . Their sum (as subsets of ) is a 'staircase shaped' polygon, as shown below:
This figure shows all the points which are not acceptable. Now we only need to find the minimal (in the sense of the sum of coordinates) point with integer coordinates outside the staircase polygon, but inside the rectangle .
The model solution considers all pairs and finds the pairs that are not dominated by other pairs. That is, they are the vertices of the 'staircase' polygon. The pairs are processed in lexicographical order using a stack. The stack contains the pairs that are processed so far, that are not dominated. Whenever we add a pair, the pairs dominated by it are on the top of the stack and can be popped. Then such a pair is pushed on top of the stack. Since each pair can be pushed and popped from the stack only once, the amortized cost of processing the pairs is . Finally, the result is the 'north-east' neighbour of a concave vertex of the 'staircase' polygon.
The overall time complexity of the algorithm is , since the dominating phase is sorting pairs.
Comments