This task is a simple variation of the discrete backpack problem. Instead of items packed in a backpack, we have parties with certain numbers of seats in a parliament to form a coalition. In this problem, we do not have to find out if a given amount of votes can be obtained, but what is the maximal size of a possible, non-redundant coalition. Non-redundancy makes the problem a little bit harder — during dynamic algorithm one has to somehow ensure that constructed coalition will not be redundant, which can occur when trying to apply standard methods.

The solution to this problem is considering the parties in non-ascending order of number of seats. It is a simple observation that if one breaks the minority when adding a party to a coalition consisting only of larger parties, the new coalition will be proper and non-redundant. Therefore, after sorting the sizes of parties we use the standard dynamic algorithm to consider subsets of parties which do not have majority and record only 'skips' over the half.

This 'trick' makes the problem more interesting, but still it is rather standard and easy.

Jury's solution

Firstly, let us observe that a coalition is non-redundant if without a member party with the smallest number of seats it hasn't got the majority in the parliament. Obviously, every non-redundant coalition has this property. Moreover, if exclusion of the smallest party breaks the majority, then exclusion of each larger will break as well, so each coalition with this property will be indeed non-redundant. Going further, all non-redundant coalitions are created from subsets not having majority by adding a party not larger than any already included.

In the first step of the algorithm, the results of parties are to be sorted in non-ascending order of the number of seats. As there are at most ~300~ parties, we can do this using sorting algorithms with complexity ~\mathcal O(n^2)~, or use template ones in C/C++ instead. Now we can assume that if ~a_1, a_2, \dots, a_n~ are the number of seats of parties then ~a_1 \ge a_2 \ge \dots \ge a_n~.

In the second step, we apply a dynamic programming approach. Let ~s~ be the total number of seats in the parliament, computed during input reading. We will use two arrays with size ~[0 \dots s]~: partyUsed[i] and partySkip[i]. Let us assume that we have already considered the first ~k~ largest parties. In partyUsed[i] we will store the number of the smallest party of a subset of considered parties, which has exactly ~i~ seats in total. If such a subset does not exist, ~-1~ will be stored. In partySkip[i] the size of party from partyUsed[i] shall be recorded. It will be useful further to reconstruct the optimal coalition. The information in those two arrays will be stored only for subsets of parties not having majority and for non-redundant coalitions.

It is easy to observe that such a data structure can be maintained by considering the parties one after another. Firstly, partyUsed is filled with ~-1~. If we consider ~k^\text{th}~ party, we add its number of seats to all values not exceeding ~\lfloor \frac s 2 \rfloor~, obtained in previous steps. Thus we construct new subsets of parties, each including this new party. We record all the new possible numbers of seats built in this way, changing the appropriate value in partyUsed to ~k~ and in partySkip to the corresponding number of votes. The values having majority are being recorded in this step, but they are not included in the set of values, to which we add the considered number of seats. The observation in the first paragraph ensures us that all such number of seats will be results of non-redundant coalitions, as the parties were considered in non-ascending order of number of seats.

In order to quickly find out, which numbers of seats have been obtained so far, we store them in an additional container — for example a vector or an array. If a new number of seats below majority has been constructed, we simply add information about it to this structure. In the beginning, only ~0~ is included.

In the third step, we are to reconstruct the optimal coalition. Firstly we seek its number of seats. We can do it by finding the largest index with nonnegative value in partyUsed, or by remembering it during performing the previous step. Then we are able to reconstruct the answer. We begin with a variable best set to the found index and decrement it by partySkip[best] while recording usage of partyUsed[best]. After reaching ~0~, the whole coalition has been recorded and is ready to be printed. This algorithm is correct, because parties with no seats will never be used, as they are always redundant.

The first step of the algorithm, implemented efficiently, has time complexity ~\mathcal O(n \log n)~. The second one takes ~\mathcal O(ns)~ time — for each of ~n~ parties we consider at most ~\lfloor \frac s 2 \rfloor~ recorded values. The last step has complexity ~\mathcal O(n)~, as the answer cannot be larger. For a reasonable data set we have ~s \ge n~, so the time complexity of the whole algorithm is ~\mathcal O(n \log n + ns) = \mathcal O(ns)~. It is noteworthy that the usage of inefficient sorting algorithms does not worsen the time complexity.

The memory complexity is ~\mathcal O(s)~ because of the usage of arrays of this size in dynamic programming.