HDU 3748 Equivalent mass

Problem Statement:

• Given N elements, A[N], determine if it is possible to pick exactly K of them s.t. the sum is V. But you cannot pick X^th and Y^th simultaneously, for some given pairs (X, Y). There are M such pairs.

Constraints:

• 1 <= N <= 32
• 1 <= A[i], V <= 10^9
• 0 <= M <= 6
• 0 <= K <= N

Algorithm:

1. Divide A[N] roughly into halves, S and T, s.t. each holds roughly the same number of elements.
2. For each set, exhaust all (2^||S|| for set S) possible configurations.
3. Try to merge configurations of S and T to form a solution.
   i.e., If you find a way to pick M elements from S with sum = U, you will want to check if it is possible to pick K-M elements from T with sum = V - U.
4. The checking can be done using a hash table/STL-map... etc.

Complexity:

• Roughly O(2^N/2) × [ O("Insertion+Query runtime") + O(M) ]
  (c.f., Point 1. below)

Subtlety:

1. Handle (X, Y) pair constraints.
   If X and Y are in S and T respectively, it could be difficult to handle. My implementation fixes every two elements which occur in the same constraint to be in set S. Although then |S| may not be ~= N/2, but |S| will be at most 2M.
2. When K is large.
   Rephrase the problem as: Find N - K elements, s.t. the sum is ∑_iA[i] - V.
   (Remind: Take extra care of the (X, Y) pair constraints.)

Related:

• POJ 3139 Balancing the Scale (Shanghai 2006)