What if there were no magic stones?

What should we do if we take the magic stone?

Take the max of the two cases above.

public class MagicSubset {
    public int findBest(int[] values) {
        int n = values.length;
        int s1 = 0;
        for (int i = 1; i < n; i++) s1 += Math.max(0,values[i]);
        int s2 = values[0];
        for (int i = 1; i < n; i++) s2 += Math.min(0,values[i]);
        return Math.max(s1,-s2);
    }
}

Choose an arbitrary pile as the "final" pile. What are some strategies to get all the stones in that pile?

Do we have enough moves?

Let's choose pile 0 as our "final" pile. Then, while there exists a non-empty pile that is not pile 0, do a move on that pile. This is guaranteed to terminate in at most (num stones) * (num piles) steps.

import java.util.ArrayList;
import java.util.Arrays;

public class ForwardMancala {
    public ArrayList<Integer> find(int[] start) {
        ArrayList<Integer> ret = new ArrayList<>();
        int n = start.length;
        while (true) {
            boolean changed = false;
            for (int i = 1; i < n; i++) {
                if (start[i] > 0) {
                    changed = true;
                    int t = i;
                    int d = start[i];
                    start[i] = 0;
                    while (d-->0) {
                        t = (t+1) % n;
                        start[t]++;
                    }
                    ret.add(i);
                }
            }
            if (!changed) break;
        }
        return ret;
    }

    public int[] findMoves(int[] start) {
        ArrayList<Integer> ans = find(start);
        int[] ret = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++)
            ret[i] = ans.get(i);
        return ret;
    }
}

Add the edges in increasing cost.

#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;  

class MinMaxMax {
public:
	ll findMin(vector<int> a, vector<int> b, vector<int> w, vector<int> v) {
		int n=SZ(v),m=SZ(w);
		vector<pair<int,int> > ov; REP(i,n) ov.PB(MP(v[i],i)); sort(ov.begin(),ov.end());
		vector<pair<int,int> > ow; REP(i,m) ow.PB(MP(w[i],i)); sort(ow.begin(),ow.end());
		vector<vector<ll > > d(n,vector<ll>(n,LLONG_MAX));
		REP(i,n) {
			vector<bool> alive(n,false); REPE(j,i) alive[ov[j].second]=true;
			vector<int> comp(n); REP(i,n) comp[i]=i;
			REP(j,m) {
				int aa=a[ow[j].second],bb=b[ow[j].second];
				if(comp[aa]==comp[bb]||!alive[aa]||!alive[bb]) continue;
				ll cur=(ll)ov[i].first*ow[j].first;
				vector<int> va,vb; REP(k,n) if(comp[k]==comp[aa]) va.PB(k); else if(comp[k]==comp[bb]) vb.PB(k);
				REPSZ(ai,va) REPSZ(bi,vb) { int ca=va[ai],cb=vb[bi]; if(cur<d[ca][cb]) d[ca][cb]=cur; if(cur<d[cb][ca]) d[cb][ca]=cur; }
				REPSZ(bi,vb) { int cb=vb[bi]; comp[cb]=comp[aa]; }
			}
		}
		ll ret=0; REP(i,n) FOR(j,i+1,n) { assert(d[i][j]!=LLONG_MAX); ret+=d[i][j]; } return ret;
	}    
};

Add the nodes in increasing cost.

import java.util.Arrays;
import java.util.Comparator;
public class MinMaxMax {
    static class Pair {
        public int a,b;
        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    public long findMin(int[] a, int[] b, int[] w, int[] v) {
        int n = v.length, m = a.length;
        Pair[] d = new Pair[n];
        for (int i = 0; i < n; i++) {
            d[i] = new Pair(v[i],i);
        }
        Arrays.sort(d, Comparator.comparingInt(x -> x.a));
        long[][] mn = new long[n][n];
        for (long[] x : mn) Arrays.fill(x, 1L << 40);
        for (int i = 0; i < m; i++) {
            mn[a[i]][b[i]] = mn[b[i]][a[i]] = w[i];
        }
        long[][] dist = new long[n][n];
        for (long[] x : dist) Arrays.fill(x, 1L << 60);
        for (int e = 0; e < n; e++) {
            int k = d[e].b;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    mn[i][j] = Math.min(mn[i][j], Math.max(mn[i][k],mn[k][j]));
                    dist[i][j] = Math.min(dist[i][j], 1L * mn[i][j] * Math.max(v[k], Math.max(v[i], v[j])));
                }
            }
        }
        long ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                ret += dist[i][j];
            }
        }
        return ret;
    }
}

The two operations are inverses of each other.

We can bring both of them to any common state.

Read the problem statement for div2 med. Try to get all the stones into one pile.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class ReverseMancala {
    public ArrayList<Integer> find(int[] start, boolean rev) {
        ArrayList<Integer> ret = new ArrayList<>();
        int n = start.length;
        while (true) {
            boolean changed = false;
            for (int i = 1; i < n; i++) {
                if (start[i] > 0) {
                    changed = true;
                    int t = i;
                    int d = start[i];
                    start[i] = 0;
                    while (d-->0) {
                        t = (t+1) % n;
                        start[t]++;
                    }
                    if (rev) {
                        ret.add(t+n);
                    } else {
                        ret.add(i);
                    }
                }
            }
            if (!changed) break;
        }
        if (rev) Collections.reverse(ret);
        return ret;
    }

    public int[] findMoves(int[] start, int[] target) {
        ArrayList<Integer> ans = find(start, false);
        ans.addAll(find(target, true));
        int[] ret = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++)
            ret[i] = ans.get(i);
        return ret;
    }
}

What are some obvious winning or losing states?

After checking those two cases, we can ignore the lowest bits of all the numbers, as well as the magic stone.

This then becomes a game where a[i] is replaced by a[i]>>1, and the last player who takes a stone loses. This is misere nim.

public class MagicNim {
	public String findWinner(int[] a) {
		return (Arrays.stream(a).max().getAsInt() <= 3 ? 2 : 1) != Arrays.stream(a).reduce(0, (x,y) -> x^y) ? "Alice" : "Bob";
	}
}

Solve the problem when k = 1.

Solve a more general version of the problem when k=1, but we also want certain pairs of hyperboxes to be intersecting (described by a bit-mask with (m choose 2) bits). To restate, for every 2^(m choose 2) choices of bitmasks, compute the number of ways to solve this problem in 1 dimension.

Two hyperboxes intersect if and only they intersect in every single dimension. Thus, they are disjoint if we take the bitwise and of all intersections of each dimension and it equals zero. This can be done efficiently with a Fast Walsh Hadamard transform.

public class Hyperboxes {
    public static int mod = 998244353;
    public static long[] inv;
    static {
        inv = new long[20];
        inv[1] = 1;
        for (int i = 2; i < inv.length; i++) {
            inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        }
    }
    public long choose(long n, int k) {
        if (k < 0 || k > n) return 0;
        long ret = 1;
        for (int i = 0; i < k; i++) {
            ret = ret * (n-i) % mod;
            ret = ret * inv[i+1] % mod;
        }
        return ret;
    }

    public int[] t = {0,1,3,6,10,15};
    public int getBit(int i, int j) {
        if (j > i) {
            int w = i; i = j; j = w;
        }
        return t[i-1] + j;
    }

    public boolean nextPermutation(int[] p) {
        for (int a = p.length - 2; a >= 0; --a)
            if (p[a] < p[a + 1])
                for (int b = p.length - 1; ; --b)
                    if (p[b] > p[a]) {
                        int t = p[a];
                        p[a] = p[b];
                        p[b] = t;
                        for (++a, b = p.length - 1; a < b; ++a, --b) {
                            t = p[a];
                            p[a] = p[b];
                            p[b] = t;
                        }
                        return true;
                    }
        return false;
    }

    public long mod_exp(long b, long e, long mod) {
        long res = 1;
        while (e > 0) {
            if ((e & 1) == 1)
                res = (res * b) % mod;
            b = (b * b) % mod;
            e >>= 1;
        }
        return res;
    }

    public int n,m,k;
    public int[] f1;
    public int[] f2;
    public void dfs(int next, int closed, int groupopen, int pclosed, int intersections, int groups, long mult) {
        if (next == m && closed == (1 << m) - 1) {
            f1[intersections] += choose(n, groups) * mult % mod;
            if (f1[intersections] >= mod) {
                f1[intersections] -= mod;
            }
            return;
        }
        if (next < m) {
            dfs(next + 1, closed, (1 << next), -1, intersections, groups + 1, mult);
            if (pclosed == -1) {
                dfs(next + 1, closed, groupopen | (1 << next), -1, intersections, groups, mult * inv[Integer.bitCount(groupopen) + 1] % mod);
            }
        }
        // choose to close, continue same group
        for (int x = pclosed+1; x < next; x++) {
            if (((closed>>x) & 1) == 1) continue;
            if (((groupopen>>x) & 1) == 1) continue;
            int ninter = intersections;
            for (int w = 0; w < next; w++) {
                if (w != x && ((closed>>w) & 1) == 0) {
                    ninter |= 1 << getBit(x, w);
                }
            }
            dfs(next, closed|(1<<x), groupopen, x, ninter, groups, mult);
        }
        // start different group
        for (int x = 0; x < next; x++) {
            if (((closed>>x) & 1) == 1) continue;
            int ninter = intersections;
            for (int w = 0; w < next; w++) {
                if (w != x && ((closed>>w) & 1) == 0) {
                    ninter |= 1 << getBit(x, w);
                }
            }
            dfs(next, closed|(1<<x), 0, x, ninter, groups+1, mult);
        }
    }

    public void postprocess() {
        int[] perm = new int[m];
        for (int i = 0; i < m; i++) perm[i] = i;
        for (int mask = 0; mask < 1 << t[m-1]; mask++) {
            if (f1[mask] == 0) continue;
            for (int i = 0; i < m; i++) perm[i] = i;
            do {
                int nmask = 0;
                int c = 0;
                for (int x = 0; x < m; x++) {
                    for (int y = 0; y < x; y++) {
                        int target = getBit(perm[x], perm[y]);
                        if (((mask>>c)&1) == 1)
                            nmask |= 1 << target;
                        c++;
                    }
                }
                f2[nmask] += f1[mask];
                if (f2[nmask] >= mod) f2[nmask] -= mod;
            } while (nextPermutation(perm));
        } while (nextPermutation(perm));
    }

    public int findCount(int _n, int _m, int _k) {
        n = _n; m = _m; k = _k;
        f1 = new int[1<<t[m-1]];
        // brute force m
        // catalan(m) * m! * 2^(2m)
        dfs(1, 0, 1, -1, 0, 1, 1);

        // post process
        // 2^(m choose 2) * m! * m
        f2 = new int[1<<t[m-1]];
        postprocess();

        // FWT
        // (m choose 2) * 2^(m choose 2)
        int levels = 31-Integer.numberOfLeadingZeros(f2.length);
        int len = f2.length;
        for (int i = levels-1; i >= 0; i--) {
            for (int j = 0; j < len; j++) {
                if (((j>>i)&1) == 0) {
                    f2[j] = (f2[j] + f2[j|(1<<i)]) % mod;
                }
            }
        }
        for (int i = 0; i < len; i++) {
            f2[i] = (int)mod_exp(f2[i], k, mod);
        }
        for (int i = 0; i < levels; i++) {
            for (int j = 0; j < len; j++) {
                if (((j>>i)&1) == 0) {
                    f2[j] = (f2[j] - f2[j|(1<<i)] + mod) % mod;
                }
            }
        }
        return f2[0];
    }
}