Two Sets
Split 1 through n into two groups with equal sum, or report that such a partition does not exist.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Use every number from \(1\) through \(n\) exactly once and split them into two sets with the same total sum. If this cannot be done, print that immediately.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
The total sum is \[ \frac{n(n + 1)}{2}. \] If that sum is odd, then two equal halves are impossible.
Assume the total sum is even and let the target be half of it. We can build one set greedily from large numbers down to small numbers:
inspect \(n, n - 1, \ldots, 1\)
whenever the current number does not exceed the remaining target, take it into the first set
subtract it from the remaining target
This works because the numbers are consecutive. If a large number fits, taking it is always safe and makes the remaining target smaller; if it does not fit, we simply skip it and keep looking. By the time we reach \(1\), the remaining target must be \(0\).
Everything that was not taken belongs to the second set.
Pseudocode
Natural algorithm flow before dropping to the concrete C++ implementation.
Compute the total sum of \(1\) through \(n\).
If the total sum is odd:
print
NOstop
Set the remaining target to half of the total.
For values from \(n\) down to \(1\):
if the value is at most the remaining target, put it in the first set and subtract it from the target
otherwise leave it for the second set
Print both sets.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(n)\)
Memory: \(O(n)\) to store the chosen partition
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
#include <vector>
int main() {
std::int64_t n;
std::cin >> n;
const std::int64_t total = n * (n + 1) / 2;
if (total % 2 == 1) {
std::cout << "NO\n";
return 0;
}
std::int64_t target = total / 2;
std::vector<int> first_set;
std::vector<int> second_set;
for (int value = static_cast<int>(n); value >= 1; --value) {
if (value <= target) {
first_set.push_back(value);
target -= value;
} else {
second_set.push_back(value);
}
}
std::cout << "YES\n";
std::cout << first_set.size() << '\n';
for (std::size_t i = 0; i < first_set.size(); ++i) {
std::cout << first_set[i] << (i + 1 == first_set.size() ? '\n' : ' ');
}
std::cout << second_set.size() << '\n';
for (std::size_t i = 0; i < second_set.size(); ++i) {
std::cout << second_set[i] << (i + 1 == second_set.size() ? '\n' : ' ');
}
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
Any valid partition is accepted, so the greedy descending construction is enough.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.