EVENGAME - Editorial

PROBLEM LINK:

Practice
Contest

Setter: Akash Bhalotia
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Simple

PREREQUISITES:

Maths

PROBLEM:

There are N integers in an array A. Two players take turns alternatively in placing signs (+ or -) before them, and then they all are added. The sign can be placed before any element of the array that has not been assigned a sign yet. All elements must be assigned a sign. Player 1 wins if the resulting sum is even, else player 2 wins. Find out who shall win if they both play optimally.

EXPLANATION:

If the sum of elements of the array A is even then player 1 will win otherwise player 2 will win. It doesn’t matter how signs are placed by the players. Why? let’s see.

Consider the sum of all elements, sum = X. Now suppose in some game the i-th element A_i of the array has (-) sign placed before it, so the new sum, sum' = sum - 2*A_i and as we are subtracting (2*A_i) which is an even quantity, the parity of sum' will be equal to sum. So the parity will not change regardless of you put the (-) sign or (+) sign in front of the element and will be equal to the sum of all elements.

TIME COMPLEXITY:

  • Time complexity per test case is O(N).

SOLUTIONS:

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n;
	long long sum = 0, in;
	cin >> n;
	for(int i = 0; i < n; i ++) {
		cin >> in;
		sum += in;
	}
	if(sum % 2) cout << 2 << "\n";
	else cout << 1 << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	while(t --) {
		solve();
	}

	return 0;
}

VIDEO EDITORIAL:

4 Likes

For those who are not able to understand why we subtract sum - 2*a[i]

basically if we add -ve sign before some element a[i] , then how the sum will change ?

sum changes as => sum - a[i] (this is for we don’t have to include now) - a[i] (this is for we have to subtract too ) => sum - 2*a[i]

ex : 1 3 4 => sum is 8 (1+3+4) now let we add -ve sign before 1
now sum will be => 8 - 1 (as we are not including 1 now ) - 1 (this is for we subtract from our not included sum too) = 8 -2*1 = 6 which is correct (-1+3+4 = 6)

6 Likes

Can anyone help me why this code is wrong? I just started to learn c++ .

using namespace std;

int main()
{
int t,n,x,sum;
cin >> t;
sum = 0
while(t–){
cin >> n;
for(int i = 0; i < n; i ++){
cin >> x;
sum += x;
}
if (sum % 2 == 0) {
cout << “1” << endl;
}
else {
cout << “2” << endl;

   }

}

return 0;

}

1 Like

what is the range of int ?

Use long long int. The maximum sum possible is 10^9 * 10^5 = 10^{14}. Which will not fit in an Integer.
Here’s the bonus. Can you solve the problem just by using int? A: Yes of course. I leave the logic to you :wink:
@ssrivastava990, you could also try :smile:.

Ok. Thank you so much!! :kissing_smiling_eyes:

Adding + or - does not change the overall property of the sum.So you can just calculate the normal sum and still you will get you answer.I did the same way

lmao , use modular addition :slight_smile:

2 Likes

Basically:

We can always rewrite the summation such that it will respect this rule:
“If original number is + or - with an even number, the parity stays the same.”