Task A – Permutation Duel

A cyclic permutation maps [1\to2\to3\to\dots\to13\to1] Two players choose indices (x,y\in[1,13]). Compare the images (p(x)) and (p(y)); output the winner or "Draw".

int main() {
    int x, y; std::cin >> x >> y;
    int px = (x == 13 ? 1 : x + 1);
    int py = (y == 13 ? 1 : y + 1);
    if (px == py) std::cout << "Draw";
    else if (px < py) std::cout << "Bob";
    else std::cout << "Alice";
}

Task B – Sub-grid Matching

Given two square grids (A) (N\times N) and (B) (M\times M), decide whether (B) occurs as a contiguous block inside (A). (N,M\le 50).

Brute-force (O(N^2M^2))

Enumerate every top-left corner in (A) and compare the (M\times M) block with (B).

2-D rolling hash (O(N^2))

Use two bases (B) (row) and (D) (column) and 64-bit overflow as modulus.

1. Row hashes: (h_{i,j}=h_{i,j-1}\cdot B+A_{i,j})
2. Column hashes: (g_{i,j}=g_{i-1,j}\cdot D+h_{i,j})
3. Any rectangle ([x_1,x_2]\times[y_1,y_2]) has fingerprint [g_{x_2,y_2}-g_{x_1-1,y_2}D^{x_2-x_1+1}-g_{x_2,y_1-1}B^{y_2-y_1+1}+g_{x_1-1,y_1-1}D^{x_2-x_1+1}B^{y_2-y_1+1}]

Compute the hash of (B) once and scan (A) in (O(N^2)).

const u64 B = 911, D = 1777;
u64 powB[55], powD[55];

u64 rect(const vector<vector<u64>>& g,
         int r1,int r2,int c1,int c2) {
    return g[r2][c2]
         - g[r1-1][c2]*powD[r2-r1+1]
         - g[r2][c1-1]*powB[c2-c1+1]
         + g[r1-1][c1-1]*powD[r2-r1+1]*powB[c2-c1+1];
}

Task C – Hamiltonian Walks

Count simple paths starting at vertex (1) that visit all (N\le 8) vertices exactly once in an unweighted undirected graph.

Depth-first search with bit-mask pruning is sufficient: track the current vertex and the set of visited vertices. Complexity (O(N!)) is aceptable for (N=8).

int n, m;
vector<int> adj[9];
ll dfs(int u, int mask) {
    if (mask == (1<<n)-1) return 1;
    ll res = 0;
    for (int v : adj[u])
        if (!(mask >> (v-1) & 1))
            res += dfs(v, mask | (1<<(v-1)));
    return res;
}

Task D – Optimal Chemical Blending

We need (k\cdot M_a) grams of substance (A) and (k\cdot M_b) grams of substance (B) for some positive integer (k). (N\le 40) medicines are available; each (i) contains (a_i) g (A) and (b_i) g (B) and costs (c_i). Buy any subset whose total (A) and (B) satisfy the ratio exactly, minimizing total cost.

Dynamic Programming

Let (dp[i][x][y]) be the minimum cost to obtain exact (x) g (A) and (y) g (B) using the first (i) medicines. Transition: [dp[i+1][x][y]=\min\bigl(dp[i][x][y],;dp[i][x-a_{i+1}][y-b_{i+1}]+c_{i+1}\bigr)] Bounds: (x\le 40\cdot 10=400), (y\le 400). Answer is [\min_k dp[N][kM_a][kM_b]\quad(k\ge 1)]

const int MAX = 410;
const ll INF = 1e18;
ll dp[MAX][MAX];
memset(dp, 0, sizeof dp);
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
    int a = A[i], b = B[i], c = C[i];
    for (int x = MAX-1; x >= a; --x)
        for (int y = MAX-1; y >= b; --y)
            dp[x][y] = min(dp[x][y], dp[x-a][y-b] + c);
}
ll ans = INF;
for (int k = 1; k*Ma < MAX && k*Mb < MAX; ++k)
    ans = min(ans, dp[k*Ma][k*Mb]);