Let us denote by ~Z_n~ the set of all considered colours, i.e.:

$$\displaystyle Z_n = \{1, 2, \dots, n\}$$

For any ~X \subseteq Z_n~, let us denote by ~A_X~ the number of all left gloves of colours from the set ~X~, and by ~B_X~ the number of all right gloves of colours from the set ~X~. Formally:

• ~A_X = \sum_{i \in X} a_i~
• ~B_X = \sum_{i \in X} b_i~

By ~L = A_{Z_n} = a_1 + \dots + a_n~, we will denote the total number of left gloves, and by ~R = B_{Z_n} = b_1 + \dots + b_n~, we will denote the total number of right gloves.

We will call a pair ~(l, r)~ acceptable if and only if we can take ~l~ left gloves and ~r~ right gloves (i.e. ~l \le L~ and ~r \le R~), and taking ~l~ left gloves and ~r~ right gloves guarantees that we have taken at least one pair of equally-coloured gloves. We say that pair ~(l, r)~ dominates pair ~(l', r')~ iff ~l > l'~ and ~r > r'~, or ~l > l'~ and ~r > r'~.

Model Solution

Let ~X~ be a subset of ~Z_n~ and let ~Y = Z_n \setminus X~. For any ~0 \le l \le A_X~ and ~0 \le r \le B_Y~, choosing ~l~ gloves from the first drawer and ~r~ gloves from the second drawer does not guarantee getting one pair of equally-coloured gloves. On the other hand, if we take ~l~ left gloves and ~r~ right gloves from respective drawers, and for every ~X \subseteq Z_n~ and ~Y = Z_n \setminus X~ we have:

$$\displaystyle l > A_X \lor r > B_Y \quad (1)$$

then we have taken at least one pair of equally-coloured gloves. To prove it, it is enough to consider any choice of ~l~ left gloves and ~r~ right gloves, which does not contain any equally-coloured pair and observe that for the partition of ~Z_n : X = \{i \in Z_n : a'_i > 0\}, Y = \{i \in Z_n : a'_i = 0\}~ (where ~a'_i~ denotes the number of gloves of colour ~i~ 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 ~X \subseteq Z_n~. For each such ~X~, we compute the numbers ~A = A_X~ and ~B = B_{Z_n \setminus X}~. We can view a rectangle on the plane ~[0, A] \times [0, B]~, representing all the points ~(l, r)~ that do not satisfy (1). We can generate all such rectangles by considering all subsets ~X \subseteq Z_n~. Their sum (as subsets of ~\mathbb R^2~) is a 'staircase shaped' polygon, as shown below:

This figure shows all the points ~(l, r)~ 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 ~[0, L] \times [0, R]~.

The model solution considers all ~2^n~ pairs ~(A, B)~ 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 ~\mathcal O(2^n)~. Finally, the result is the 'north-east' neighbour of a concave vertex of the 'staircase' polygon.

The overall time complexity of the algorithm is ~\mathcal O(2^n n)~, since the dominating phase is sorting ~2^n~ pairs.