A newbie oriented tutorial for G — Generalized Subtraction Game

Revision en1, by CristianoPenaldo, 2022-11-20 13:23:46

Idea: To be updated next week. I am a little busy now, so please do not downvote me. If you are interested or confused, you can comment or chat with me.

My submission: submission

My code here:

#include<bits/stdc++.h>
using namespace std;
#define BIT(x, i) (((x) & (1 << (i))) >> (i))
#define DEBUG 0
#define DEBUG_INTERACTIVE 0

constexpr int C = 11, MAXN=2005; //Since N <= 2000, nim number <= 2000, so we only need to scan 1<<0 to 1<<11.
int n, l, r;
int sg[MAXN]; //sg number for 1-n
int f[MAXN][MAXN]; 
//f[i][j] If we want to get sg number j from [1, i], where should I cut?
//For example, if sg(i) = 4 and get sg number 3 after cutting [j, k], then f[i][3] = j;

int nim(const vector<int>& v, int* index, int* value_after_change){
    //input: 
    //v: A vector of stones.
    //index and value_after_change: If the XOR sum of v is 0, then index remains unchanged. we modify v[*index]
    //to *value_after_change to guarantee that the XOR sum of v after modification is 0.
    //Output:
    //The XOR sum of v (current v)

    //Example1:
    //vector<int> v = {1, 4, 3};
    //int index, value_after_change;
    //int value = nim(v, &index, &value_after_change);
    //cout << value << " " << index << " " << value_after_change << "\n"; //6 1 2
    //value = 1^4^3 = 6;
    //change 4->2, 1^2^3=0
    
    //Example2:
    //vector<int> v = {1, 2, 3};
    //int index, value_after_change;
    //int value = nim(v, &index, &value_after_change);
    //cout << value << " " << index << " " << value_after_change << "\n"; //0 32763 -1204770170
    //1^2^3 = 0. You cannot modify any number, then index and value_after_change are uninitialized random numbers (may not be 32763 -1204770170)

    int sz = (int)v.size();
    vector<int> ones[C+1];
    int res = 0;
    for(int b = 0; b <= C; ++b){
        for(int i = 0; i < sz; ++i){
            if(BIT(v[i], b)){
                ones[b].push_back(i);
            }
            if(!b) res ^= v[i]; //Calculate the XOR sum, also known as the Nim sum. Remember only xor once.
        }
    }
    if(res == 0) return res;
    bool flipped = false;
    *value_after_change = 0;
    int choosed = -1; //FIX
    for(int b = C; b >= 0; --b){
        if(BIT(res, b)){
            if(!flipped){
                choosed = b;//FIX
                flipped = true;
                *index = ones[b][0]; //Never overflows, think out why?
            }else{
                *value_after_change += ((!BIT(v[*index], b)) << b);
            }
        }else if(flipped){
            (*value_after_change) += (v[*index] & (1 << b));
        }
    }
    for(int i = choosed+1; i <= C; ++i){ //FIX
        *value_after_change += (v[*index] & (1<<i)); //FIX
    } //FIX
    return res;
}

void sgdp(bool debug){ //dynamic programming to calculate sprague-grundy numbers
    //The following code is unnecessary because sg is global variable.
    //for(int i = 0; i <= l-1; ++i){
    //    sg[i] = 0; //Nowhere to fetch, have to lose, sg number is 0.
    //}
    for(int len = l; len <= n; ++len){
        set<int> mex;
        for(int i = 1; i <= len-l+1; ++i){
            //We fetch [i, i+l-1]
            int sgleft = sg[i-1]; //sg[0] is defined
            int sgright = sg[len-i-l+1];
            int sgall = sgleft ^ sgright; //Grundy theorem!!!
            f[len][sgall] = i;
            mex.insert(sgall);
        }
        int t = 0; 
        while(mex.count(t)) ++t;
        sg[len] = t;
    }
    //DEBUG
    if(!debug) return;
    for(int len = l; len <= n; ++len){
        printf("sg[%d]==%d\n", len, sg[len]);
        for(int k = 0; k < sg[len]; ++k){
            printf("f[%d][%d]==%d\n", len, k, f[len][k]);
        }
        printf("\n");
    }
}

int main(int argc, char** argv){
    if(DEBUG){
        //freopen(argc == 1?"test1.txt":argv[1], "r", stdin);
    }else if(DEBUG_INTERACTIVE){
        ; //DO NOTHING
    }else{
        cin.tie(0) -> sync_with_stdio(0);
    }
    cin >> n >> l >> r;
    //The first case: r is large enough:
    //Prefix (length <= l-1), Middle (length==r), Appendix (length <= l-1)
    int a = 1, b = 1; //Ready to receive moves from the AI.
    if(r + 2 * l - 2 >= n && l + r - 1 <= n){
        //Killer move
        cout << "First" << endl;
        cout << l << " " << r << endl;
        cin >> a >> b;
        //AI fails.
        return 0;
    }
    //The second case: Mimicking
    if(l != r || n % 2 == l % 2){
        //According to the tutorial, we can use the first move to separate [1-n] into two symmetric parts.
        int tmp = r;
        while((n - tmp) % 2) --tmp; //Don't be scary, it is O(1). 
        //Such tmp is always valid. If l != r, one of {r-1, r} is ok. Otherwise if l==r, r is eligible for tmp.
        int interval = (n - tmp)/2;
        cout << "First" << endl;
        cout << interval+1 << " " << tmp << endl;
        //Here we cut the interval [1, n] into two parts: [1, interval], [interval+tmp+1, n]
        //interval == n-interval-tmp.
        while(a || b){
            cin >> a >> b;
            if(a == 0 && b == 0){
                return 0;
            }
            if(a <= interval){
                //cout << a+interval+tmp << " " << b+interval+tmp << endl; //BUG. The second parameter is the LENGTH, not the ENDING POINT.
                cout << a+interval+tmp << " " << b << endl;
            }else{
                //cout << a-interval-tmp << " " << b-interval-tmp << endl; //BUG. The second parameter is the LENGTH, not the ENDING POINT.
                cout << a-interval-tmp << " " << b << endl;
            }
        }
        return 0;
    }
    //The third case: l == r && n % 2 != l % 2. We cannot mimick. No matter where we choose [x, x+y-1], We cannot separate [1, n]
    sgdp(DEBUG || DEBUG_INTERACTIVE);
    set<pair<int, int>> intervals = {{1, n}};
    bool turn = true, initial = true;
    if(sg[n] == 0) {
        cout << "Second" << endl;
        turn = false;
    }else{
        cout << "First" << endl;
    }
    while(a || b){
        if(turn){
            if(!initial){
                //Use {a, a+b-1} to separate intervals
                pair<int, int> ab = {a, a+b-1};
                auto it = intervals.upper_bound(ab); 
                if(it==intervals.end() || it->first > ab.first) it = prev(it);//Always valid
                int fi = it->first, se = it->second;
                if(DEBUG || DEBUG_INTERACTIVE) {
                    for(auto pa: intervals){
                        cout << "[Intervals1]" << pa.first << " " << pa.second << "\n";
                    }
                    printf("DEBUG1: it=={%d, %d}, ab=={%d, %d}\n", fi, se, ab.first, ab.second);
                }
                if(ab.first-1 >= it->first){
                    intervals.insert({it->first, ab.first-1});
                }
                if(ab.second+1 <= it->second){
                    intervals.insert({ab.second+1, it->second});
                }
                intervals.erase({fi, se});
            }
            int isz = (int)intervals.size();
            vector<int> v(isz);
            vector<pair<int, int>> vp(intervals.begin(), intervals.end()); //This is bad, but convenient...
            if(DEBUG || DEBUG_INTERACTIVE) {
                for(int i = 0; i < isz; ++i) {
                    printf("DEBUG_PLACE1 <SG should NOT be 0>: vp[%d]=={%d, %d}, gr==%d\n", i, vp[i].first, vp[i].second, sg[vp[i].second - vp[i].first + 1]);
                }
            }
            for(int i = 0; i < isz; ++i){
                v[i] = sg[vp[i].second - vp[i].first + 1];
            }
            int index = -1, value_after_change = -1;
            nim(v, &index, &value_after_change); //I will never make nim(v, &index, &value_after_change)==0 here!
            int cutplace = f[vp[index].second - vp[index].first + 1][value_after_change];

            if(DEBUG || DEBUG_INTERACTIVE) {
                for(int i = 0; i < isz; ++i) printf("v[%d]==%d, index==%d, value_after_change==%d\n", i, v[i], index, value_after_change);
                cout << vp[index].first + cutplace - 1 << " " << l << " AI" << endl;
            }
            else cout << vp[index].first + cutplace - 1 << " " << l << endl;

            //Also remember to separate intervals!
            pair<int, int> ab = {vp[index].first + cutplace - 1, vp[index].first + cutplace + l - 2};
            auto it = intervals.upper_bound(ab); //Always valid
            if(it==intervals.end() || it->first > ab.first) it = prev(it);
            int fi = it->first, se = it->second;
            if(DEBUG || DEBUG_INTERACTIVE) {
                for(auto pa: intervals){
                    cout << "[Intervals2]" << pa.first << " " << pa.second << "\n";
                }
                printf("DEBUG2: it=={%d, %d}, ab=={%d, %d}\n", fi, se, ab.first, ab.second);
            }
            if(ab.first-1 >= it->first){
                intervals.insert({it->first, ab.first-1});
            }
            if(ab.second+1 <= it->second){
                intervals.insert({ab.second+1, it->second});
            }
            intervals.erase({fi, se});
            if(DEBUG || DEBUG_INTERACTIVE) {
                int i = 0;
                for(pair<int, int> pa: intervals) {
                    printf("DEBUG_PLACE2 <SG should be 0>: i==%d, {%d, %d}, sg==%d\n", i, pa.first, pa.second, sg[pa.second-pa.first+1]);
                    ++i;
                }
            }
        }else{
            cin >> a >> b;
        }
        turn  = !turn;
        initial = false;
    }
    if(a == -1 && b == -1) return 0;
}

Acknowledgment: ABalobanov, Nyaan.

Tags game theory, sg function

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English CristianoPenaldo 2022-11-20 13:29:34 6
en2 English CristianoPenaldo 2022-11-20 13:25:54 139
en1 English CristianoPenaldo 2022-11-20 13:23:46 9944 Initial revision (published)