Game Theory - Calculation Techniques

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute Grundy numbers on a directed acyclic graph (DAG).
5
// Then XOR across multiple tokens (independent components) to decide the winner.
6
// Input format (example):
7
// n m
8
// m lines: u v (edge u -> v)
9
// t
10
// t lines: start_node_of_each_token
11
// Nodes are 0..n-1
12
13
vector<vector<int>> gph;
14
vector<int> grundy;
15
vector<char> vis;
16
17
int mex_from_used(vector<int>& neighGr){
18
    // Compute mex of small set using boolean array
19
    int mx = (int)neighGr.size();
20
    // mex bounded by size of set; we can allocate mx+1
21
    vector<char> used(mx + 1, 0);
22
    for (int v : neighGr) if (v <= mx) used[v] = 1;
23
    for (int i = 0; i <= mx; ++i) if (!used[i]) return i;
24
    return mx + 1; // fallback (rare)
25
}
26
27
int dfs_grundy(int u){
28
    if (vis[u]) return grundy[u];
29
    vis[u] = 1;
30
    vector<int> childG;
31
    childG.reserve(gph[u].size());
32
    for (int v : gph[u]){
33
        childG.push_back(dfs_grundy(v));
34
    }
35
    grundy[u] = mex_from_used(childG);
36
    return grundy[u];
37
}
38
39
int main(){
40
    ios::sync_with_stdio(false);
41
    cin.tie(nullptr);
42
43
    int n, m; if(!(cin >> n >> m)) return 0;
44
    gph.assign(n, {});
45
    for (int i = 0; i < m; ++i){
46
        int u, v; cin >> u >> v;
47
        gph[u].push_back(v);
48
    }
49
    int t; cin >> t;
50
    vector<int> tokens(t);
51
    for (int i = 0; i < t; ++i) cin >> tokens[i];
52
53
    grundy.assign(n, 0);
54
    vis.assign(n, 0);
55
56
    // Compute Grundy for all token start nodes (others lazily if reachable)
57
    int xorsum = 0;
58
    for (int s : tokens){
59
        xorsum ^= dfs_grundy(s);
60
    }
61
62
    cout << (xorsum ? "First" : "Second") << " player wins\n";
63
64
    // Optional: construct a winning move if First wins
65
    if (xorsum){
66
        // Find a token and a move that makes XOR zero
67
        for (int i = 0; i < t; ++i){
68
            int u = tokens[i];
69
            int gu = grundy[u];
70
            // We need a child v with grundy[v] == gu ^ xorsum
71
            int need = gu ^ xorsum;
72
            for (int v : gph[u]){
73
                if (grundy[v] == need){
74
                    cout << "Winning move: move token #" << i << " from node " << u << " to node " << v << "\n";
75
                    return 0;
76
                }
77
            }
78
        }
79
        // If not found (shouldn't happen on DAG with correct SG), we did something wrong.
80
        cout << "No explicit winning move found (check graph acyclicity).\n";
81
    }
82
    return 0;
83
}
84

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Subtraction game: from a heap of size n, you may remove any s in S (s <= n).
5
// We compute Grundy values g[0..LIM] bottom-up, detect an eventual period,
6
// and then answer large queries by mapping to preperiod + (n - preperiod) % period.
7
8
static const int VERIFY_MULTIPLIER = 5; // check multiple periods to avoid false positives
9
10
// Try to find the smallest period p such that seq[i] == seq[i-p] for all i in [start, end)
11
int find_period(const vector<int>& seq, int start){
12
    int N = (int)seq.size();
13
    for (int p = 1; start + p < N; ++p){
14
        bool ok = true;
15
        for (int i = start + p; i < N; ++i){
16
            if (seq[i] != seq[i - p]) { ok = false; break; }
17
        }
18
        if (ok) return p;
19
    }
20
    return -1;
21
}
22
23
int main(){
24
    ios::sync_with_stdio(false);
25
    cin.tie(nullptr);
26
27
    int k; cin >> k; // size of S
28
    vector<int> S(k);
29
    for (int i = 0; i < k; ++i) cin >> S[i];
30
    sort(S.begin(), S.end()); S.erase(unique(S.begin(), S.end()), S.end());
31
    int M = S.back();
32
33
    // Choose a reasonable limit to observe periodicity (tunable per problem)
34
    // Often 2e5..5e5 is enough for competitive programming.
35
    int LIM = max(1000, M * 400); // heuristic upper bound
36
37
    vector<int> g(LIM + 1, 0);
38
    for (int n = 1; n <= LIM; ++n){
39
        // gather reachable Grundy values
40
        // mex is at most |S|, so use small boolean array
41
        vector<char> used(k + 1, 0);
42
        for (int s : S){
43
            if (s > n) break;
44
            int val = g[n - s];
45
            if (val <= k) used[val] = 1;
46
        }
47
        int m = 0; while (m <= k && used[m]) ++m;
48
        g[n] = m;
49
    }
50
51
    // Detect period after a warm-up window (start >= M)
52
    int start = max(M * 3, 50);
53
    start = min(start, LIM / 2); // ensure room
54
55
    // Strengthen detection: require repetition to hold over last window of size W
56
    int period = -1;
57
    for (int trial = start; trial <= start * 2 && trial < LIM; trial += max(1, M)){
58
        int p = find_period(g, trial);
59
        if (p == -1) continue;
60
        // verify over several periods
61
        int end = LIM;
62
        bool ok = true;
63
        for (int i = trial + p; i < end; ++i){
64
            if (g[i] != g[i - p]) { ok = false; break; }
65
        }
66
        if (ok) { period = p; start = trial; break; }
67
    }
68
69
    int q; cin >> q;
70
    while (q--){
71
        long long n; cin >> n;
72
        int ans;
73
        if (period == -1 || n <= LIM){
74
            // fall back to table if within range or no period found
75
            long long idx = min<long long>(n, LIM);
76
            ans = g[(int)idx];
77
        } else {
78
            if (n < start) ans = g[(int)n];
79
            else {
80
                long long idx = start + ( (n - start) % period );
81
                ans = g[(int)idx];
82
            }
83
        }
84
        cout << ans << "\n";
85
    }
86
    return 0;
87
}
88

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// We have m piles; pile i has size a[i] and its own subtraction set S_i.
5
// Compute Grundy for each pile (with small DP up to its size or via memo), XOR to decide winner,
6
// and if winning, output one move that makes the XOR zero.
7
8
int main(){
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int m; cin >> m;
13
    vector<int> A(m);
14
    vector<vector<int>> Sets(m);
15
    int maxA = 0;
16
    for (int i = 0; i < m; ++i){
17
        int sz, k; cin >> sz >> k; // pile size and number of allowed moves
18
        A[i] = sz; maxA = max(maxA, sz);
19
        Sets[i].resize(k);
20
        for (int j = 0; j < k; ++j) cin >> Sets[i][j];
21
        sort(Sets[i].begin(), Sets[i].end());
22
        Sets[i].erase(unique(Sets[i].begin(), Sets[i].end()), Sets[i].end());
23
    }
24
25
    // For simplicity and clarity, compute each pile's Grundy via DP up to its size separately.
26
    // If total sizes are large with few distinct rules, group by rule set to reuse DP.
27
    map<vector<int>, vector<int>> dpByRule; // key: S_i, value: g[0..max_needed]
28
29
    auto compute_g = [&](const vector<int>& S, int need){
30
        auto it = dpByRule.find(S);
31
        if (it == dpByRule.end() || (int)it->second.size() <= need){
32
            vector<int> g;
33
            if (it == dpByRule.end()) g.assign(need + 1, 0);
34
            else g = it->second, g.resize(need + 1, 0);
35
            int start = (int)it->second.size();
36
            if (it == dpByRule.end()) start = 1; // g[0] = 0 already
37
            vector<int> Ssorted = S;
38
            for (int n = max(1, start); n <= need; ++n){
39
                int K = (int)Ssorted.size();
40
                vector<char> used(K + 1, 0);
41
                for (int s : Ssorted){ if (s > n) break; int v = g[n - s]; if (v <= K) used[v] = 1; }
42
                int m = 0; while (m <= K && used[m]) ++m; g[n] = m;
43
            }
44
            dpByRule[S] = g;
45
            return g;
46
        } else {
47
            return it->second;
48
        }
49
    };
50
51
    vector<int> G(m);
52
    int X = 0;
53
    for (int i = 0; i < m; ++i){
54
        vector<int> g = compute_g(Sets[i], A[i]);
55
        G[i] = g[A[i]];
56
        X ^= G[i];
57
    }
58
59
    cout << (X ? "First" : "Second") << " player wins\n";
60
61
    if (X){
62
        // Find a pile and a legal move to make total XOR zero.
63
        for (int i = 0; i < m; ++i){
64
            int target = G[i] ^ X; // we need to move pile i to some state with Grundy == target
65
            if (target > G[i]) continue; // in subtraction games, Grundy usually does not increase by moves
66
            // Scan moves to find a child with the needed Grundy.
67
            vector<int> g = dpByRule[Sets[i]]; // has at least up to A[i]
68
            for (int s : Sets[i]){
69
                if (s > A[i]) break;
70
                int newSize = A[i] - s;
71
                if (g[newSize] == target){
72
                    cout << "Winning move: on pile #" << i << ", remove " << s << " to get size " << newSize << "\n";
73
                    return 0;
74
                }
75
            }
76
        }
77
        cout << "No explicit winning move found (check DP coverage).\n";
78
    }
79
80
    return 0;
81
}
82

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Misère Nim decision:
5
// If all heaps are size 1, P-position iff the number of heaps is odd.
6
// Otherwise, treat exactly as normal Nim (XOR != 0 is winning).
7
8
int main(){
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int n; if(!(cin >> n)) return 0;
13
    vector<long long> a(n);
14
    long long xr = 0;
15
    bool allOne = true;
16
    for (int i = 0; i < n; ++i){
17
        cin >> a[i];
18
        xr ^= a[i];
19
        if (a[i] != 1) allOne = false;
20
    }
21
22
    bool firstWins;
23
    if (allOne){
24
        // odd count => P-position (losing for player to move)
25
        firstWins = !(n % 2 == 1);
26
    } else {
27
        firstWins = (xr != 0);
28
    }
29
30
    cout << (firstWins ? "First" : "Second") << " player wins\n";
31
32
    // Optional: construct a winning move in non-all-one case (normal Nim move)
33
    if (!allOne && firstWins){
34
        long long X = xr;
35
        for (int i = 0; i < n; ++i){
36
            long long hi = a[i];
37
            long long target = hi ^ X;
38
            if (target < hi){
39
                long long remove = hi - target;
40
                cout << "Example winning move: on heap #" << i << ", remove " << remove << " to leave " << target << "\n";
41
                break;
42
            }
43
        }
44
    }
45
46
    return 0;
47
}
48