PROBLEM LINK:
Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi
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 N-2” \times 4.
Let’s define dp[i] as the number of subsets whose sum is equal to i. dp can be calculated using the well-known knapsack problem.
Now, for each unique pair of numbers in the set, try removing them and calculating the NOSS of the rest of the numbers. It can be proven that the number of unique pairs of numbers in the set is of O(S), where S is the sum of all of the numbers in the set. You can remove the pair from the dp array in O(S) and then count how many of the slots in dp are greater than 0 modulo some big prime MOD (like 10^9 + 7). The probability that those slots really contain 0 and not just 0 modulo MOD is very high. This way, we can calculate NOSS of the rest of the numbers.
This solution runs in O(S^2).
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.
The proof is relatively simple. Let’s assume that there are K different numbers in a. Now, let’s sort these K numbers. The first one is at least 1, the second one is at least 2, the third one is at least 3 and so on. This gives us S \geq \frac{K \times (K+1)}{2}. Hence, K is of O(\sqrt{S}).
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 N-2 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 N-2 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:
for (int i = MAXN-1; i >= x; i--)
dp[i] += dp[i-x];
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:
for (int i = x; i < MAXN; i++)
dp[i] -= dp[i-x];
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