Divisibility Removal Game
Autumn Tournament (2016)
Submission name: div.cpp
Problem summary
Players X and Y alternately remove one distinct residue from a set. After exactly K removals X wins if the remaining sum is divisible by P; otherwise Y wins. Determine the winner under optimal play, for either starting player.
Source clarification. The pairing characterization and necessity induction follow the official editorial: https://infos.infosbg.com/files/Contests/ETI/2016/A/analyses/div_analysis.pdf
Input
T games; each gives N K P, starting letter X or Y, and N distinct residues.
Output
One line containing the T winning letters without separators.
Constraints
1≤K≤N≤5000; P≤10^18; 0≤ai<P, all distinct.
Worked example
Original statement sample, with whitespace restored where PDF extraction joined numbers.
Input
3 5 3 7 X 1 2 3 4 6 8 4 13 Y 5 10 6 11 2 8 9 3 6 1 12 X 1 4 5 7 9 11
Output
XYX
Solution analysis
- If K=N, the final sum is zero. Otherwise Y wins whenever Y makes the last move: at least two distinct choices remain and at most one can leave a divisible sum. For K=1 with X moving, directly check whether the residue of the total is present.
- For K>1 with X moving last, N−K must be even. A winning pairing strategy uses pairs summing to r modulo P, where r·((N−K)/2)≡0 mod P. Write q=gcd(P,(N−K)/2); only r=0,P/q,...,(q−1)P/q are candidates.
- For each r count values lacking a different partner. If Y starts, all values must pair; if X starts, exactly one may remain unpaired and X removes it first. Sort once and use two-pointer pair matching separately on values≤r (sum r) and values>r (sum P+r). In the first sample, r=0 and X removes the unpaired residue, then answers each Y move with its pair.
Why it works
Pairing suffices because X can always remove the partner of Y’s choice, leaving an even number of equal-sum pairs whose total is divisible by P. For necessity, the official editorial gives an induction: for every admissible r retain two unmatched witnesses; their union has at most2q≤N−K elements, so Y can remove a value outside it. X can remove only one witness, preserving a failed pairing until the final two moves. The simple endgame cases cover all excluded parities.
Watch out. Self-pairing is forbidden because values are distinct and a residue cannot pair with itself. Keep residues in long long; P+r≤2·10^18 is safe, but the complete input sum need not fit.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int unmatched(const vector<long long>&a,int left,int right,long long target){
int bad=0;
while(left<=right){
if(left==right){
bad++;
break;
}
long long sum=a[left]+a[right];
if(sum==target){
left++;
right--;
}
else if(sum<target){
bad++;
left++;
}
else{
bad++;
right--;
}
}
return bad;
}
int main(){
int tests;
cin>>tests;
while(tests--){
int n,k;
long long p;
char first;
cin>>n>>k>>p>>first;
vector<long long>a(n);
long long sum=0;
for(long long&value:a){
cin>>value;
sum=(sum+value)%p;
}
sort(a.begin(),a.end());
bool wins=false;
bool xLast=(first=='X')==(k%2==1);
if(k==n){
wins=true;
}
else if(!xLast){
wins=false;
}
else if(k==1){
wins=binary_search(a.begin(),a.end(),sum);
}
else if((n-k)%2==0){
long long q=gcd(p,static_cast<long long>((n-k)/2));
for(long long i=0;i<q&&!wins;i++){
long long r=i*(p/q);
int split=upper_bound(a.begin(),a.end(),r)-a.begin();
// Modular pairs cannot cross these two sorted ranges.
int bad=unmatched(a,0,split-1,r);
bad+=unmatched(a,split,n-1,p+r);
wins=bad==(first=='X'?1:0);
}
}
cout<<(wins?'X':'Y');
}
cout<<'\n';
}