Editorial for DMOPC '17 Contest 3 P3 - N-Kat
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
,For of points, we can write two nested loops, both of which iterate over all
non-empty subsets. We can check in
time that the two subsets are distinct, and also determine the difference between the two subsets' values.
Time Complexity:
Call the value of a subset ,
, the sum of the values of the elements in a subset
. For the remaining
of points, we can generate all non-empty subsets as well as their values in
. Then, we can sort these by their values in
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 and
such that
,
(and
is before
in the sorted list), and
is minimized. To break ties, choose
minimal. To break further ties, choose
such that
appears as early as possible in the sorted list.
Assume for the sake of contradiction that and
are not adjacent in the sorted list. Let subset
be the subset directly after
in the sorted list. By our assumption,
.
Case 1:
Since all values of individual elements are positive, then . Note that since
,
. Also, since
is between
and
in the sorted list,
, so
. Now let
and
. Note that
and
. But
, which is a contradiction to
minimal.
Case 2:
Since ,
. If
, then since
and
appears before
, this is a contradiction to
appearing the earliest (while the other conditions are satisfied, which they are for
and
). Otherwise, let
and
. But then
and
, which is a contradiction to
being minimized while
is minimized.
So in both these cases, there is a contradiction. So and
are adjacent in the sorted list.
Time Complexity:
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