ADAPWNS - Editorial

PROBLEM LINK:

Div1
Div2
Practice

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. :slight_smile:

SOLUTION

Setter

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;
}

Tester

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 :smiley:

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-

3 Likes

Fantastic editorials!

I guess I have to read about grundy numbers first :slight_smile:

The way of denoting piles for tester and setter is different… causing confusion…other than that the editorial is great.

1 Like

hello, can you please help me understand this alternative thing in more simpler way.

I tried to understand this by myself but can’t(no problem in understanding grundy numbers)

And also what will happen if we apply Sprague Grundy Theorem not alternative but for all piles.

@vijju What do you mean by non-significant piles, and with respect to which player ,current or the opponent ?

One of the sections of argument above says:
When you make a move on an insignificant pile, your opponent is always guaranteed a move.

But the argument doesn’t seem relevant.
One could say: “When you make a move on a pile of three or more, your opponent is always guaranteed a move.” The logic doesn’t seem to help.

In some sense what matters is that after a move from an alternating zeros position of the form 0,x,0,y,0,z,0 then a mirroring move will return to one of these alternating zeros positions.

When on a winning strategy, the idea of mirroring the opponent’s move after a move from an insignificant pile is certainly correct. But seems to be tricky to find the reason.

Thank you :slight_smile:

Hey,

If I recall right, both of them used “Distance this pawn can move” as number of stones on that pile. Can you point where you feel its different? :slight_smile:

And also what will happen if we apply Sprague Grundy Theorem not alternative but for all piles.

Did not get time to test it, but I feel it should give wrong answer.

Are you clear with the fact that, the opponent always gets a move if you move on insignificant piles?

The last pile is always significant. Now from last pile, take every alternating piles. These are the piles which actually determine game, as when all stones are on insignificant piles, the game is already decided. (The player forced to do a move on insignificant pile will always lose as opponent will always have a corresponding move.)

But seems to be tricky to find the reason.

I very much agree to that. Only for this reason, ADAPWNS was the second last editorial written (more difficult problems had their editorials ready beforehand) because I needed more time to get an intuition.

My intuition was that, once all stones are on those insignificant piles, the player who makes first move on those piles has to lose, as his opponent will always have a move of putting stones on next insignificant pile/eliminating them (if its the last pile). Thats true even if that pile has < 3 stones.

Your mirroring point seems correct. :slight_smile:

And yes, I am always taking feedback/alternate explanations which can better the editorial. After interacting with one of the contestants, I added section 6 in my bonus corner. In case you also have anything else, please let us all know - everyone is always welcome to discuss any alternate solutions especially if they can be better than my explanation :slight_smile:

I liked that editorialist :wink:

May god give you patience. I was new then, I wrote a frickin tutorial on how to solve such Qs in middle of editorial. I think I should remove that part someday lol

No, not moved to another post. Remove is remove.

thanks @vijju. i think i understand what you were trying to say about alternative thing.

Added more links to the editorial so its easier for people who are unable to get a perspective of “Only Alternating Piles matter”.

Intro to Staircase Nim + Editorial for HackerRank "Move the Coins" - Codeforces.
Refer this in order to understand how we are deciding significant/insignificant positions