Solution of Peculiar Function

The first observation we can make is that 0 ≤ orSum(S') < 2^19 for any subset S' of S1. Let's see if we can construct a set Q, having 0 ≤ orSum(Q) < 2^19 using the integer values from S1. It is enough to consider for this all elements of S1 which are completely included in Q. An element x is completely included in a set S if orSum(S) | x = orSum(S), i.e. there is no position 0 ≤ i < 19 for which orSum(S) & 2^i == 0 and x & 2^i != 0. If these are not enough to form Q, then we cannot obtain Q at all.

We now need to compute for each such Q the orSum of all elements “completely included” in S1. We can compute dp[x] = orSum(dp[x - 2^i]), where 0 ≤ i < 19 and x & 2^i == 2^i. Remark: if x belongs to S1, then dp[x] = x.

Now, S2 needs to contain all numbers x having dp[x] = x and orSum({dp[x - 2^i] where 0 ≤ i < 19 and x & 2^i == 2^i}) < x. This assures us that they cannot be generated by applying orSum on a subset of numbers from S1, so they must be in S2.

Questions?

Sponsors Gold