PROBLEM LINK:
Setter: Manik Goenka
Tester: Aditya Kumar Shaw
Editorialist: Saranya Naha Roy
DIFFICULTY:
EASY
PREREQUISITES:
Basic observations
PROBLEM:
There is an array of integers A[] of size N and two players White and Gale. Each player removes one number from the array in alternate turns until only one number is left. If the number left is even then Mr. White wins otherwise Gale wins. Mr. White always takes the first turn (i.e. Mr. White takes the first turn → Gale takes second turn → Mr. White takes the third turn and so on). You need to find the number of ways in which White can choose the first number such that White wins.
QUICK EXPLANATION:
Determine the optimal choice for each player and find a condition to determine the winner. If Mr. White is the winner, find those numbers which can be removed from the array without violating the condition for White’s win.
EXPLANATION:
At any point in the game, the optimal choice for Mr. White is to remove an odd number from the array, and similarly, the optimal choice for Gale is to remove an even number from the array. Mr. White wins if there is no odd number left in the array as the last number left in the array will always be an even number in this case.
As White and Gale remove one number from the array in alternate turn, in each iteration one odd number and one even number are removed from the array. Let assume there are E even numbers and O odd numbers in the array.
Now if E>O, there will be a point when no odd number will be left in the array hence White wins.
if O>E, there will be a point when no even number will be left in the array hence Gale wins.
if O=E, now if White takes the first turn, the last number left in the array will be an even number hence White wins.
So in this way, we can determine the winner if both play optimally.
If Gale wins we return -1.
If white wins we need to calculate the number of ways in which white can choose the first number. White can choose a number from the array if removing the number from the array does not violate the condition E>O for the rest of the array.
Now if E>O+1, any number removed from the array will result in E>O. So white can choose any number from the array. Hence return the size of the array.
if E=O+1, in this case, if white removes an even number it will become E=O but it will be Gale’s turn to remove a number. So white loses. White has to remove an odd number. Hence we return the count of odd numbers in the array.
if E=O, Here again, white has to remove an odd number to maintain the condition for his win. Hence we return the count of odd numbers in the array.
Time Complexity: O(n)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define f(i, a, b) for (ll i = a; i < b; i++)
#define rf(i, a, b) for (ll i = a; i >= b; i--)
#define rep(i, n) f(i, 0, n)
#define rrep(i, n) rf(i, n - 1, 0)
#define w(t) \
ll t; \
cin >> t; \
while (t--)
#define vi vector<ll>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mii map<ll, ll>
#define mci map<char, ll>
#define inf (ll)(1e18)
using namespace std;
ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};
ll bin_expo(ll x, ll n, ll m)
{
x %= m;
ll res = 1;
while (n)
{
if (n & 1)
res = res * x % m;
x = x * x % m;
n >>= 1;
}
return res;
}
void coder99()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int main()
{
coder99();
// srand(time(0));
w(t)
{
ll n;
cin >> n;
ll a[n], even = 0, odd = 0;
rep(i, n)
{
cin >> a[i];
if (a[i] % 2 == 0)
even++;
else
odd++;
}
ll ans;
if (even < odd)
ans = -1;
else if (even == odd)
ans = odd;
else if (even > odd)
{
if (even == (odd + 1))
ans = odd;
else
ans = n;
}
cout << ans << "\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int T, N;
cin >> T;
while (T--)
{
cin >> N;
//int size = N;
int arr[N];
int odd = 0, even = 0;
for (int i = 0; i < N; ++i)
{ // take N elements as input
cin >> arr[i];
if (arr[i] & 1)
++odd;
else
++even;
}
if (odd == even)
cout << odd << "\n";
else if (odd + 1 < even)
cout << N << "\n";
else if (odd + 1 == even)
cout << odd << "\n";
else
cout << "-1\n";
}
return 0;
}