Can anyone help me in this CSES Two Set"
I understood the problem, but don’t know how to approach.
heres a hint
the total sum of the elements is n\cdot(n+1)/ 2
The sum of first n natural number is n.(n+1)/2 . If this is even we can always partition the n numbers into 2 sets; such that sum of elements of each set is equal.
Can someone prove this?(I’ve already done this problem using above as a fact and got accepted; but I would like to know if the above statement is true and how to approach about its proof)
void solve(ll n) {
ll temp = (n*(n+1)/2);
if (temp % 2 == 1) {
cout << "NO\n";
return;
}
cout << "YES\n";
ll target = temp/2;
ll sum = 0;
ll i = n;
unordered_set<ll> s;
s.reserve(n);
while (sum < target) {
s.insert(i);
sum += i;
/* cout << "Inserting " << i << " sum = " << sum << endl; */
i--;
}
if (sum > target) {
sum -= (i+1);
assert(sum < target);
s.erase(s.find(i+1));
/* cout << "Removing " << i + 1 << " sum = " << sum << endl; */
s.insert(target - sum);
/* cout << "Inserting " << target - sum << " sum = " << sum << endl; */
}
cout << s.size() << "\n";
for (auto element : s) {
cout << element << " ";
}
cout << "\n";
cout << n - s.size() << "\n";
for (int j = 1; j <= n; j++) {
if (s.find(j) == s.end()) {
cout << j << " ";
}
}
cout << "\n";
}
When N is even; the proof is simple construction i.e take the numbers in pairs.
for e.g :- 1 2 3 4 5 6 7 8
But what’s the proof when N is odd and sums up to even. e.g N = 7
when N is 6, there is no solution …
I meant that when N is even and the sum \displaystyle N.\frac{N+1}{2} is even, then it is easy to partition into 2 sets by taking numbers in pairs.
Your submission is not visible to me.
Same here ^^.
Because we can’t split the odd sum into 2 equal halfs. Ex.: n = 21, 21/2 = 11.5 the solution is not possible.
A natural approach is to greedily add the largest numbers from n, n-1, \dots, 1 such that the sum of the selected numbers does not exceed \frac{n(n+1)}{4} (the required sum for each of the two piles). If it does exceed, consider the next smaller number as the new candidate and go from there.
For this to work, we need to first prove that subsets of 1, 2, \dots, n can be used to create any sum between 1 and n(n+1)/2 inclusive. A simple construction suffices for this. 1 through n inclusive can be created with just a single number. Now consider how to create from n+1 to 2n. Consider the baseline sum to be n, and n-1 to be the "new n". Then creating n+1 to 2n is equivalent to creating 1 to n, which can be done with the same “single number” construction as aforementioned. Repeating this procedure should make clear the claim is true.
To complete the proof of our greedy solution, notice that when you add the largest number such that the sum does not exceed n(n+1)/4, you are left with a remaining portion less than n(n+1)/4 that you need to sum to. This remaining portion is guaranteed to not exceed n(n+1)/2, even in new scopes of n, so the greedy approach must be able to construct a solution due to the proof above.
4 Likes