Codejam 2015 - Round 3 - Log Set

7 Jan 2016

Problem is getting more difficult. I cannot solve this problem at all, not even the small data set.

I've realised that some of the sets will contain only one element. Therefore, I can pick some elements and check if they are the answer. The solution runs way too slow.

A more clever solution is to utilise the difference between the largest sum and the second largest sum. This guarantees that there is only one element between them. This can be proven by contradiction. Let's write the proof:

The largest sum is X, the second largest sum is Y, and X > Y. If there are 2 elements, a and b, between X and Y, then Y cannot be the second largest sum. There must be A = Y + a, and B = Y + b, and X > A > Y and X > B > Y.

Now why isn't it true for the 2nd largest sum and the 3rd largest sum? why isn't there one element between them? – This is because the 2nd largest sum could come from the 4th largest sum with one more element.

Let's move on. Since we have found that one element, d, we can remove it from the set. When we remove one element, the number of power sets is reduced by half (from 2N to 2N-1). Now the question becomes which sum (or set) should be removed.

The first thing to notice is that d is the smallest element. We can also prove this by contradiction. Y wouldn't be the 2nd largest sum if d is not the smallest element.

When we add d, Y is transitioned to X. That's it. We can delete half members of the power set by pairing up 2 sums that has the difference d. For example, if we have A, B, C, and D, and B - A = C -B = D - C = d, then we can eliminate D and B. We don't delete C, even B + d = C. Because we have only one d and C doesn't contain d because C + d = D… Therefore, C must not contain d. Therefore, we cannot delete C.

Anyway, after we delete d, we can repeat the process again and again until we find all the magnitudes of the set.

Man, this solution is so difficult to understand. I read it for like 2 hours and coded it for another 2 hours to get it right… I say magnitude because we need to figure out which element is positive and which is negative. We can do that easily by finding which subset yields the largest sum. Then those elements should be positive, and the rest should be negative.