PROBLEM LINK:
[Contest: IYWT2021 - If you win this, Bhel Puri Treat] (Contest Page | CodeChef )
Author: Meenaksshi S
Tester: Meenaksshi S
Editorialist: Meenaksshi S
DIFFICULTY:
EASY
PREREQUISITES:
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;
}