Alice is able to determine what move Bob makes as Bob can only make one move to maximize the results.

Because Alice may choose only one entry of $$$A$$$, every other position has a fixed contribution we can precompute — specifically, how large the result would be if Bob chose that index after Alice's move. For any choice $$$i$$$ that Alice makes, Bob will pick whichever gives a larger value: either he picks $$$j = i$$$, or he picks the best index among all $$$j \neq i$$$. Alice's goal after that is to pick an index $$$i$$$ that minimizes this worse-case value.

To evaluate the best index among all $$$j \neq i$$$ efficiently for every i, we can compute the two largest values of $$$f(j) = A_j | (y-A_j)$$$ over all $$$j$$$. For a given index $$$i$$$, if the overall maximum $$$f(j)$$$ comes from $$$j = i$$$, then the best choice among the remaining indices is the second-largest. Otherwise, the best choice is the largest. Using this idea, we can check every $$$i$$$ in constant time after the initial scan, giving an $$$O(n)$$$ solution.

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
 
    int t;
    cin >> t;
    
    while(t--){
        int n; ll x, y;
        cin >> n >> x >> y;
        
        vector<ll> vals(n);
        ll sum = 0;
        for(int i = 0; i < n; ++i) {
            cin >> vals[i];
            sum += vals[i];
        }
 
        vector<ll> loss(n);
        for(int i = 0; i < n; ++i) loss[i] = vals[i]-(vals[i]&y);
 
        ll min1 = LLONG_MAX, min2 = LLONG_MAX;
        int idx1 = -1;
        for(int i = 0; i < n; ++i) {
            if(loss[i] < min1){
                min2 = min1;
                min1 = loss[i];
                idx1 = i;
            } else if(loss[i] < min2) {
                min2 = loss[i];
            }
        }
 
        ll ans = LLONG_MAX;
        for(int i = 0; i < n; ++i) {
            ll alice = vals[i]|x;
            ll delta = alice-vals[i], same = alice-(alice&y);
            ll obest = ((i == idx1) ? min2 : min1);
            ll bob = min(obest, same);
            ll temp = sum+delta-bob;
            ans = min(ans, temp);
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}

Look for invariants

Observation 1: Let white stones represent $$$+1$$$, and black stones represent $$$-1$$$. The difference between the values of two people's stones is constant. If the starting value of stones is $$$a_i$$$, then the ending value will be $$$a_i + C$$$, for some constant $$$C$$$.

Observation 2: Define a pair of stones to be a black stone and a white stone. Note that these pairs can be freely moved. BW,0,0 B,B,B 0,0,BW

Observation 3: If there are $$$N-2$$$ pairs, and one extra stone, they can be eliminated BW, BW, BW, B, 0 W, W, W, 0, W 0, 0, 0, B, 0

Observation 4: If there are less than $$$N-2$$$ pairs, they cannot be removed without changing $$$C$$$. Proof: Every operation changes $$$C$$$ by $$$1$$$. Thus, to not change $$$C$$$, you must perform an even number of operations. Since the total number of stones changes by $$$N-2$$$ each operation, after an even number of operations, thus changing the total number of stones by a multiple of $$$2(N-2)$$$.

Thus, for a given $$$C$$$, the minimum number of pairs can be computed. It can be shown, that the value of $$$C$$$ that minimizes the stones is the negative of the median of $$$a_i$$$, plus or minus 1. Thus, you can simply test those values.

Think non-simple paths, especially the ones that use the same edge several times.

Because a path does not need to be simple, at any node $$$u$$$, we can traverse the same edge twice in a row and return to $$$u$$$. Because of this, if we consider some path from $$$s$$$ to $$$t$$$ with path weight $$$c$$$, we can always augment the path weight by $$$2 \cdot w_i$$$ arbitrarily.

Let $$$g = \gcd(w_1, w_2, \dots, w_n)$$$. Then, using the ideas of Bezout's identity and the previous observation, all path weights in the set $$$\{c, 2g + c, \dots, 2(k-1) \cdot g + c\} \mod k$$$ are obtainable. Since $$$c \mid g$$$, only $$$c = 0$$$ and $$$c = g$$$ are important given they may form different sets.

If both $$$c$$$ values are obtainable, then the obtainable set of path weights is $$$\{0, g, \dots, g(k-1)\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, g)}$$$.

If only one $$$c$$$ is obtainable, the obtainable set of path weights is $$$\{c, 2g + c, \dots, 2(k-1)g + c\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, 2g)}$$$.

Define $$$W_i = \frac{w_i}{g}$$$. Let $$$W_i$$$ be the weights of a new graph. In this graph, we notice that the existence of an even path weight corresponds to $$$c = 0$$$ and the existence of an odd path weight corresponds to $$$c = g$$$. Calculating whether an odd and/or even path exists can be done using a BFS/DFS with two states per node $$$u$$$ (whether an odd/even path exists from $$$s$$$ to $$$u$$$), solving the problem in $$$\mathcal{O}(n)$$$.

If $$$g = 0$$$, then the answer is $$$1$$$. This must be handled manually to avoid division by $$$0$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
 
int n, m, qq, a, b;
ll k;
void solve() {
    cin >> n >> m >> k >> a >> b;
    a--, b--;
    ll g = 0;
    vector<pair<pi, ll>> edges(m);
    vector<vector<pi>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        edges[i] = {{--u, --v}, w};
        g = gcd(g, w);
    }
        
    if (g == 0) {
        cout << "1\n";
        return;
    }
 
    for (int i = 0; i < m; i++) {
        auto [p, w] = edges[i];
        auto [u, v] = p;
        adj[u].push_back({v, (w / g) & 1});
        adj[v].push_back({u, (w / g) & 1});
    }
 
    vector<vector<bool>> vis(2, vector<bool>(n));
    vis[0][a] = 1;
    queue<pi> q;
    q.push({0, a});
    while (!q.empty()) {
        auto [p, u] = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) {
            if (!vis[(p + w) & 1][v]) {
                vis[(p + w) & 1][v] = 1;
                q.push({(p + w) & 1, v});
            }
        }
    }
 
    if (!vis[0][b] || !vis[1][b]) g *= 2;
    cout << k / gcd(g, k) << "\n";
}
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

Formulate a DP.

Dijkstra?

Let's solve this using DP. Let $$$d_{i, j}$$$ be the minimum number of robots required to get one robot on cell $$$(i, j)$$$. At the start, if cell $$$(i, j)$$$ is a spawn point $$$A$$$, then $$$d_{i, j} = 1$$$, otherwise $$$d_{i, j} = \text{INF} = 4 \cdot 10^{18} + 1$$$ to denote that $$$(i, j)$$$ is unreachable.

Let $$$x$$$ be some cell $$$(i, j)$$$ and $$$y$$$ be some cell orthogonally adjacent to $$$x$$$. If $$$d_x, d_y \neq \text{INF}$$$, then the robot in $$$x$$$ can push the robot in $$$y$$$ to cell $$$z$$$ (if cell $$$z$$$ is not an obstacle), setting $$$d_z$$$ to $$$\min(d_z, d_x + d_y)$$$.

Since there is no proper order to process the states, naively looping through the grid $$$nm$$$ times to calculate the states takes $$$\mathcal{O}(n^2m^2)$$$ computations. Although there is no graph nor specific edge weights, Dijkstra's algorithm can be used here. What Dijkstra does is order and process the states in non-decreasing $$$d_{i, j}$$$, eliminating wasted computations. Note that when processing cell $$$x$$$, for some orthogonally adjacent $$$y$$$, both $$$x$$$ pushing $$$y$$$ and $$$y$$$ pushing $$$x$$$ must be considered, for a total of $$$8$$$ transitions per cell. This solves the problem in $$$\mathcal{O}(nm \log nm)$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

const int N = 1005;
const ll inf = (ll)4e18 + 1;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
char grid[N][N];
ll dist[N][N];
int n, m, k, qq;
void solve() {
    cin >> n >> m;
    int tx, ty;
    priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'A') {
                dist[i][j] = 1;
                q.push({1, {i, j}});
            }

            else dist[i][j] = inf;
            if (grid[i][j] == 'B') tx = i, ty = j;
        }
    }

    auto ok = [&](int x, int y) {
        return (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#');
    };

    while (!q.empty()) {
        auto [d, p] = q.top();
        auto [x, y] = p;
        q.pop();
        if (d != dist[x][y]) continue;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!ok(nx, ny)) continue;
            ll nd = d + dist[nx][ny];
            nx += dx[i], ny += dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }

            nx = x - dx[i], ny = y - dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }
        }
    }

    cout << (dist[tx][ty] == inf ? -1 : dist[tx][ty]) << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

Recall that the trolleys are sorted such that the heaviest trolleys go first, and the lightest ones go last. If a trolley gets stopped by a cow, what does that mean for the rest of the trolleys?

If we have a trolley get stopped by a cow, then we can direct subsequent trolleys to the same cow.

Once we have one cow that can stop a trolley, all subsequent trolleys can be directed to that same cow. This means that in our array of trolleys, we will have some prefix of trolleys that won't awaken a cow, while the rest of the trolleys will result in us waking up a cow.

Let's consider binary searching on the longest prefix of trolleys that won't awaken a cow. Consider checking if a prefix length of $$$m$$$ is valid.

Let the weight of the heaviest trolley in our prefix be $$$x$$$. We need to find the minimum index $$$i$$$, such that either $$$c[i] \geq x$$$ or $$$d[i] \geq x$$$.

If we are zero-indexing, $$$i$$$ is equal to the number of cows that must be awoken before finally reaching a cow heavy enough to stop our prefix of trolleys.

As long as $$$i$$$ is less than $$$n - m$$$, the number of trolleys not in our prefix, we can force all $$$m$$$ trolleys into a cow that is heavy enough.

Thus, with this condition, we can binary search on the longest prefix. The answer is then the number of trolleys that aren't in our prefix. With that, we can solve the problem in $$$\mathcal{O}(n \log n)$$$ time.

Note that an $$$\mathcal{O}(n)$$$ solution exists, but is slightly more difficult to implement.

#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, a, b;
    std::cin >> n >> a >> b;
    std::vector<int> t(n), c(a), d(b);
    for (auto &i : t) std::cin >> i;
    for (auto &i : c) std::cin >> i;
    for (auto &i : d) std::cin >> i;

    int lo = 0, hi = n;
    while (lo < hi) {
        int m = (lo + hi + 1) / 2;

        int biggest = (m == 0) ? -1 : t[m - 1];
        int get_hit = std::min(a, b);

        for (int i = 0; i < a; i++) {
            if (biggest <= c[i]) get_hit = std::min(get_hit, i);
        }

        for (int i = 0; i < b; i++) {
            if (biggest <= d[i]) get_hit = std::min(get_hit, i);
        }

        if (get_hit <= n - m) lo = m;
        else hi = m - 1;
    }

    std::cout << n - lo << '\n';
}

If we have a square $$$s$$$ and another square $$$S$$$ that completely covers $$$s$$$, then the intersection of $$$s$$$ and $$$S$$$ is a valid square.

Recall that we can pick any valid square, so long as the coordinates for both axes are in the range $$$[-10^9, 10^9]$$$.

Note that all coordinates for our squares are in the range $$$[-10^9, 10^9]$$$. Also, consider that we are allowed to print any square that satisfies the condition in the problem statement.

Consider Hint 1: if another square completely covers one square, then their intersection remains a square. Thus, the easiest construction is for our square $$$S$$$ to cover all the input squares completely.

Because of this, we can print a square with its lower-left corner at $$$(-10^9, -10^9)$$$ and its upper-right corner at $$$(10^9, 10^9)$$$.

inf = 10**9
print(-inf, -inf, inf, inf)

Is there a greedy that determines the optimal independent set?

How can we make the $$$K$$$ grids "independent"?

Think game theory. What does the graph also represent?

We can first notice that choosing the independent set can be done greedily from maximum to minimum $$$S$$$ due to $$$NM^{K \cdot S} \gt NM^{K \cdot (S-1)} (NM^K - 1)$$$. The issue now is the large value of $$$K$$$, which calls for finding a way to think of each of the $$$K$$$ boards independently. To do this, consider the following two player-game:

Initially, each grid, numbered $$$1$$$ to $$$K$$$, has one token on one of the cells. Alice and Bob take turns alternately. On each player's turn, the current player chooses some grid $$$G$$$ $$$(1 \leq G \leq K)$$$ and moves the token on cell $$$(i, j)$$$ and moves it to either $$$(k, j)$$$ $$$(0 \leq k \lt i)$$$ or $$$(i, k)$$$ $$$(0 \leq k \lt j)$$$ on grid $$$G$$$. Note that this is equivalent to traversing the graph with each move moving closer to $$$((0, 0), \dots, (0, 0))$$$. The current player loses when they cannot move.

The key realization here is that the game states in which the current player is losing is exactly our desired independent set in the graph. Because there are $$$K$$$ disjoint boards in the setting of a game, we can now think of each token position as some Grundy number. Let $$$\text{SG}(i, j)$$$ be the Grundy number if the token is at $$$(i, j)$$$. From this transformation, we see that a node $$$(P_1, P_2, \dots, P_K)$$$ is in our desired independent set if and only if $$$\text{SG}(P_1) \oplus \text{SG}(P_2), \cdots, \text{SG}(P_{K-1})\oplus \text{SG}(P_K) = 0$$$, where $$$\oplus$$$ is the bitwise XOR operator.

We can then let

Now, denoting the $$$\oplus$$$ convolution operator as $$$*$$$, the answer is $$$(\underbrace{C * ... * C}_{\text{K times}})_0$$$. Naive binary exponentiation can compute this in $$$\mathcal{O}((N + M)^2 \log K)$$$ given that $$$\max(SG(i, j))$$$ scales on the order of $$$\mathcal{O}(N + M)$$$.

These are already some very tough observations, but this still only gets $$$60/100$$$ points. There are still two more key parts to achieve a full solution.

The first part is to optimize calculating Grundy numbers of each cell, in which a naive solution takes $$$\mathcal{O}(NM (N + M))$$$. If we write a brute force and look for patterns, what we find is that $$$\text{SG}(i, j) = i \oplus j$$$. This can be proven by induction by showing that if this property holds for all cells in the square $$$((0, 0), (2^k-1, 2^k-1))$$$, then it also holds for all values in the square $$$((0, 0), (2^{k+1}-1, 2^{k+1}-1))$$$. The full proof is left as an exercise for the reader.

The second part is to optimize the $$$\oplus$$$ convolution. To do this, we must use $$$\oplus$$$ $$$\text{FWHT}$$$ (Fast Walsh–Hadamard transform). Denoting $$$\text{FWHT}$$$ as $$$F$$$ for short, we note that $$$C * C = F^{-1}(F(C) \cdot F(C))$$$. Applying $$$\text{FWHT}$$$ naively with binary exponentiation obtains an $$$\mathcal{O}((N + M) \log (N + M)\log K)$$$ solution.

However, we can make this faster by more closely analyzing the convolution.

Canceling the $$$F$$$ and $$$F^{-1}$$$, we get

From this, by induction, we can notice that $$$\underbrace{C * ... * C}_{\text{K times}} = F^{-1}\left(F(C)^K\right)$$$. This allows us to use binary exponentiation on each index of $$$C$$$ and only $$$2$$$ calls of $$$\text{FWHT}$$$, solving the problem in $$$\mathcal{O}((N + M) \cdot (\log (N + M) + \log K))$$$.

#include "bits/stdc++.h"
using namespace std;

constexpr int mod = 998244353, inv2 = (mod + 1) / 2;
typedef long long ll;

int add(int x, int y) {
    if (x + y >= mod) return x + y - mod;
    if (x + y < 0) return x + y + mod;
    else return x + y;
}

int mul(int x, int y) {
    return (ll)x * y % mod;
}

int power(int x, int p) {
    int res = 1;
    while (p) {
        if (p & 1) res = mul(res, x);
        x = mul(x, x);
        p >>= 1;
    }

    return res;
}

void FWHT(vector<int> &a, bool inv = false) {
    int sz = a.size();
    for (int len = 1; 2 * len <= sz; len <<= 1) {
        for (int i = 0; i < sz; i += 2 * len) {
            for (int j = i; j < i + len; j++) {
                int x = a[j], y = a[j + len];
                if (!inv) a[j] = add(x, y), a[j + len] = add(x, -y);
                else a[j] = mul(add(x, y), inv2), a[j + len] = mul(add(x, -y), inv2);
            }
        }
    }
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int x = n * m, y = 1;
    while (y < x) y <<= 1;
    int v = power(x, k);
    vector<vector<int>> a(n, vector<int>(m));
    vector<int> f(y);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            f[i ^ j] = add(f[i ^ j], power(v, a[i][j]));
        }
    }

    FWHT(f);
    for (int i = 0; i < y; i++) {
        f[i] = power(f[i], k);
    }

    FWHT(f, 1);
    cout << f[0] << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}