CF 279D - The Minimum Number of Variables

Rating: 2200
Tags: bitmasks, dp
Solve time: 2m 37s
Verified: no

Solution

Problem Understanding

We are given a sequence of distinct positive integers. The sequence is not arbitrary, it must be generated step by step using a collection of variables.

At the beginning every variable contains 0.

The first value of the sequence is special. We may write a₁ directly into any variable.

For every later value a_t, we must choose two variables, read their current contents, add them, and assign the result to some variable. The value produced at step t must be exactly a_t.

Variables may be reused. Assigning a new value to a variable overwrites whatever was stored there before.

The question is not whether the sequence can be generated. We must find the smallest number of variables that makes the whole process possible. If no number of variables works, the answer is -1.

The constraint that changes everything is n ≤ 23. The values themselves can be as large as 10^9, so we cannot build a DP over the numbers. The small value of n strongly suggests that every produced value should be treated as an individual object and represented by a bit in a mask.

A subtle observation is that every value ever stored in a variable is either 0 or one of the sequence elements that has already been produced. Since all sequence values are distinct and positive, a value can never be recreated accidentally as a later sequence element.

Several edge cases are easy to miss.

Consider

2
1 5

The second value must be obtained as a sum of already existing values. The only available positive value is 1, so the only possible sums are 1+1=2 or 1+0=1. Producing 5 is impossible, so the correct answer is -1.

Another trap is allowing a value to be used twice in the same sum.

2
3 6

After producing 3, we may compute 6 = 3 + 3. The statement allows i = j, so only one stored copy of 3 is needed. An implementation that requires two different variables would incorrectly reject this case.

A third trap is forgetting that assigning a new value overwrites at most one existing value.

3
1 2 3

After producing 2, we may overwrite the variable holding 1 when creating 3, but we cannot delete several values at on