Editorial for DMOPC '17 Contest 3 P3 - N-Kat

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Kirito, r3mark

For $20\%$ ~20\%~ of points, we can write two nested loops, both of which iterate over all $\mathcal O(2^N)$ ~\mathcal O(2^N)~ non-empty subsets. We can check in $\mathcal O(N)$ ~\mathcal O(N)~ time that the two subsets are distinct, and also determine the difference between the two subsets' values.

Time Complexity: $\mathcal O(N \cdot 2^{2N})$ ~\mathcal O(N \cdot 2^{2N})~

Call the value of a subset $S$ ~S~, $val(S)$ ~val(S)~, the sum of the values of the elements in a subset $S$ ~S~. For the remaining $80\%$ ~80\%~ of points, we can generate all non-empty subsets as well as their values in $\mathcal O(N \cdot 2^N)$ ~\mathcal O(N \cdot 2^N)~. Then, we can sort these by their values in $\mathcal O(N \cdot 2^N)$ ~\mathcal O(N \cdot 2^N)~ time. The answer is then the pair of adjacent subsets in this sorted list which are disjoint and have the smallest difference.

To prove that this indeed works, consider the two subsets $A$ ~A~ and $B$ ~B~ such that $A \cap B = \emptyset$ ~A \cap B = \emptyset~, $val(A) \le val(B)$ ~val(A) \le val(B)~ (and $A$ ~A~ is before $B$ ~B~ in the sorted list), and $val(B)-val(A)$ ~val(B)-val(A)~ is minimized. To break ties, choose $val(A)$ ~val(A)~ minimal. To break further ties, choose $B$ ~B~ such that $B$ ~B~ appears as early as possible in the sorted list.

Assume for the sake of contradiction that $A$ ~A~ and $B$ ~B~ are not adjacent in the sorted list. Let subset $C$ ~C~ be the subset directly after $A$ ~A~ in the sorted list. By our assumption, $B \ne C$ ~B \ne C~.

Case 1: $A \subset C$ ~A \subset C~

Since all values of individual elements are positive, then $val(A) < val(C)$ ~val(A) < val(C)~. Note that since $A \cap B = \emptyset$ ~A \cap B = \emptyset~, $C \not\subset B$ ~C \not\subset B~. Also, since $C$ ~C~ is between $A$ ~A~ and $B$ ~B~ in the sorted list, $val(B) \ge val(C)$ ~val(B) \ge val(C)~, so $B \not\subset C$ ~B \not\subset C~. Now let $B' = B \setminus (B \cap C)$ ~B' = B \setminus (B \cap C)~ and $C' = C \setminus (B \cap C)$ ~C' = C \setminus (B \cap C)~. Note that $val(B')-val(C') = val(B)-val(C)$ ~val(B')-val(C') = val(B)-val(C)~ and $B' \cap C' = \emptyset$ ~B' \cap C' = \emptyset~. But $val(B')-val(C') = val(B)-val(C) < val(B)-val(A)$ , which is a contradiction to $val(B)-val(A)$ ~val(B)-val(A)~ minimal.

Case 2: $A \not\subset C$ ~A \not\subset C~

Since $val(A) \le val(C)$ ~val(A) \le val(C)~, $C \not\subset A$ ~C \not\subset A~. If $A \cap C = \emptyset$ ~A \cap C = \emptyset~, then since $val(C) \le val(B)$ ~val(C) \le val(B)~ and $C$ ~C~ appears before $B$ ~B~, this is a contradiction to $B$ ~B~ appearing the earliest (while the other conditions are satisfied, which they are for $A$ ~A~ and $C$ ~C~). Otherwise, let $A' = A \setminus (A \cap C)$ ~A' = A \setminus (A \cap C)~ and $C' = C \setminus (A \cap C)$ ~C' = C \setminus (A \cap C)~. But then $val(A') < val(A)$ ~val(A') < val(A)~ and $val(C')-val(A') = val(C)-val(A) \le val(B)-val(A)$ , which is a contradiction to $val(A)$ ~val(A)~ being minimized while $val(B)-val(A)$ ~val(B)-val(A)~ is minimized.

So in both these cases, there is a contradiction. So $A$ ~A~ and $B$ ~B~ are adjacent in the sorted list.

Time Complexity: $\mathcal O(N \cdot 2^N)$ ~\mathcal O(N \cdot 2^N)~

Note: There is also an approach via meet-in-the-middle which the majority of contestants used to solve this problem. Interestingly, the above approach fails when the values of items may be negative, while the meet-in-the-middle approach still works. Another thing to note is that test cases were weak, so checking adjacent elements without also checking if they are disjoint will AC. These submissions fail on the following test case:

3
1 10 100

Comments

There are no comments at the moment.