GMSTN - Editorial

PROBLEM LINK: Better call Saul!

Setter: Yashodhan Agnihotri
Tester: Nishit Sharma , Aman Singhal

DIFFICULTY:

EASY

PREREQUISITES:

Games, Parity.

PROBLEM:

Given N stone piles with Ai stones in each pile, after X moves between two players, in which they remove one pile per move, find the winner of the game, if both of them play optimally.
Winner of the game depends on the final Sum parity of the stone piles.

EXPLANATION:

Let odd be the number of piles with odd-number of stones in it and even be the number of piles with even-number of stones in it. Here, remaining refers to N-X piles or the remaining number of piles after X moves.

Case 1

The player that plays last can win if there are both odd and even piles remaining.

Case 2

If Walter makes the last move and the remaining piles are even numbered, then Jesse should try to remove all odd or all even piles.

Case 3

If Jesse makes the last move and remaining are even, then Walter cannot win.

Case 4

If remaining are odd, Walter should try to remove all the even piles.

After including all the above cases, solution will run in O(n) complexity (due to counting of even and odd values).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, x, i;
		cin >> n >> x;
		vector<int> a(n);
		int even = 0, odd = 0, ans = -1;
		for (i = 0; i < n; i++) {
			cin >> a[i];
			if (a[i] & 1)odd++;
			else even++;
		}
		if (x >= 2 * odd)ans = 0;
		else if (x >= 2 * even)ans = (n - x) % 2;
		else ans = x % 2;
		if (!ans) cout << "Jesse\n";
		else cout << "Walter\n";
	}

	return 0;
} 
Tester's Solution (C++)
//#pragma GCC optimize "trapv"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define vll vector<ll>
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
ll add(ll x, ll y) {ll res = x + y; return (res >= MOD ? res - MOD : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= MOD ? res % MOD : res);}
ll sub(ll x, ll y) {ll res = x - y; return (res < 0 ? res + MOD : res);}
ll power(ll x, ll y) {ll res = 1; x %= MOD; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}
ll mod_inv(ll x) {return power(x, MOD - 2);}

using namespace std;

int main()
{
    quick;
    int t;
    cin >> t;
    while (t--)

    {
        int n, x;
        cin >> n >> x;
        int a[n];
        int cntodd = 0;
        fab(0, n, i) {
            cin >> a[i];
            cntodd += (a[i] % 2);
        }
        int cnteven = n - cntodd;
        int walterturns = (x + 1) / 2;
        int jesseturns = (x / 2);

        if (x % 2) {
            if ( ((n - x) % 2 and cntodd > jesseturns) or ( (n - x) % 2 == 0 and (cnteven > jesseturns and cntodd > jesseturns) ) )
                cout << "Walter" << endl;
            else
                cout << "Jesse" << endl;
        }
        else {
            if (((n - x) % 2 and (cnteven > walterturns)  ) or ( (n - x) % 2 == 0 ) )
                cout << "Jesse" << endl;
            else
                cout << "Walter" << endl;
        }
    }
    return 0;
}
Tester's Solution (Python)
import math
T=int(input())
for _ in range(T):
    n,x=map(int,input().split())
    A=list(map(int,input().split()))
    ne=0
    no=0
    for i in A:
        if (i%2==0):
            ne=ne+1
        else:
            no=no+1
    flag=0
 
    if (no<=x//2):
        flag=1
 
    elif (ne<=x//2):
        flag=(n-x+1)%2
 
    else:
        flag=(x+1)%2
    
 
    if (flag==1):
        print("Jesse")
    else:
        print("Walter")

For doubts, please leave them in the comment section, I’ll address them.

6 Likes

Proofs for all cases would be helpful. :slightly_smiling_face:

1 Like

Can you prove how do we arrive at these conditions ?
And how would the due course follow ?

All these cases are cumulation of various possibilities, which are not many.
Remaining Piles - Odd/Even, Last one to move, Probable Parity of sums.

All the cases are self explanatory, aside of these, no other cases are left to be included.

Am I the only one who used dp for this?

  • base case: (number of odd piles) is odd ? Walter wins : Jesse wins
1 Like

Can you share your solution

Yes, it indeed can be solved by DP, though it’s not really intuitive.

Recursive dp: https://www.codechef.com/viewsolution/39307894

1 Like

if (x >= 2 * odd)
ans = 0;
else if (x >= 2 * even) ans = (n - x) % 2;
else ans = x % 2;

can anyone explain this condition. i mean what is the logic behind this conditions?

This is a simplified implementation of the above mentioned 4 cases.

Thanks for giving such neat and clean solution :):

Why is this not getting a MLE? I think the constraints on N was till 10^5. Am I missing something here?

I’ll look into this. Technically , this should be getting an MLE.

3 Likes

@zappelectro Can you share your thought process while you framed the 4 base cases? Couldn’t really think as expected

Well, tbh when I set the problem for starters, I just took N = 5, and tried all possible combination of odd and even for moves 1,2,3,4 each. Did a lot of casework, and simplified them into the 4 basic cases mentioned above.

There was a bad case preparation on my part due to which the above solution passed.
Sorry for the inconvenience. I’ll add a strong case for the practice section.

@zappelectro nice question just correct the explanation of 2nd case, it should be 2 and not 3

  1. For the case (x >= 2*odd):
    This means that if Jesse is able to remove all the odd numbers from the array and therefore the remaining numbers are all evens and hence the sum is even, so Jesse wins.
  2. For the case (x >= 2*even):
    This also goes a similar way. This means that either Jesse or Walter can remove all the evens from the array. Now if after removing all the evens from the array, the sum can either be even or odd. So, if the remaining sum is odd, then Walter will remove all the evens or if the remaining sum is even, then Jesse will remove all the evens.
  3. This case is when no one can remove all the odds or all the evens. Then here only that person wins who has the chance to make the last move.

thanks for your detailed explanation

That was very neatly explained @smit5300 :partying_face: