PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
You’re given two integers x and N. Consider all integers between 1 and N inclusive, except x. We want to partition these integers into two disjoint sets such that the sums of numbers in this sets are equal.
QUICK EXPLANATION
Write simple brute-force which goes from N to 1 and firstly tries to take current number into lesser set. Turns out it’s fast enough.
EXPLANATION:
Sum of numbers from 1 to N is equal \tfrac{N(N+1)}{2}. If it has different parity from x then solution doesn’t exist at all. Otherwise it does with few exceptions.
To solve the problem you can write the following simple brute-force:
bool brute(int n, int x, int64_t l = 0, int64_t r = 0) {
if(n == x) {
ans[n - 1] = '2';
return brute(n - 1, x, l, r);
}
if(n == 0) {
return l == r;
}
if(l < r) {
if(brute(n - 1, x, l + n, r)) {
ans[n - 1] = '0';
return true;
} else {
ans[n - 1] = '1';
return brute(n - 1, x, l, r + n);
}
} else {
if(brute(n - 1, x, l, r + n)) {
ans[n - 1] = '1';
return true;
} else {
ans[n - 1] = '0';
return brute(n - 1, x, l + n, r);
}
}
}
This solution goes by numbers from N to 1 trying to keep l and r close to each other. Thus if first sum currently less than second one then we try to proceed adding number n to first sum, otherwise we firstly try second sum. If that didn’t lead to solution then we try another option. At first it looks like this will consume too much time but it’s not true.
You can prove by induction that |l-r|\leq n+1 at each step of algorithm for which n \geq x or n < x - 1. And only for n=x-1 it is |l-r|\leq n+2. That means that if x>2 we will have |l-r|\leq 2 for n=1. But |l-r| will always be even after this step since we ensured that l+r=\dfrac{N(N+1)}{2}-x is even at the beginning. That means that |l-r|=1 at n=1 for x>2 and greedy solution works just fine.
As for cases x=1 and x=2 we should use the fact that |l-r|\leq 6 for n=5. You can manually check that you will always find solution from this step:
- x=1,|l-r|=0 \to \{2, 5\}, \{3,4\}
- x=1,|l-r|=2 \to \{2, 4\}, \{3,5\}
- x=1,|l-r|=4 \to \{2, 3\}, \{4,5\}
- x=1,|l-r|=6 \to \{4\}, \{2,3,5\}
- x=2,|l-r|=1 \to \{1, 5\}, \{3, 4\}
- x=2,|l-r|=3 \to \{1, 4\}, \{3, 5\}
- x=2,|l-r|=5 \to \{1, 3\}, \{4, 5\}
So overall it will take for you at most n+2^5 operations per testcase which is enough to solve the problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
