 # CHAAT3 - Editorial

[Contest: IYWT2021 - If you win this, Bhel Puri Treat] (Contest Page | CodeChef )

CHAAT3 - Samosa

Author: Meenaksshi S
Tester: Meenaksshi S
Editorialist: Meenaksshi S

EASY

Math

# PROBLEM:

Divide a sequence of n integers (1,2,3…n) into two sets X and Y such that each integer belongs to only one set (either X or Y) and sum of all integers in one set is equal to the sum of all integers in the other set i.e. ( Sum(X) = Sum(Y) )

Given the integer n, determine if it is possible to divide the sequence of n integers in such a way.

# QUICK EXPLANATION:

Calculate the sum of 1 to n integers.

Sum= \sum_{i = 1}^{N} i

Formula: \frac{n * (n+1)}{2}

If the sum is odd then it is impossible (Answer: “NO”)
Else if it is even then there is always a way to divide the sequence into two parts of equal sum. (Answer: “YES” ) → Proof is given in detail in explanation.

# EXPLANATION:

#include "bits/stdc++.h"

using namespace std;

int main()
{
int n;
cin >> n;
int sum = (n * (n + 1)) / 2; // formula for sum of first n natural numbers

if (sum % 2 == 0)   // sum is even
cout << "YES";

else                // sum is odd
cout << "NO";

return 0;
}


If \frac{n * (n+1)}{2} is even → Output “YES”

Otherwise → Output “NO”

Proof:

Let S = (n*(n+1)) /2

If we have an integer sequence of 1,2,3,…,n then we can obtain any number from 0 to S as the sum of some elements from this sequence.

Eg: (Greedily)

n = 3
S = (n*(n+1))/2 => (3*4)/2
=>S = 6

1 → 1
2 → 2
3 → 3
4 → 3+1
5 → 2+3
6 → 3+3

Hence if S is even, then we can obtain the sum S/2 in X.
And the remaining in Y => (S – (S/2)) = (S/2)
Hence the sum of integers in sets X and Y is equal to (S/2)
Therefore, there is always a possibility to obtain equal sum in sets X and Y if S is even. Answer is “YES”.

If S is odd it is only possible to obtain ceil(S/2) in one set and floor(S/2) in the other set. But it is never possible for the sum in both the sets to be equal. Hence the answer is “NO”.

# ALTERNATE EXPLANATION:

There is also another way to solve this problem
Take n \bmod 4 ( = n%4) and solve the problem manually for different cases.

Eg:
n = 1 → “NO”
n = 2 → “NO”
n = 3 → “YES” (1+2 , 3)
n = 4 → “YES” (1+4 , 2+3)
n = 5 → “NO”
n = 6 → “NO”
n = 7 → “YES” (1+2+5+6 , 3+4+7)
n = 8 → “YES” (1+4+5+8 , 2+3+6+7)
n = 9 → “NO”
n = 10 → “NO”

You may notice that this forms a pattern.
Here we can see that if (n%4) == 0 or (n%4) == 3, then the answer is “YES”
But if (n%4) == 1 or (n%4) == 2, then the answer is “NO”.
Proof:
Let’s see what can be done with the numbers n, n−1, n−2 and n−3. We can add n and n−3 in X and add n−1 and n−2 in Y. Then the difference between sums will definitely be 0. We can consider last four numbers this way until we have at least four numbers. And then we have a case n≤3. We can prove the solution for these four cases using bruteforce.

# SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"

using namespace std;

int main()
{
int n;
cin >> n;
cout << ((((n * (n + 1)) / 2) & 1) ? "NO" : "YES") << endl;
return 0;
}

Tester's Solution
#include "bits/stdc++.h"

using namespace std;

int main()
{
int n;
cin >> n;
n %= 4;
cout << ((n == 1 || n == 2) ? "NO" : "YES") << endl;
return 0;
}

Editorialist's Solution
#include "bits/stdc++.h"

using namespace std;

int main()
{
int n;
cin >> n;
int sum = (n * (n + 1)) / 2; // formula for sum of first n natural numbers

if (sum % 2 == 0)   // sum is even
cout << "YES";

else                // sum is odd
cout << "NO";

return 0;
}