Bit mask DP

This is the lastest question of the weekly contest of June 12, 2021. It is pretty hard if you don’t know the bit mask DP before.

1900. The Earliest and Latest Rounds Where Players Compete

Basic idea:

Using the bit mask to represent the exist player. If that specified bit is 1, it means we have a plyer at that position.

0, 1, 2, 3, will have 1111.

// find special cases:
        // 1) a pk b, this is the basecase, return
        // 2) a is in that round, a win
        // 3) b is in that round, b win
        // 4) the middle if the size of plays is odd
        // 5) not a and not b in that round, collect it into candidates.

We will have the above 5 cases to consider to update the state. Then we can use dfs + memo to solve the problem

int min_ = 28, max_ = 0;
class Solution {
public:
    int a, b, n;
    void dfs(int state, int round, set<pair<int, int>>& memo) {
        pair<int, int> key = {state, round};
        if (memo.find(key)!= memo.end()){
            return;
        }
        memo.insert(key);
        vector<int> f;
        for (int i =0; i < n; ++i)
            if (state & (1 << i))f.push_back(i);
         
        const int m = f.size();
        if (m == 0) return;
        int newstate = 0;
        vector<pair<int, int>> candidates;
        int i = 0, j = m - 1;
        // find special cases:
        // 1) a pk b, this is the basecase, return
        // 2) a is in that round, a win
        // 3) b is in that round, b win
        // 4) the middle if the size of plays is odd
        // 5) not a and not b in that round, collect it into candidates.
        while (i <= j){
            // 1)
            if (f[i] == a && f[j] == b){
                 min_ = min(min_, round);
                 max_ = max(max_, round);
                return;
            // 4)
            } else if (i==j){
                newstate |= (1 << f[i]); 
                break;
            // 2)
            } else if (f[i] == a || f[j] == a){
                newstate |= (1 << a);
            // 3)
            } else if (f[i] == b || f[j] == b){
                 newstate |= (1 << b);
            // 5()
            } else {
                candidates.emplace_back(f[i], f[j]);
            }
            i++; j --;
        }
        const int nn = candidates.size();
        int thisstate;
        if (nn==0) return dfs(newstate, round + 1, memo);
        // power set of candidates to check all the possibilities.
        for (int k = 0; k < (1 <<nn); ++k ) {
            thisstate = newstate;
            for (int j = 0; j < nn; ++j) {
                if (k &(1<<j)) {
                    thisstate |= (1 <<candidates[j].second);
                } else{
                    thisstate |= (1 <<candidates[j].first);
                }
            }
            dfs(thisstate, round + 1,memo);
        }
    }
    vector<int> earliestAndLatest(int n, int a, int b) {
        this-> n = n;
        // chaneg to 0 index
        this-> a = min(a, b) - 1;
        this-> b = max(a, b) - 1;
        min_ = 28, max_ = 0;
        int state = (1 << n) - 1;
        set<pair<int, int>> memo;
        dfs(state, 1, memo);
        return {min_, max_};
    }
};

Thanks for reading. Hope it is helpful to you.