Codeforces Round #717 Baby Ehab Partitions Again - Math+01 Knapsack problem

Solution

Define $sum=\sum_{i=1}^n a_i$. If $sum$ is a odd number, then of course no need remove anything.

If $sum$ is an even number, then we do a classic 01 knapsack problem in which capacity is $\frac {sum}2$. If it's impossible to fill the knapsack, then no need to remove anything.

Now, we have to remove something.

First of all, if it's exist odd number in $a$, then we can remove this odd number directly. And make the $sum$ become an odd number.

If it does not exist any odd number. Which mean all number in $a$ is even number. So before we remove any number, we can divide all the values in the array by 2. And we still keep two groups with the same sum without any group change.

If an odd number appeared after divided 2, then remove this number directly. Otherwise, still all even numbers, we divide it again and again until odd numbers appear.

Code:

Submission #113893840 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge