EVENGAME - Editorial

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

Simple

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)

5 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
@ssrivastava990, you could also try .

Ok. Thank you so much!!

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