Two Sets

Two Sets
CSES medium

Divide the numbers \(1, 2, \ldots, n\) into two sets with equal sums.

Constraints:

  • \(1 \le n \le 10^6\)

Input:

  • One line: integer \(n\).

Output:

  • YES if the division is possible, otherwise NO.
  • If it is possible, then describe the two sets: for each set, one line with its number of elements, and one line with its elements.

Examples:

Input:

7

Output:

YES
4
1 2 4 7
3
3 5 6

Input:

6

Output:

NO
Solution

The sum of all numbers is \(S = n(n + 1) / 2\). If \(S\) is odd, it cannot be split into two equal integer halves, so the answer is NO.

If \(S\) is even, a division always exists, and we construct it. The first set must have sum \(T = S / 2\). We go through the numbers from \(n\) down to \(1\) and put the number \(i\) into the first set if \(i \le T\), where \(T\) is the sum that the first set still needs. Otherwise \(i\) goes into the second set.

Why does the first set get exactly the sum \(S / 2\)? The first set cannot take all numbers, because their sum \(S\) is larger than \(S / 2\). So some number is skipped. Consider the first number \(i\) that is skipped because \(i > T\). Then \(T \le i - 1\), and the number \(T\) itself is still among the unused numbers \(1, \ldots, i - 1\). From then on, every number larger than \(T\) is skipped, and when the loop reaches the number \(T\), it takes it and \(T\) becomes \(0\).

For \(n = 7\): \(S = 28\) and \(T = 14\). We take \(7\) and \(6\) (\(T = 1\)), skip \(5, 4, 3, 2\), and take \(1\). The sets are \(\{7, 6, 1\}\) and \(\{5, 4, 3, 2\}\), both with sum \(14\).

\(S\) can be about \(5 \cdot 10^{11}\), so we store it in long long.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long sum = 1LL * n * (n + 1) / 2;
    if (sum % 2 == 1) {
        cout << "NO\n";
        return 0;
    }

    long long target = sum / 2;  // the sum that the first set still needs
    vector<int> first, second;

    for (int i = n; i >= 1; i--) {
        if (i <= target) {
            first.push_back(i);
            target -= i;
        } else {
            second.push_back(i);
        }
    }

    cout << "YES\n";
    cout << first.size() << "\n";
    for (int x : first) {
        cout << x << ' ';
    }
    cout << "\n";
    cout << second.size() << "\n";
    for (int x : second) {
        cout << x << ' ';
    }
    cout << "\n";
}