You are not logged in. Please login at www.codechef.com to post your questions!

×

# NOSS - Editorial

Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi

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

This question is marked "community wiki".

asked 29 Dec '18, 09:05

7★watcher
37
accept rate: 0%

19.8k350498541

 0 Finally, the long-awaited 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 144●6 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,212
×86
×41

question asked: 29 Dec '18, 09:05

question was seen: 162 times

last updated: 22 Jan, 00:09