PROBLEM LINK:
Setter- Alei Reyes
Tester- Pranjal Jain
Editorialist- Abhishek Pandey
DIFFICULTY:
Easy- Medium
PRE-REQUISITES:
Observations, Game Theory, Grundy Numbers, Sprague Grundy Theorem
PROBLEM:
Treat the number of free moves for a pawn as pile of stones. The game hence reduces to, we can remove at most 2 stones from i'th pile and transfer it to (i+1)'th pile. Stones moved from last pile are lost. We need to tell who wins given the starting configuration.
QUICK-EXPLANATION:
Key to AC- Correlation to Grundy numbers, applying Sprague Grundy theorem, and getting that only piles at even indices (starting from end) matter.
A number of observations are needed.
- If we have a game where we can remove at most K stones per turn, the grundy numbers for that pile repeat at A_i\%(K+1)
- Grundy number of overall game is XOR of all piles, as per Sprague Grundy theorem.
- Lets reverse the piles, so that its easier to denote and understanding. In this new pile, starting from first pile (the last pile in original configuration), only alternate piles matter. This is because, moving on moving stones from other piles, opponent can simply shift them to next pile by mirroring our move. As an example, say our piles were (2,3,1). Reverse them. We get (1,3,2). Any stone we move from the middle pile to last pile, is discarded by the opponent by mirroring our move on last pile.
With respect to above, the solution is simply XORSUM of grundy numbers all such alternate piles. The first player loses iff the XORSUM is 0. An explicit formula can be seen as-
Click to view
reverse(d.begin(),d.end());//Reverse the piles.
int ans=0;
for(int i=0;i< int(d.size());i+=2){
ans^=(d[i]%3);//Refer to first observation.
}
EXPLANATION:
The question was more on observation side. Hence, we will try to prove the observations in the main editorial. Calculation of answer from there, as shown in quick explanation, is trivial.
1. Reducing the problem into game of piles and stones.
This step is the basic foundation of our solution. Make sure to read it carefully.
Lets focus on i'th pawn in initial configuration. Calculate how many moves it can move. We can treat this as number of stones on the i'th pile.
More formally, in our reduction to game of piles and stones, we say that, i'th pile has K stones if the i'th pawn can move K steps in initial/given configuration.
As an example, for below configuration-
...P..P.P....
Our piles will be (3,2,1) as first pawn can move 3 steps before getting blocked, the second pawn can move only 2 steps before being blocked by first pawn and so on.
Now, we need to define the operations.
A player can move a pawn at most 2 steps. Say we are considering i'th pawn. An operation on it will reduce number of steps this pawn can move by at most 2, and increase number of steps (i+1)'th pawn can move by same amount. This is, equivalent to moving at most 2 stones from i'th pile to (i+1)'th pile.
Note that, if current pile is last pile, the stones are removed from the game (as there is no pawn after the last pawn to move on those free cells in original version).
2.If we have a game where we can remove at most K stones per turn, the grundy numbers for that pile repeat at A_i\%(K+1)
Refer to example 2 in the pre-requisite link of Grundy Numbers. Our proof is similar.
Say we have a pile of N stones, and can remove exactly 1 stone from it. Grundy number takes values from 0 (if the first player immediately loses) else mex(Position_i) where Position_i is set of all possible game positions.
Lets analyze this for N=1 to N=4.
At N=0, first player loses. Grundy number is, hence, 0. At N=1, he wins, hence the Grundy Number takes value of 1. At N=2, the first player is bound to lose. This is same game position as have 0 stones at start. Hence, Grundy is equal to 0. For N=3, the first player wins by removing 1 stone, as then player 2 cannot win no matter what.
See the pattern. GrundyNum=0,1,0,1,.....
Lets take example where we can remove at most 2 coins now. This is the situation in our current problem. Grundy numbers for a pile with 0 coins is 0, pile of 1 coins is 1. for a pile of 2 coins, player 1 wins by removing 2 stones - this is a new gaming move/position, hence grundy number is mex(0,1)=2. At N=3, no matter what he does, the second player can win by removing 1 or 2 stones depending on what move player 1 does. Hence, at N=3, player 1 always loses, and its Grundy number is 3 (position equivalent to pile with 0 coins).
If we further work up examples for higher N, we see that GrundyNum=0,1,2,0,1,2,0,1,2... which is basically N\%3
As an exercise, can you work on a formal, or at least intuitional proof for it? The answer is, as usual, in my Chef Vijju’s Corner :D.
3. Starting from end, only alternate piles matter-
Lets say our piles are (2,4,5,1,3). I claim that, piles at position 2 and 4, i.e. with stones 4 and 1, don’t matter. Rest of the piles matter.
Let me denote the pile at i'th position by Pile_i. Say I moved 2 stones from Pile_2 to Pile_3, i.e. from Pile with 4 stones to Pile with 5 stones. The opponent can simple copy my move, and move those two stones from Pile_3 (one with 5 stones initially) to Pile_4 (the one with 1 stones initially).
More formally, if we move stones from non-significant piles, the opponent will simply put them back to a significant pile, which makes it equivalent to us putting stones from first significant pile to the next ourselves.
Also, another interesting question. What if we become stubborn, and keep removing stones only from non significant piles? (Hint: Think in terms of who gets to make the last move).
An alternative perspective is this-
Its a game of Nim in alternate piles, starting from last pile. In case a player moves on the insignificant piles, the winning player can simply copy his move and remove those stones from Nim piles by moving them to next insignificant pile, or eliminating them completely if current pile is last pile. This keeps configuration of Nim piles same, and hence losing player is still in losing position.
Let me summarize the various intuitions on why we are ignoring the insignificant piles -
- If the losing player makes move on these piles, then winner can simply mirror it and move the piles to next insignificant pile, or even eliminate them if current pile was last pile.
- If a player moves on these insignificant piles, then the other player gets to remove the stones, or move them to next insignificant pile. Hence, the other player is guaranteed another move.
4. Wrapping it up-
Once you see it in a perspective of a game of NIM in alternate piles, the problem becomes trivial. We simply start from end, and XOR the grundy numbers of every pile (which is A_i \%3) as in accordance to Sprague Grundy Theorem. If the final XORSUM is 0, player 1 loses, else he wins.
What is more difficult in the question is, getting the perspective. I will admit that once you get that its a game of NIM on alternate piles, its easy to prove things. But the real question is, how to get this observation in first place? For starters, I feel doing game theory questions based on Grundy numbers regularly is the way to go. This was just a game of nim on alternate piles, we never know what next twist is waiting for us there. 
SOLUTION
Click to view
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int mx=300;
char s[mx];
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
int bat(int b,int i){
if(b&(1<<i))return 1;
return 0;
}
int f[(1<<20)+10];
int solve(int b){
if(f[b]!=-1)return f[b];
for(int i=1;i<20;i++){
if(bat(b,i)==1 && bat(b,i-1)==0 && solve(b^(1<<i)^(1<<(i-1)))==0 ){
return f[b]=1;
}
if(i>=2 && bat(b,i)==1 && bat(b,i-1)==0 && bat(b,i-2)==0 && solve(b^(1<<i)^(1<<(i-2)))==0 ){
return f[b]=1;
}
}
return f[b]=0;
}
int main(){
// freopen("secret/sample.in","r",stdin);
// freopen("secret/0.in","r",stdin);
// freopen("secret/0.out","w",stdout);
int t=rint('\n');
assert(1<=t && t<=500);
memset(f,-1,sizeof f);
while(t--){
assert(scanf("%s",s)==1);
int n=strlen(s);
assert(2<=n&&n<=128);
vector<int>d;
int bef=-1;
for(int i=0;i<n;i++){
if(s[i]=='P'){
d.push_back(i-1-bef);
bef=i;
}
}
reverse(d.begin(),d.end());
int ans=0;
for(int i=0;i<int(d.size());i+=2){
ans^=(d[i]%3);
}
if(ans==0)puts("No");
else puts("Yes");
if(n<=20){
int b=0;
for(int i=0;i<n;i++)if(s[i]=='P')b^=(1<<i);
int w=solve(b);
if(ans>0)ans=1;
assert(w==ans);
}
}
return 0;
}
Click to view
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(char ch) {
return string("'")+ch+string("'");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
bool start = true;
string res = "{";
while (first!=last) {
if (!start) {
res += ", ";
}
start = false;
res += to_string(*first);
++first;
}
res += "}";
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
input>>x.F>>x.S;
return input;
}
template <typename A>
istream& operator>>(istream& input,vector<A>& x){
for(auto& i:x)
input>>i;
return input;
}
#ifdef PRINTERS
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
void solve(){
string x;
cin>>x;
int last=-1;
vi temp;
int N=x.size();
for(int i=0;i<N;i++){
if(x[i]=='P')temp.emplace_back(i-last-1),last=i;
}
int xor_sum = 0;
reverse(all(temp));
for(int i=0;i<temp.size();i+=2){
xor_sum^=(temp[i]%3);
}
cout<<(xor_sum?"Yes\n":"No\n");
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
Time Complexity=O(N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER 
1. Proof on Grundy Numbers-
Click to view
The intuition behind this is, that, a position is winning position IFF you can remove some stones such that Grundy number of remaining stones in pile is 0. Meaning, from current position, if you can goto a position with Grundy Number =0, your opponent loses no matter what. Else he wins. If we can remove at most K stones, then if the pile has \leq K coins, we can always win by a new game move. Hence their the Grundy number is equal to number of stones removed by definition of mex() function. Once the pile has K+1 stones, we cannot win and Grundy number is back to 0 (as we cannot goto any position where Grundy number is 0 by removing only K stones). Now, K+1 has grundy number 0. If pile has (K+1)+1 stones, we again come back to starting - we win by removing a single stone. Similar for K+1+i provided i\leq K. This completes the proof.
2. Answer to the interesting observation in section 2.-
Click to view
If we only remove stones from non-significant piles, always the opponent will get the finishing move.
3. Derive Grundy numbers for a single pile, with stones from N=1 to N=10 if you are allowed to remove only 2, 4 or 5 stones at once. Can we get a nice recurrence for it? Why/Why not?
4.Setter’s Notes-
Click to view
Find the distances between each pair of pawns, performing one operation means decreasing one distance and increasing another. The grundy number of the game is the xor sum of distances of even index looking from right to left.
5. Tester’s Explanation for Alternate Piles with an example-
Click to view
Consider …P…P…P.
Here, we have 4 piles, of sizes 2,3,4,1.
Now, an operation consists of moving 1 or 2 stones from pile i to pile (i+1).
Mirroring an operation means, if opponent has moved k stones from i to (i+1), I move k stones from (i+1) to (i+2).
So, in the example above, the piles of importance are piles having 2 stones and 4 stones. If someone moves from pile having 3 stones, opponent will mirror the operation by moving to those stones to last pile.
So, instead of considering the game as “move all stones to last pile”, we can consider it as “move all stones to odd indices”.
So, we get two piles to consider 2 and 4 where we can remove either 1 or 2 stones. This gives (2%3)^(4%3).
6. An alternate intuition on insignificant piles-
Click to view
This one is a personal derivation. Feel free to point any errors/doubts.
When you make a move on an insignificant pile, your opponent is always guaranteed a move. Also, on making a move on insignificant pile, opponent can put those stones onto another insignificant pile. What happens if we exhaust stones at all significant piles? The winner in this case, is already fixed. Hence, we can model it has, remove stone from every significant pile such that you get the last move in it. This is same as getting last move when the insignificant piles were absent.
7. Related Problems-
