A newbie oriented tutorial for ABC278G — Generalized Subtraction Game

Revision en3, by CristianoPenaldo, 2022-11-20 13:29:34

Details will 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.

The idea is from official. This blog is about the implementation.

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)