PROBLEM LINK:Author: AmirReza PoorAkhavan PREREQUISITES:DP, KNAPSACK PROBLEM:You are given a set of positive integers $a$. You are asked to replace any two of those numbers with any pair of positive integers so that the number of values you can obtain by adding up a subset of them (possibly empty) is maximized. You need to print this maximum number of values. QUICK EXPLANATION:The answer is "the maximum NOSS over all subsets of size $N2$" $\times 4$. EXPLANATION:First of all, let's define $S$ as the sum of all the integers given in the input. The problem's description guarantees that $S \leq 10^4$. Let's prove that there are at most $O(\sqrt{S})$ different numbers in $a$. Since there are ${K+1}\choose{2}$ unique pairs of numbers to change, the abovementioned fact tells us there are at most $O(S)$ unique pairs of numbers to change. The description of the problem tells us we can change two numbers to any natural number. Let's think of it as removing two numbers, making a new set out of the remaining $N2$ numbers, and then adding two arbitrary numbers to that set. By adding a number to a set, its NOSS can get doubled at most; and we can achieve that increment by choosing a very large number to add. With the same reasoning, by adding two numbers we can increase the NOSS of the set $3$ times. Or in other words, we'd be multiplying the NOSS of the set of size $N2$ by $4$. So all that's left is to calculate for each unique pair of integers from the set, what will the NOSS of the set be after removing them. Let's define $dp[i]$ as the number of subsets of $a$ whose sum is equal to $i$. You can calculate this dp by inserting the numbers one by one, something like this:
Now let's iterate over all unique pairs of numbers from $a$ and try removing them from $dp$. The removal can be done like this:
After removing the pair, go through all the slots of $dp$ and count how many of them are greater than $0$. This gives us a solution of $O(S^2)$. One problem remains though. The numbers in the $dp$ array can get arbitrarily large. To avoid overflow, we can do all of our calculations modulo some big prime called MOD. MOD can be $10^9 + 7$. The only problem with this approach is that if $dp[i] = 0$, we assume that $dp[i]$ really is equal to $0$ and not just equal to $0$ modulo MOD. But The probability of this assumption failing is low and thus this solution works. Refer to the editorialist's solution to see the described solution. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here Tester's solution can be found here Editorialist's solution can be found here
This question is marked "community wiki".
asked 29 Dec '18, 09:05

Finally, the longawaited editorial for this problem. Thanks! Looking forward to reading the editorial of this problem as well in near future. https://www.codechef.com/LTIME66A/problems/MDN Please admin look into it, really need the editorial to the "median" problem.
link
This answer is marked "community wiki".
answered 22 Jan, 00:09
