Bogi’s Pile Game
National Olympiad — National round (2010 season)
Submission name: bogig.cpp
Problem summary
Players alternate reducing exactly one pile to the size of another, strictly smaller pile currently present. The player unable to move loses. Determine whether the first player can force a win.
Input
n followed by n pile sizes.
Output
1 for a first-player win, otherwise 0.
Constraints
2 ≤ n ≤ 20; each pile has at most 1000000000 stones.
Worked example
An independently prepared example for this explanation.
Input
4 1 2 3 4
Output
0
Solution analysis
- Only equality and ordering of pile sizes matter. Sort the piles and encode a bit at position i (1≤i<n) when sizes i−1 and i differ. This mask describes the ordered block sizes of equal piles, using at most 19 effective bits.
- For a move select the final position i of a higher-size block and the final position j of a lower-size block. The moved pile is deleted at i and inserted after j, equal to the target block. Bits up to j stay fixed, bit j+1 becomes zero, bits j+1 through i−1 shift one place right, and bits above i stay fixed.
- Memoize whether a mask is winning. A state is winning iff some move reaches a losing mask. Mask zero has every pile equal and no legal move. The sample with four distinct sizes is losing; the official second example with sizes 1,1,1,2,3 is winning.
Why it works
Order-preserving renaming of distinct pile sizes preserves all legal reductions, so the boundary mask is a complete game state. Moving the last representative of a source block to the end of the target block represents every possible move between sizes, and the bit transformation exactly describes the resulting sorted sequence. The sum of canonical ranks strictly decreases, so the state graph is acyclic. The standard winning/losing recurrence is therefore correct by induction along this order.
Watch out. Repeated pile sizes must form one block. An empty pile is not an automatic target unless a size-zero pile is already present. Bit zero is unused.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long>piles(n);
for(long long&value:piles){
cin>>value;
}
sort(piles.begin(),piles.end());
int initial=0;
for(int i=1;i<n;i++){
if(piles[i]!=piles[i-1]){
initial|=1<<i;
}
}
vector<signed char>memo(1<<n,-1);
memo[0]=0;
function<bool(int)>winning=[&](int mask){
if(memo[mask]!=-1){
return memo[mask]!=0;
}
for(int i=1;i<n;i++){
if(i!=n-1&&(mask&(1<<(i+1)))==0){
continue;
}
for(int j=0;j<i;j++){
if((mask&(1<<(j+1)))==0){
continue;
}
int low=(1<<(j+1))-1;
int middle=((1<<i)-1)^low;
int high=~((1<<(i+1))-1);
// Remove the source slot and insert an equal target slot.
int next=(mask&low)|((mask&middle)<<1)|(mask&high);
if(!winning(next)){
memo[mask]=1;
return true;
}
}
}
memo[mask]=0;
return false;
};
cout<<(winning(initial)?1:0)<<'\n';
}