Cookie Monster is playing with his three cookies, which have distinct sizes $$$a$$$, $$$b$$$, and $$$c$$$, respectively. He wants to create a cookie tower by stacking them up. Cookie Monster wants the largest cookie to be on the bottom (for a strong foundation). However, he wants the top of the tower to be big as well, so he wants to place the second largest cookie on top and the smallest cookie in the middle.

Given the sizes of Cookie Monster's cookies $$$a$$$, $$$b$$$, and $$$c$$$, help him order the cookies in the order biggest, smallest, middle.

The first line will contain the three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \leq a, b, c \leq 100$$$). It is guaranteed that $$$a \neq b$$$, $$$b \neq c$$$, and $$$a \neq c$$$.

Print three integers corresponding to the cookies in the order Cookie Monster wants them in.

We can sort the array $$$[a, b, c]$$$ in decreasing order and then make a swap between the last two numbers and print our result.

blocks = list(map(int, input().split()))
blocks.sort(reverse=True)
temp = 0
temp = blocks[2]
blocks[2] = blocks[1]
blocks[1] = temp
print(" ".join(str(el) for el in blocks))

Cookie Monster has an empty board with $$$m$$$ rows and $$$n$$$ columns. He wants to place as many $$$2 \times 1$$$ dominoes as possible on the board without overlapping. Dominoes can be placed either vertically or horizontally, and each domino must cover exactly two adjacent cells.

Determine whether it is possible for Cookie Monster to tile the entire board with such dominoes so that no cell remains uncovered.

A single line containing two integers $$$m$$$ and $$$n$$$ ($$$1 \leq m, n \leq 100$$$).

Print YES if the board can be completely tiled with $$$2 \times 1$$$ dominoes. Otherwise, print NO.

If the total number of squares is odd, then it is impossible to tile the board as each domino contains an even number of squares. On the other hand, if either $$$m$$$ or $$$n$$$ is even, we can always fill the board with dominoes. Thus, we only have to check if $$$m$$$ or $$$n$$$ is even.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    long long m, n;
    cin >> m >> n;
 
    if ((m * n) % 2 == 0) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
 
    return 0;
}

Look at the sample image given and try some cases on paper to see how the rotation operation works. We can think of the $$$180$$$ degree rotation as reversing the array of digits and rotating each individual digit by $$$180$$$ degrees. Notice that when rotated $$$180$$$, all digits remain the same except for $$$6$$$ and $$$9$$$ which swap. So to solve the problem, we need to reverse the order of the $$$n$$$ digits and swap any $$$6 \leftrightarrow 9$$$.

n = int(input())
nums = list(map(int, input().split()))
nums = nums[::-1]
nums = [6 if el == 9 else (9 if el == 6 else el) for el in nums]
print(" ".join(str(el) for el in nums))

We can find formulas for the index of the desk in the $$$i$$$-th row and $$$j$$$-th column ($$$0$$$-indexed) in both Cookie Monster's and Elmo's ordering.

• Cookie Monster: $$$i \cdot m + j + 1$$$
• Elmo: $$$i + j \cdot n + 1$$$

Setting them equal to each other, we get $$$i \cdot (m - 1) = j \cdot (n - 1)$$$ where $$$0 \le i \lt n$$$ and $$$0 \le j \lt m$$$. Let $$$g = \text{gcd}(m-1, n-1)$$$, $$$a=\frac{m-1}{g}$$$, and $$$b=\frac{n-1}{g}$$$. The equation simplifies to $$$i \cdot a = j \cdot b$$$, where $$$a$$$ and $$$b$$$ are coprime. This means that $$$i$$$ and $$$j$$$ must be multiples of $$$b$$$ and $$$a$$$, respectively. If we let $$$i=k \cdot b$$$, then we can see that $$$j=k \cdot a$$$. Within the constraints on $$$i$$$ and $$$j$$$, there are $$$g+1$$$ values of $$$k$$$ that satisfy the equation. So the answer is $$$\text{gcd}(m-1, n-1) + 1$$$.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m; cin >> n >> m;
    if (n == 1 && m == 1) cout << 1 << endl;
    else if (n == 1) cout << m << endl;
    else if (m == 1) cout << n << endl;
    else cout << 1 + __gcd(n-1, m-1) << endl;
}

Since the XOR operation is associative and commutative, if $$$A$$$ and $$$B$$$ have the same XOR, then the XOR of the whole array must be $$$0$$$. So if the XOR of the whole array is not $$$0$$$, then the answer is $$$0$$$. If the XOR is $$$0$$$, then any valid way to partition the array must result in two sets with equal XOR. The number of ways to partition the array as defined in the statement is $$$2^n - 2$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n; cin >> n;
    int x = 0;
    for (int i = 0; i < n; i++) {
        int v; cin >> v;
        x ^= v;
    }
    if (x) cout << 0 << endl;
    else cout << (1LL << n) - 2 << endl;
}

Define a fixed point as an integer $$$i \in [1, n]$$$ such that $$$a_i = i$$$. Let $$$f(a)$$$ be the number of integers $$$j \in [1, n]$$$ which are not fixed points of the permutation $$$a_1, \ldots, a_n$$$.

Claim: Let $$$A^\prime$$$ refer to the permutation $$$A$$$ after applying the given operation once. We must have $$$f(A^\prime) \le \frac{f(A)}{2}$$$.

Proof: If $$$A$$$ has no fixed points, we are done. Otherwise, let $$$i$$$ be the index of the first $$$a_i$$$ which is not a fixed point. We will perform $$$\text{swap}(i, a_i)$$$, which converts $$$a_i$$$ into a fixed point. Additionally, $$$a_{a_i}$$$ is guaranteed to not be a fixed point and is moved to index $$$i$$$, where it may or may not be affected by future swaps. We can then continue to the next $$$a_j$$$ ($$$j \gt i$$$) which is not a fixed point. Each swap affects two numbers and converts at least one of them into a fixed point. Thus, the number of fixed points is at least halved during the operation.

A permutation is sorted when it has $$$n$$$ fixed points or when $$$f(A) = 0$$$. Initially, $$$f(A) \le n$$$, so after $$$O(\log{n})$$$ iterations we are guaranteed to have $$$f(A) = 0$$$. Thus, we can simulate operations until the permutation is sorted for a time complexity of $$$O(n \log n)$$$.

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

void solve() {
	int n; cin >> n;

    int bound = 32 - __builtin_clz(n);

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        arr[i]--;
    }

    int cnt = 0;

    do {
        bool ok = true;
        for (int i = 0; i < n-1; i++) {
            if (arr[i] > arr[i+1]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << cnt << endl;
            break;
        }
        
        for (int i = 0; i < n; i++) {
            swap(arr[i], arr[arr[i]]);
        }

        cnt++;
        assert(cnt <= bound);
    } while (true);
}

int main() {
    int t = 1; 
    // cin >> t;
    while (t--) {
        solve();
    }
}

The problem is basically asking us to attach the trees that node $$$1$$$ is not a part of onto the tree that node $$$1$$$ is a part of. Starting with the tree that node $$$1$$$ is part of, it is optimal to keep attaching trees onto the deepest point of this tree. To compute the height of the final tree, we take the height of the initial tree plus the diameters of all the other trees, which is the farthest distance between any two nodes of the tree, as this tells us how deep we can make the tree go. To compute the diameter of each of these trees, we can perform a depth first search from an arbitrary node in the tree to find the farthest node from that node, then find the height of the tree when rooted at this new farthest node.

#include <bits/stdc++.h>
 
using namespace std;
 
using pi = pair<int, int>;
#define f first
#define s second
 
int main() {
	int n, m; cin >> n >> m;
 
    vector<int> vis(n, 0);
    vector<vector<int>> adj(n);
 
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; 
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    auto dfs = [&](auto &&self, int x, int v) -> pi {
        vis[x]++;
        pi res{0, x};
        for (auto y : adj[x]) {
            if (vis[y] != v) continue;
            pi ret = self(self, y, v);
            if (ret.f >= res.f) {
                res = ret;
                res.f++;
            }
        }
        return res;
    };
 
    int ans = n-m-1;
    pi v = dfs(dfs, 0, 0);
    ans += v.f;
 
 
    for (int i = 0; i < n; i++) {
        if (vis[i] == 0) {
            pi z1 = dfs(dfs, i, 0);
            pi z2 = dfs(dfs, z1.s, 1);
            ans += z2.f;
        }
    }
 
    cout << ans << endl;
}

Cookie Monster and Elmo are playing a game on an $$$8 \times 8$$$ chessboard, but Cookie Monster is a prolific fraudster with a fake CS degree from MIT. The game is too hard for him, so Cookie Monster probably plans to cheat using a hidden vibrating device, but before this, he needs your help.

On each square of the board is a number $$$a_{ij}$$$. With one move, either player can increase the value of a single square $$$a_{ij}$$$ by $$$1$$$. First, Cookie Monster performs no more than $$$x$$$ moves on the board. Second, Elmo performs no more than $$$y$$$ moves on the board.

At the end of each of their turns, Cookie Monster's score is the number of $$$a_{ij}$$$ that are prime. Cookie Monster wants to maximize his score, while Elmo wants to minimize it. Determine the maximum score Cookie Monster can attain.

The first line will contain two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 64$$$).

The following $$$8$$$ lines will each contain $$$8$$$ integers $$$a_{ij}$$$ ($$$3 \lt a_{ij} \le 10^6$$$).

Output a single integer, the maximum possible attainable score for Cookie Monster if both players act optimally.

Since $$$a_{ij} \gt 1$$$, increasing a prime number by 1 will make it a non-prime, as it'll become divisible by $$$2$$$. Thus, Elmo's strategy is to increase as many prime numbers on the board as he can with exactly one operation, leaving all non-primes untouched.

Cookie Monster's strategy is based on trying to maximize the number of primes on the board. Let's first precompute all primes $$$\le 10^6$$$ with the Sieve of Eratosthenes. Then, we can find for each $$$a_{ij}$$$ the minimum number of operations to make it prime, which we will call $$$d_{ij}$$$. We can use a greedy algorithm to maximize the number of primes: keep taking the smallest $$$d_{ij}$$$ and converting it into prime until you run out of operations. We can do this by sorting $$$d_{ij}$$$, whcih gives a final time complexity of $$$O(n \log n + M \log \log M)$$$, where $$$n$$$ is the size of the board and $$$M$$$ is the maximum $$$a_{ij}$$$.

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


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int x, y, sum = 0, tot, a;
    cin >> x >> y;
    vector<int> v;
    vector<bool> c(1'000'200);
    for (int i = 2; i * i < 1'000'200; i++) {
        if (!c[i]) {
            for (int j = i + i; j < 1'000'200; j += i) {
                c[j] = true;
            }
        }
    }
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> a;
            tot = 0;
            for (int k = 0; k < 70; k++) {
                if (!c[a]) {
                    break;
                }
                a++;
                tot++;
            }
            v.push_back(tot);
        }
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < 64; i++) {
        if (x >= v[i]) {
            x -= v[i];
            sum++;
        }
    }
    cout << max(sum - y, 0);
	return 0;
}

In this variation, a few critical details have been changed. We see that Elmo's can still make a number no longer "valid" in exactly one move using Fermat's Theorem on Sums of Two Squares.

Using the same logic from the easy variant, and combining our intuition from the aforementioned theorem, our main hurdle is determining quickly whether a very large number is prime. We use the deterministic variant of the Miller Rabin algorithm to overcome this. This algorithm is supported by a binary exponentiation algorithm, as well as utilizes 128-bit integers to avoid overflow with the scale of our grid's values. Besides this, we conduct a greedy and sorting approach as detailed previously.

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

using u64 = uint64_t;
using u128 = __uint128_t;

u64 binpower(u64 base, u64 e, u64 mod) {
    u64 result = 1;
    base %= mod;
    while (e) {
        if (e & 1)
            result = (u128)result * base % mod;
        base = (u128)base * base % mod;
        e >>= 1;
    }
    return result;
}

bool check_composite(u64 n, u64 a, u64 d, int s) {
    u64 x = binpower(a, d, n);
    if (x == 1 || x == n &mdash; 1)
        return false;
    for (int r = 1; r < s; r++) {
        x = (u128)x * x % n;
        if (x == n &mdash; 1)
            return false;
    }
    return true;
};

bool MillerRabin(u64 n) {
    if (n < 2)
        return false;

    for (int a : {2, 3, 5, 13, 19, 73, 193, 407521, 299210837}) {
        if (n == a)
            return true;
    }

    int r = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        r++;
    }

    for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        if (n == a)
            return true;
        if (check_composite(n, a, d, r))
            return false;
    }
    return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int x, y, sum = 0, tot;
    long long a;
    cin >> x >> y;
    vector<int> v;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> a;
            if (a % 2 == 1) {
                tot = 0;
                if (a % 4 == 3) {
                    tot += 1;
                    a += 2;
                }
                while (!MillerRabin(a)) {
                    tot += 2;
                    a += 4;
                }
                v.push_back(tot);
            } else if (a == 2) {
                v.push_back(0);
            } else {
                v.push_back(1000);
            }
        }
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < 64; i++) {
        if (x >= v[i]) {
            x -= v[i];
            sum++;
        }
    }
    cout << max(sum &mdash; y, 0);
	return 0;
}

Consider a slow method of answering a single query. Binary search on the first time the range is less than $$$x$$$. When trying to check a specific time, let's say $$$T$$$, first build a segment/Fenwick tree with the initial values. Then apply all updates until $$$T$$$, then finally query for the range in question and compare that with $$$x$$$.

The issue with the previous solution is that we are repeatedly doing the process of building the segment tree and then updating from time $$$1 \ldots t$$$. We can expand on this solution by using a sweepline, performing the binary searches in parallel. Repeatedly perform the process of building the segment tree and updating times $$$1 \ldots t$$$. Whenever you reach a time $$$T$$$ that needs to be checked for a query's binary search, do a range sum on the tree and update that query's binary search state, and then mark the new $$$T$$$ that needs to be checked. If the binary search has terminated, set that value as the answer for the query.

There is a more detailed explanation here.

There are other alternative solutions, such as square root decomposition and powerful data structures (offline 2D BIT).

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pl = pair<ll, ll>;
#define f first
#define s second
 
struct SegTree {
    int len;
    vector<ll> arr;
    SegTree(int _len) : len(_len), arr(_len * 2, 0) {}
    void set(int ind, ll val) {
        //cerr<<"set: " << ind << " " << val << endl;
        ind += len; arr[ind] = val;
        for (; ind > 1; ind /= 2) arr[ind / 2] = arr[ind] + arr[ind ^ 1];
    }
    ll query(int start, int end) {
        // cerr<<"query: "<< start << " " << end;
        ll res = 0;
        for (start += len, end += len; start < end; start /= 2, end /= 2) {
            if (start % 2 == 1) { res += arr[start++]; }
            if (end % 2 == 1) { res += arr[--end]; }
        }
        //cerr << " " << res << endl;
        return res;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, q, t; cin >> n >> t >> q;
    vector<ll> arr(n);
    for (auto &x : arr) cin >> x;
 
    vector<pl> ops(t);
    for (auto &x : ops) cin >> x.f >> x.s;
    for (auto &x : ops) x.f--;
 
    vector<array<ll, 3>> queries(q);
    for (auto &x : queries) cin >> x[0] >> x[1] >> x[2];
    for (auto &x : queries) {x[0]--; x[1]--;}
 
    vector<pl> bound(q, {-1, t+1});
 
    int rounds = 64 - __builtin_clz(q) + 1;
    while (rounds--) {
        vector<int> check[t+1];
        for (int i = 0; i < q; i++) {
            int m = (bound[i].f + bound[i].s) / 2;
            if (m >= 0 && m <= t) check[m].push_back(i);
        }
 
        vector<ll> car(arr);
        SegTree st(n);
        for (int i = 0; i < n; i++) st.set(i, car[i]);
 
        for (auto j : check[0]) {
            ll res = st.query(queries[j][0], queries[j][1]+1);
            if (res <= queries[j][2]) bound[j].s = 0;
            else bound[j].f = 0;
        }
 
        for (int i = 0; i <= t; i++) {
            for (auto j : check[i]) {
                ll res = st.query(queries[j][0], queries[j][1]+1);
                if (res <= queries[j][2]) bound[j].s = i;
                else bound[j].f = i;
            }
            if (i == t) break;
            car[ops[i].f] -= ops[i].s;
            st.set(ops[i].f, car[ops[i].f]);
        }
    }
 
    for (auto &lr : bound) cout << (lr.s == t+1 ? -1 : lr.s) << endl;
}

We will use intuition from linear algebra to approach this problem. We will use the notation that indexes are always taken $$$\bmod n$$$ and $$$0$$$-indexed. In other words, $$$x_i$$$ and other variables are defined as $$$x_{(i \bmod n)}$$$ for integers $$$i$$$ outside the range $$$[0, n-1]$$$.

Let $$$c_i$$$ be the total amount that you increase the $$$i$$$-th lock by. For each integer $$$i \in [0, n-1]$$$, we have an equation $$$\sum\limits_{j=i}^{i+m} c_{j} = a_{i+m}$$$, forming a system of $$$n$$$ linear equations. If we subtract all pairs of equations with adjacent $$$i$$$, then we get $$$n$$$ equations of the form $$$c_{i+m+1} - c_i = a_{i+m+1} - a_{i+m}$$$. Our new system of equations contains $$$2n$$$ variables instead of $$$mn$$$, making it significantly simpler to solve. However, our new system contains less information as we cannot represent the original system as a linear combination of the equations in our new system. To fix this, we can add one equation from our original system (i.e. $$$c_0 + \ldots + c_m = a_m$$$) to our new system at the end, which we will refer to as the "final" equation.

Let's define $$$d_{i} = a_{i+m+1} - a_{i+m}$$$ for convenience. We now have our system of equations $$$c_{i+m+1} - c_i = d_{i}$$$ for each integer $$$i \in [0, n-1]$$$. Let's consider this as a functional graph with an edge from every node $$$i$$$ to node $$$(i+m+1) \bmod n$$$ with weight $$$d_i$$$. This graph has several useful properties. First, it consists of $$$g=\text{gcd}(m+1, n)$$$ disjoint cycles of equal length. Additionally, if there is a path from node $$$i$$$ and to node $$$j$$$ with sum of the edge weights equal to $$$x$$$, then $$$c_j - c_i \equiv x \pmod {998\,244\,353}$$$. Thus, if we traverse one full cycle, the edge weights along our path must add to $$$0 \pmod {998\,244\,353}$$$. If any cycle does not satisfy this condition, then no solution exists and we can terminate our algorithm. Otherwise, we can always find values $$$c_i$$$ that satisfy the constraints. If we fix the value $$$c_i$$$ for one node in a cycle, it determines the values of $$$c_i$$$ for the remaining nodes in the cycle. In linear algebra terms, each cycle, if satisfiable, consists of $$$1$$$ free variable and $$$\frac{n}{g} - 1$$$ basic variables.

After processing each cycle, we have a total of $$$g$$$ free variables and all other variables $$$c_i$$$ are determined from one of these free variables plus a constant offset. Now, we need to consider the "final" equation. This equation essentially reduces the number of our free variables by $$$1$$$ by allowing us to write one of our free variables as a linear combination of the others plus some constant. Since $$$g \ge 1$$$, we will always have at least one free variable to accommodate this equation. After this step, we have fully solved our system of equations.

To output a construction as the problem asks, we can set each the free variables to any value and solve for the rest of the variables. For instance, the model solution sets all the free variables to $$$0$$$. The final time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int M = 998'244'353;

ll modpow(ll x, ll p) {
    ll a = 1;
    while (p) {
        if (p & 1) a = (a * x) % M;
        x = (x * x) % M;
        p >>= 1;
    }
    return a;
}

ll modinv(ll x) {
    return modpow(x, M-2);
}



int main() {
	int n, m; cin >> n >> m;
    m++;
    int g = __gcd(m, n);

    // input, adjacent differences
    ll a[n], b[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) b[i] = (a[(i+1)%n] - a[i] + M) % M;

    // free variable, difference
    // c[i] = c[fv[i]] + d[i]
    int fv[n];
    ll d[n];
    for (int i = 0; i < g; i++) {
        fv[i] = i; d[i] = 0LL;

        int x = i, y = (i + m) % n;
        while (y != i) {
            fv[y] = i;
            d[y] = (d[x] + b[x]) % M;
            x = y;
            y = (y + m) % n;
        }

        if ((d[x] + b[x]) % M != d[i]) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;

    // construction
    ll x = a[0];
    for (int i = 0; i < m; i++) x += M - d[i];
    x %= M;

    int fac = m / g;
    ll sm = modinv((ll)m/g) * x % M; // c1 + ... + cg = sm (mod M)

    ll c[n];      
    c[0] = sm;
    for (int i = 1; i < g; i++) c[i] = 0;
    for (int i = g; i < n; i++) c[i] = (c[fv[i]] + d[i]) % M;

    for (int i = 0; i < n; i++) cout << c[(i + m - 1) % n] << " \n"[i==n-1];

    // verify
    ll arr[2*n];
    for (int i = 0; i < 2*n; i++) arr[i] = 0;
    for (int i = 0; i < n; i++) {
        arr[i] += c[(i + m - 1) % n];
        arr[i + m] -= c[(i + m - 1) % n];
    }
    for (int i = 1; i < 2*n; i++) arr[i] += arr[i-1];
    for (int i = 0; i < n; i++) arr[i] += arr[i+n];

    for (int i = 0; i < n; i++) {
        arr[i] %= M;
        assert(arr[i] == a[i]);
        // cerr << arr[i] << " \n"[i==n-1];
    }
}

We can notice that the available seats for Person $$$i$$$ depends only on where everyone with a higher number sat. This motivates us to have people sit from highest to lowest order.

We can approach this problem with dynamic programming. Let $$$\text{dp}[i][j]$$$ be the number of ways to add the $$$i$$$ highest people so that there are $$$j$$$ valid places for the next highest person and at least $$$1$$$ invalid place. The lattermost condition ensures that there are exactly $$$2$$$ ways to increase $$$j$$$ or keep it the same: one on either side of the current valid range.

In other words, there is a contribution of $$$2 \text{dp}[i][j]$$$ for each $$$\text{dp}[i+1][j+\ell]$$$ for $$$0 \le \ell \lt k$$$. The number of ways to reduce $$$j$$$ by $$$1$$$ is $$$j - 2k$$$, so there is a contribution of $$$(j - 2k) \cdot \text{dp}[i][j]$$$ to $$$\text{dp}[i+1][j-1]$$$. We might try to transition to a state $$$\text{dp}[i+1][j+\ell]$$$ where $$$i + 1 + j + \ell \ge n$$$, which means that now all remaining places are valid for future people. This contributes $$$(n-i-1)! \cdot \text{dp}[i+1][j+\ell]$$$ to our final answer, and we can ignore it in our subsequent transitions.

#include <bits/stdc++.h>
using namespace std;
 
const int mod = 998'244'353;
 
long long ex(long long a, long long b) {
    if (b == 0) {
        return 1;
    }
    long long r = ex(a, b / 2);
    r *= r;
    r %= mod;
    if (b % 2 == 1) {
        r *= a;
        r %= mod;
    }
    return r;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    // long long dp[n+k][n+1], p[n+k][n+1];
    // memset(dp, 0, sizeof(dp));
    // memset(p, 0, sizeof(p));
    vector<vector<long long>> dp(n + k, vector<long long>(n + 1)), p(n + k, vector<long long>(n + 1));
    if (2 * k + 1 > n) {
        cout << 1;
    } else {
        for (int j = 2 * k; j < n; j++) {
            for (int i = n + k - 1; i >= 2 * k; i--) {
                if (i != n + k - 1) {
                    p[i][j] += p[i + 1][j];
                    p[i][j] %= mod;
                }
                if (i >= j) {
                    dp[i][j] = 1;
                } else {
                    long long den = ex(j, mod - 2);
                    dp[i][j] = (((((i - 2 * k) * dp[i - 1][j - 1]) % mod) + p[i][j]) * den) % mod;
                    dp[i][j] %= mod;
                }
                p[i][j + 1] += 2 * dp[i][j];
                p[i][j + 1] %= mod;
                p[i - k][j + 1] -= 2 * dp[i][j];
                p[i - k][j + 1] += 2 * mod;
                p[i - k][j + 1] %= mod;
            }
        }
        cout << dp[2 * k][n - 1];
    }
    return 0;
}

We can notice that the availible seats for Person $$$i$$$ depends only on where everyone with a higher number sat. This motivates us to have people sit from highest to lowest order.

Define $$$p_i$$$ as the probability that $$$i$$$ people sitting at a table with $$$i$$$ seats satisfy the condition. Denote $$$a_i$$$ as the number of valid ways people numbered $$$1$$$ through $$$i-1$$$ can be arranged in a table with $$$i$$$ seats after fixing person $$$i$$$'s seat. We can see that $$$p_i = \frac{a_i}{(i-1)!}$$$. Our goal is to compute $$$p_n$$$.

Let's see how we can compute $$$a_i$$$. Our trivial base cases are $$$p_i = 1$$$ and $$$a_i = (i-1)!$$$ for $$$1 \le i \le 2k+1$$$, because then any configuration satisfies the condition.

Claim 1: Suppose Person $$$x$$$ and Person $$$y$$$ are seated and have $$$m$$$ empty seats between them. There are $$$m$$$ people, each with a number smaller than $$$\text{min}(x,y)$$$, who want to fill in these seats. The number of ways that they can do this is $$$a_{m+1}$$$.

Proof: Every seat other than the $$$m$$$ empty ones and the $$$2$$$ occupied ones are irrelevant. If we remove them from the problem and merge the two seated people, we now have a $$$m+1$$$ seats with the highest-numbered person already seated. By definition, the number of ways to arrange the remaining $$$m$$$ people is $$$a_{m+1}$$$.

Claim 2: Suppose Person $$$i$$$ and Person $$$i-1$$$ have sat a distance $$$d \le k$$$ from each other on a table with $$$i \ge 3$$$ seats. The number of ways to place the remaining $$$i-2$$$ people is given by $$$a_{i-d} \cdot {i-2 \choose d-1} \cdot (d-1)! = a_{i-d} \cdot \frac{(i-2)!}{(i-d-1)!}$$$

Proof: We choose any $$$d-1$$$ people to put between Person $$$n-1$$$ and Person $$$n$$$, and there are $$$(d-1)!$$$ ways to order them. Since $$$d \le k$$$, these $$$d-1$$$ people will always be covered) For the remaining $$$n-d-1$$$ seats, we can apply Claim 1 and determine there are $$$a_{n-d}$$$ ways to do so.

Let's use Claim 2 to find a recurrence formula for $$$a_i$$$ for $$$i \gt 2k+1$$$. If we have a table with $$$i$$$ seats and we fix person $$$i$$$, for each $$$d$$$ from $$$1$$$ to $$$k$$$ inclusive there are $$$2$$$ ways to place person $$$i-1$$$ a distance $$$d$$$ away. Thus, our recurrence is

This formula simplifies further if we use $$$p_i$$$ instead of $$$a_i$$$. Since $$$p_i = \frac{a_i}{(i-1)!}$$$, we have

.

Thus, we have proved that $$$p_i$$$ is equal to $$$\frac{2}{i-1}$$$ times the sum of the previous $$$k$$$ values of $$$p_i$$$. The previous $$$k$$$ values can be maintained with a sliding window technique, allowing us to compute $$$p_n$$$ in $$$O(n)$$$.

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

const int mod = 998'244'353;

long long ex(long long a, long long b) {
    if (b == 0) {
        return 1;
    }
    long long r = ex(a, b / 2);
    r *= r;
    r %= mod;
    if (b % 2 == 1) {
        r *= a;
        r %= mod;
    }
    return r;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n, k;
    long long sum;
    cin >> n >> k;
    vector<long long> dp(n);
    if (2 * k > n) {
        cout << 1;
    } else {
        for (int i = 0; i < 2 * k; i++) {
            dp[i] = 1;
        }
        sum = 2 * k;
        for (int i = 2 * k; i < n; i++) {
            dp[i] = (sum * ex(i, mod - 2)) % mod;
            dp[i] %= mod;
            sum += 2 * dp[i];
            sum -= 2 * dp[i - k];
            sum += 2 * mod;
            sum %= mod;
        }
        cout << dp[n - 1];
    }
	return 0;
}

Given an array of length $$$n$$$ and a number $$$m$$$, there is a straightforward way to find the maximum bitwise AND of a length $$$k$$$ subsequence. Iterate from the most significant bit to the lowest. If there are $$$k$$$ or more numbers in the array with the current bit set to $$$1$$$, remove any numbers that have the bit set to $$$0$$$. Otherwise, do nothing. The answer is the bitwise AND of the remaining numbers.

To solve the original problem, we will define $$$\text{dp}[i][j]$$$ ($$$1 \le i \le m$$$, $$$k \le j \le n$$$) to be the number of ways to fill in the $$$i$$$ highest bits in an array of length $$$n$$$ so that the algorithm above ends with $$$j$$$ numbers remaining whose bitwise AND is equal to the $$$i$$$ highest bits of $$$x$$$. Transitions from $$$i$$$ to $$$i+1$$$ depend on the value of the $$$i+1$$$-th bit in $$$x$$$.

If the $$$i+1$$$-th bit of $$$x$$$ is $$$0$$$, we need to make sure that there are less than $$$k$$$ numbers in the array with $$$i+1$$$-th bit set to $$$1$$$. The remaining $$$n-j$$$ numbers that we discarded earlier can have their bits set to either $$$0$$$ or $$$1$$$.

The factor that each $$$\text{dp}[i][j]$$$ is multiplied by depends only on $$$j$$$ and can be precomputed beforehand.

If the $$$i+1$$$-th bit of $$$x$$$ is $$$1$$$, we can reduce the size of our group. The discarded $$$n-j$$$ numbers again can be either $$$0$$$ or $$$1$$$.

We can optimize this transition with FFT/NTT. Letting $$$d = \ell - j$$$, we can rewrite the transition as:

Since our transitions are either $$$O(n)$$$ or $$$O(n \log n)$$$ and we have $$$m$$$ layers of our $$$\text{dp}$$$, the final time complexity is $$$O(nm \log n)$$$.

#include <bits/stdc++.h>

using namespace std;

template <const long long mod>
struct Mod_Int {
  int x;
  Mod_Int() : x(0) {}
	Mod_Int(int y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  Mod_Int(long long y) : x((int)y >= 0 ? (int)y % mod : (mod - (-(int)y) % mod) % mod) {}
  static int get_mod() { return mod; }
  Mod_Int &operator+=(const Mod_Int &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  Mod_Int &operator-=(const Mod_Int &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  Mod_Int &operator*=(const Mod_Int &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  Mod_Int &operator/=(const Mod_Int &p) {
    *this *= p.inv();
    return *this;
  }
  Mod_Int operator-() const { return Mod_Int(-x); }
  Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; }
  Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; }
  Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; }
  Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; }
  bool operator==(const Mod_Int &p) const { return x == p.x; }
  bool operator!=(const Mod_Int &p) const { return x != p.x; }
  Mod_Int inv() const {
    assert(*this != Mod_Int(0));
    return pow(mod - 2);
  }
  Mod_Int pow(long long k) const {
    Mod_Int now = *this, ret = 1;
    for (; k > 0; k >>= 1, now *= now) {
      if (k & 1) ret *= now;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const Mod_Int &p) {
    return os << p.x;
  }
  friend istream &operator>>(istream &is, Mod_Int &p) {
    long long a;
    is >> a;
    p = Mod_Int<mod>(a);
    return is;
  }
};
 
template <typename T> struct NumberTheoreticTransform {
  static int max_base;
  static T root;
  static vector<T> r, ir;
  NumberTheoreticTransform() {}
  static void init() {
    if (!r.empty()) return;
    int mod = T::get_mod();
    int tmp = mod - 1;
    root = 2;
    while (root.pow(tmp >> 1) == 1) root += 1;
    max_base = 0;
    while (~tmp & 1) tmp >>= 1, max_base += 1;
    r.resize(max_base), ir.resize(max_base);
    for (int i = 0; i < max_base; i++) {
      r[i] = - root.pow((mod - 1) >> (i + 2));
      ir[i] = r[i].inv();
    }
  }
  static void ntt(vector<T> &a) {
    init();
    int n = (int) a.size();
    assert((n & (n - 1)) == 0);
    assert(n <= (1 << max_base));
    for (int k = n; k >>= 1;) {
      T w = 1;
      for (int s = 0, t = 0; s < n; s += 2 * k) {
        for (int i = s, j = s + k; i < s + k; i++, j++) {
          T x = a[i], y = w * a[j];
          a[i] = x + y, a[j] = x - y;
        }
        w *= r[__builtin_ctz(++ t)];
      }
    }
  }
  static void intt(vector<T> &a) {
    init();
    int n = (int) a.size();
    assert((n & (n - 1)) == 0);
    assert(n <= (1 << max_base));
    for (int k = 1; k < n; k <<= 1) {
      T w = 1;
      for (int s = 0, t = 0; s < n; s += 2 * k) {
        for (int i = s, j = s + k; i < s + k; i++, j++) {
          T x = a[i], y = a[j];
          a[i] = x + y, a[j] = (x - y) * w;
        }
        w *= ir[__builtin_ctz(++ t)];
      }
    }
    T iv = T(n).inv();
    for (auto &x : a) x *= iv;
  }
  static vector<T> convolution(vector<T> a, vector<T> b) {
    int k = (int) a.size() + (int) b.size() - 1, n = 1;
    while (n < k) n <<= 1;
    a.resize(n), b.resize(n);
    ntt(a), ntt(b);
    for (int i = 0; i < n; i++) a[i] *= b[i];
    intt(a), a.resize(k);
    return a;
  }
};
template <typename T> int NumberTheoreticTransform<T>::max_base = 0;
template <typename T> T NumberTheoreticTransform<T>::root = T();
template <typename T> vector<T> NumberTheoreticTransform<T>::r  = vector<T>();
template <typename T> vector<T> NumberTheoreticTransform<T>::ir = vector<T>();

using mint = Mod_Int<998244353>;
using NTT = NumberTheoreticTransform<mint>;

const int mxn = 2e5+5;

mint fc[mxn], iv[mxn], pow2[mxn];
void init() {
	fc[0] = mint(1);	pow2[0] = mint(1);
	for (int i = 1; i < mxn; i++) fc[i] = fc[i-1] * mint(i);
	for (int i = 0; i < mxn; i++) iv[i] = fc[i].inv();
	for (int i = 1; i < mxn; i++) pow2[i] = pow2[i-1] * mint(2);
}
mint choose(int n, int k) {
  assert(n >= 0 && k >= 0 && k <= n);
	return fc[n] * iv[k] * iv[n-k];
}

int main() {
	init();

	int n, m, k, x; 
	cin >> n >> m >> k >> x;

	vector<mint> coefs(n+1);
	mint cur = pow2[k] - mint(1);
	for (int i = k; i <= n; i++) {
		coefs[i] = cur * pow2[n-i];
		cur *= 2; 
		cur -= choose(i, k-1);
	}

	vector<mint> dp(n+1);
	dp[n] = mint(1);

	for (int i = m-1; i >= 0; i--) {
		if (x & (1 << i)) {
			for (int j = 0; j <= n; j++) dp[j] *= pow2[n-j] * fc[j];

			vector<mint> invs(n+1);
			for (int j = 0; j <= n; j++) invs[n-j] = iv[j];

			vector<mint> res = NTT::convolution(dp, invs);
			for (int j = n; j <= 2*n; j++) dp[j-n] = res[j];
			for (int j = 0; j <= n; j++) {
				if (j < k) dp[j] = mint(0); 
				else dp[j] *= iv[j];
			}
		} else {
			for (int j = 0; j <= n; j++)[user:flight][user:treewave] dp[j] *= coefs[j];
		}
	}

	mint ans = 0;
	for (int i = k; i <= n; i++) ans += dp[i];
	cout << ans << endl;
}

To be added by flight

To be added by flight

To be added by flight

To be added by flight

Rewrite $$$c$$$ in its binary representation. Let's call $$$c$$$ good if it has an even number of trailing zeros, possibly none.

Claim: Assume $$$c \gt 1$$$. If $$$c$$$ is good, then the current player can always make $$$c$$$ not good after their turn. On the flip side, if $$$c$$$ is not good, no matter what the current player does, it will always be good after their turn.

Proof: For the first part, if $$$c$$$ has $$$2$$$ or more trailing zeros, we can divide by $$$2$$$ to leave an odd number of trailing zeros. If $$$c$$$ doesn't have trailing zeros, we can subtract $$$1$$$ to leave exactly one trailing zero. In both of these cases, $$$c$$$ is not good after the turn. For the second part, if $$$c$$$ has an odd number of trailing zeros, dividing by $$$2$$$ will leave an even number of trailing zeros. Subtracting $$$1$$$ will make the last digit of $$$c$$$ equal to $$$1$$$, which means $$$c$$$ is good.

Thus, if $$$c$$$ is good for the current player, then with the correct move, it is certain that $$$c$$$ will be good on their next turn. Since $$$c$$$ must eventually equal $$$1$$$, and $$$1$$$ is good, this means that if $$$c$$$ is good for the current player, they can ensure that $$$c$$$ will be $$$1$$$ on their turn, meaning that they eat the last cookie and win the game. So if $$$c$$$ is good initially, then Cookie Monster wins, otherwise Elmo wins.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
signed main() {
	ios::sync_with_stdio(false);
        cin.tie(0);
        ll x;
        cin >> x;
        if (x % 2 == 1) {
                cout << "Cookie Monster" << endl;
        } else {
                int cnt = 0;
                while(x % 2 == 0 && x) {
                        x /= 2;
                        cnt++;
                }
                if (cnt % 2 == 0) {
                        cout << "Cookie Monster" << endl;
                } else {
                        cout << "Elmo" << endl;
                }
        }
}

Together, Cookies Monster and Elmo remove $$$n+m$$$ cookies in their turns. They will keep doing this until the number of cookies and left is less than $$$n+m$$$. If the number of cookies left is $$$0$$$, that means Elmo took the last cookie and there are none left. Otherwise, if the number of cookies left is less than or equal to $$$n$$$, Cookie Monster can remove all the remaining cookies. If this is not the case, Elmo wins.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n, m, c; cin >> n >> m >> c; 
    c--;
    c %= n + m;
    if (c < n) cout << "Cookie Monster" << endl;
    else cout << "Elmo" << endl;
}

Let's visualize this problem as a bar graph, where the $$$x$$$ axis represents each friend, and the $$$y$$$ axis represents the amount of cookies each friend has initially.

In terms of the bar graph, an operation of $$$[L, R]$$$ would be adding a row of cookies at the top from $$$L$$$ to $$$R$$$, and letting that row to "fall" until each of the stacks in $$$[L, R]$$$ are increased by one. However, we can observe that we don't actually have to let the row fall. That is, we can represent each operation as just a stationary $$$1$$$ by $$$(R-L+1)$$$ rectangle in the grid.

It is easy to see that we will need at least $$$T = max(arr)$$$ time no matter what $$$M$$$ we're given. So, let's consider the max amount of additional cookies we can handle if we're only allocated $$$max(arr)$$$ time. Here, we can do at most $$$T$$$ operations (add $$$T$$$ rectangles) as each operation takes $$$1$$$ second. Additionally, all rectangles have to be placed below height $$$T$$$. The problem then becomes how to add the maximum amount of 1-high rectangles into the bar graph that the total area of the rows we added is maximum.

It is obvious that we want to draw rectangles to the maximum width we can without overlapping with bars. This leads to the following important observation about the rectangles. Suppose a rectangle has a $$$y$$$ value less than another rectangle and that the lower rectangle overlaps in $$$x$$$ with the higher rectangle. The lower rectangle is guaranteed to have $$$x$$$ values completely contained/under the higher rectangle, implying that it's width is also less than or equal to the top rectangle. This means that we can apply a greedy argument. We want to greedily place the largest width rectangles which start at the top, and all next-biggest rectangles will already be under some rectangle that we already placed. One way we can simulate this is to use a priority queue of rectangles, which takes $$$O(n \log n)$$$. Each time we place a rectangle, we add the adjacent rectangles underneath. These rectangles are found with a segment tree; repeatedly query for bars with height one below the placed bar.

From this process, we have found the greatest $$$M$$$ that can be handled if $$$T = max(arr)$$$. What if $$$T = max(arr)+1$$$. Well, we get 1 extra operation compared to when we had $$$T = max(arr)$$$. It happens conveniently that in the bar graph, the maximum height at which we can place rectangles is increased by 1 too! That means we can greedily place 1 rectangle that fills that entire row, and we can be confident that nothing is better than that. This argument can be used inductively for $$$T+2, T+3, ...$$$.

In this way, we have found a general formula for the maximum $$$M$$$ for each $$$T$$$: $$$M = [M @ T = max(arr)] + (T-max(arr)) * N$$$. It is easy to see how this can be used to solve queries in $$$O(1)$$$.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
template<class T> struct SimpleSegmentTree {
	int len;
        vector<T> segtree;
	T DEFAULT = {-1, -1};
	SimpleSegmentTree(int _len) : len(_len), segtree(_len * 2, DEFAULT) {}
 	void set(int ind, T val) {
		ind += len; segtree[ind] = val;
		for (; ind > 1; ind /= 2) segtree[ind / 2] = merge(segtree[ind], segtree[ind ^ 1]);
	}
 	T query(int start, int end) {
		T res = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { res = merge(res, segtree[start++]); }
			if (end % 2 == 1) { res = merge(res, segtree[--end]); }
		}
    	return res;
	}
        T merge(T a, T b) { 
		if (a.first > b.first) return a;
		else if (a.first == b.first) {
			if (a.second < b.second) return a;
		}
		return b;
	}
};
using SegTree = SimpleSegmentTree<pair<int, int>>; // (value, index)
struct block {
	int L, R, H, LEN;
};
struct compare {
    bool operator()(block const& a, block const& b) {
        return a.LEN < b.LEN;
	}
};
 
SegTree tree(0); //tree keeps track of highest nodes online. Used to get next "blocks" in O(log(N))
priority_queue<block, vector<block>, compare> pq; // (length, [L, R])
int N, Q;
 
void populate(block b) { //push adjacent blocks into PQ
	int nxtL = b.L;
	while (true) {
		pair<int, int> p = tree.query(b.L, b.R + 1); //p is biggest, leftmost
		if (p.first != b.H-1) break;
		block nxt; nxt.L = nxtL; nxt.R = p.second-1; nxt.H = b.H-1; nxt.LEN = nxt.R-nxt.L+1;
		nxtL = p.second + 1;
		tree.set(p.second, {-1, -1});
		if (nxt.LEN > 0) pq.push(nxt);
	}
	block nxt; nxt.L = nxtL; nxt.R = b.R; nxt.H = b.H-1; nxt.LEN = nxt.R-nxt.L+1;
	if (nxt.LEN > 0) pq.push(nxt);
}
 
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
 
	cin>>N>>Q;
	tree.segtree.resize(2 * N,  {-1, -1});
	tree.len = N;
	 
	for (int i=0; i<N; i++) {
		int a; cin>>a; tree.set(i, {a, i});
	}
 
	int base = 0, T = tree.query(0, N).first;
	block b; b.L = 0; b.R = N-1; b.LEN = b.R-b.L+1; b.H = T+1;
	populate(b);
	
	for (int i=0; i<T; i++) { //you can take T operations at most
		if (pq.empty()) break;
		block b = pq.top(); pq.pop();
		base += b.LEN;
		populate(b);
	}
 
	int zero = 0;
	while (Q--) { //for more time, greedily take more blocks on top
		int M; cin>>M;
		M = max(zero, M-base);
		int ans = T;
		ans += (M / N);
		M -= (M / N) * N;
		if (M > 0) ans++;
		cout<<ans<<"\n";
	}
}

The solution exists if and only if $$$n \equiv 0 \pmod 4$$$ or $$$n \equiv 1 \pmod 4$$$. We can prove that it impossible to find a solution if $$$n \equiv 2 \pmod 4$$$ or $$$n \equiv 3 \pmod 4$$$. (Hint: Consider the parity of the sum of the number of chips on all the uneaten cookies and how this changes after each day. This sum should equal $$$0$$$ at the end.)

Let's first see how to construct it for the case $$$n \equiv 0 \pmod 4$$$. There are probably many ways to construct a solution, some of them are probably simpler, but this is our solution.

We will use each of the first $$$n$$$ numbers in a different operation. So now the problem can be thought of as choosing pairs of the last $$$2n$$$ numbers whose differences map to the numbers from $$$1$$$ to $$$n$$$.

Consider the even differences for now, the numbers $$$2$$$, $$$4$$$, ... $$$n-2$$$, $$$n$$$. We can cover all of these with pairs $$$(2n, 3n)$$$, $$$(2n+1, 3n-1)$$$, ..., $$$(\frac{5n}{2}-1, \frac{5n}{2}+1)$$$. This uses up the values from $$$2n$$$ to $$$3n$$$ inclusive with the singular exception of $$$\frac{5n}{2}$$$. We will let this be the larger value in the pair with the difference $$$n-1$$$. The smaller value in that pair will be $$$\frac{3n}{2}+1$$$.

Now we have the numbers from $$$n+1$$$ to $$$\frac{3n}{2}$$$ inclusive and $$$\frac{3n}{2}+2$$$ to $$$2n-1$$$ inclusive remaining, and can use the odd-numbered pairs from $$$1$$$ to $$$n-3$$$, inclusive.

We use the $$$\frac{n}{2}-1$$$ pair to cover $$$\frac{3n}{2}$$$ and $$$2n-1$$$. Now, the pairs that are greater than $$$\frac{n}{2}-1$$$ can fit in $$$(n+1, 2n-2)$$$, $$$(n+2, 2n-3)$$$, ... $$$(\frac{5n}{4}-1, \frac{7n}{4})$$$. All of the pairs that are less than $$$\frac{n}{2}-1$$$, excluding $$$1$$$ for the moment, can fit in $$$(\frac{5n}{4}+2, \frac{7n}{4}-1)$$$, $$$(\frac{5n}{4}+3, \frac{7n}{4}-2)$$$, ... $$$(\frac{3n}{2}-1, \frac{3n}{2}+2)$$$. And finally, the $$$1$$$ fits perfectly in the remaining gap of $$$(\frac{5n}{4}, \frac{5n}{4}+1)$$$.

The construction for the second case with $$$n \equiv 1 \pmod 4$$$ is similar, but some of the details are slightly different.

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"
 
void solve() {
	int n; cin >> n;
	
	if (n % 4 == 2 || n % 4 == 3) {
		cout << "No" << endl;
		return;
	}
 
	cout << "Yes" << endl;
	
	if (n == 1) {
	        cout << "1 2 3" << endl;
	} else if (n == 4) {
		cout << "1 5 6" << endl;
        cout << "2 8 10" << endl;
		cout << "3 9 12" << endl;
		cout << "4 7 11" << endl;
	} else if (n == 5) {
		cout << "1 5 6" << endl;
		cout << "2 10 12" << endl;
		cout << "3 11 14" << endl;
		cout << "4 9 13" << endl;
		cout << "7 8 15" << endl;
	} else if (n % 4 == 0) {
		int l = 2*n, r = 3*n;
		while (l != r) {
			cout << r - l << " " << l << " " << r << endl;
			l++; r--;
		}
 
		cout << n - 1 << " " << 3 * n / 2 + 1 << " " << 5 * n / 2 << endl;
		cout << n / 2 - 1 << " " << 3 * n / 2 << " " << 2 * n - 1 << endl;
 
		l = n + 1; r = 2 * n - 2;
		while (r - l > n / 2 - 1) {
			cout << r - l << " " << l << " " << r << endl;
			l++; r--;
		}
 
		l = 3 * n / 2 - 1; r = 3 * n / 2 + 2;
		while (r - l < n / 2 - 1) {
			cout << r - l << " " << l << " " << r << endl;
			l--; r++;
		}
 
		cout << 1 << " " << 5 * n / 4 << " " << 5 * n / 4 + 1 << endl;
	} else {
		int l = 2 * n + 1, r = 3 * n;
		while (l != r) {
			cout << r - l << " " << l << " " << r << endl;
			l++; r--;
		}
 
		cout << n << " " << 3 * n / 2 + 1 << " " << 5 * n / 2 + 1 << endl;
		cout << n / 2 - 1 << " " << 3 * n / 2 + 2 << " " << 2 * n << endl;
 
		l = n + 1; r = 2 * n - 1;
		while (r - l > n / 2 - 1) {
			cout << r - l << " " << l << " " << r << endl;
			l++; r--;
		}
 
		l = 3 * n / 2; r = 3 * n / 2 + 3;
		while (r - l < n / 2 - 1) {
			cout << r - l << " " << l << " " << r << endl;
			l--; r++;
		}
 
		cout << 1 << " " << 5 * n / 4 + 1 << " " << 5 * n / 4 + 2 << endl;
	}
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
}

In this problem, you just have to consider several cases. We orient both the original and cut pieces of cake so that it shares the bottom left corner. There are two ways the piece cake can be oriented, either with the side of length $$$a$$$ vertical or horizontal. Additionally, the first cut that we make can either be horizontal or vertical. Thus, there are $$$4$$$ main cases to consider. Make sure to check that a given orientation is possible (i.e. the cut piece of cake lies completely inside the original one). Also, carefully handle the cases when the original and cut pieces of cake have the same side length or are equal, in which case you may only need to make $$$1$$$ or $$$0$$$ cuts.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int x, y, a, b; cin >> x >> y >> a >> b;
    int ans = 2000000000;
    if (a == x && b == y || a == y && b == x) ans = 0;
    if (a <= x && b <= y) {
        ans = min(ans, x + (a == x ? 0 : b));
        ans = min(ans, y + (b == y ? 0 : a));
    }
    if (a <= y && b <= x) {
        ans = min(ans, x + (b == x ? 0 : a));
        ans = min(ans, y + (a == y ? 0 : b));
    }
    if (ans == 2000000000) ans = -1;
    cout << ans << endl;
}

We can solve this problem with Dynamic Programming.

Let $$$dp[i][j][k]$$$ represent the maximum width of a rectangular piece of cake that you can place so that the right edge of the cake lies on column $$$i$$$ and goes from rows $$$j$$$ to $$$k$$$. From the constraints, we can infer that $$$n \leq 500$$$, so this will not use up too much time or memory.

To calculate $$$dp$$$, we can move across columns from left to right. If the current cake is unfilled for every location along column $$$i$$$ between rows $$$j$$$ and $$$k$$$, we can update $$$dp[i][j][k] = dp[i-1][j][k] + 1$$$. Otherwise, it is impossible to place a piece of cake there and $$$dp[i][j][k] = 0$$$. We can quickly check this using a 2D prefix sum array.

Note that if a piece with width $$$m$$$ can be placed with its right edge at a certain $$$dp$$$ state, then so can a piece of length $$$m-1$$$. For each fixed height ($$$k-j$$$), we can store the $$$dp$$$ values in an array and take the suffix sum, accounting for the previous fact. This allows us to precompute the answers to all queries.

#include <bits/stdc++.h>
 
#define int long long
using namespace std;
 
signed main() {
    int n, m, q; cin >> n >> m >> q;
    
    bool grid[n][m];
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) grid[i][j] = (s[j] == '1');
    }
    
    int pref[n+1][m+1];
    memset(pref, 0, sizeof(pref));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pref[i][j] += (int)grid[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
        }
    }
    
    // maximum width of subgrid with right column $$$i$$$ and height from rows $$$j$$$ to $$$k$$$.
    int dp[m][n][n];
    int pos[n][m];
    memset(dp, 0, sizeof(dp));
    memset(pos, 0, sizeof(pos));
    for (int j = 0; j < n; j++) {
        for (int k = j; k < n; k++) {
            if (pref[k+1][1] - pref[k+1][0] - pref[j][1] + pref[j][0] == 0) {
                dp[0][j][k] = 1;
                pos[k-j][0]++;
            }
        }
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = j; k < n; k++) {
                if (pref[k+1][i+1] - pref[k+1][i] - pref[j][i+1] + pref[j][i] == 0) {
                    dp[i][j][k] = dp[i-1][j][k]+1;
                    pos[k-j][dp[i][j][k]-1]++;
                } else dp[i][j][k] = 0;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = m-2; j >= 0; j--) {
            pos[i][j] += pos[i][j+1];
        }
    }
    
    while (q--) {
        int h, w; cin >> h >> w;
        h--; w--;
        cout << pos[h][w] << endl;
    } 
}

The number of good snacks is only limited by $$$a$$$ and $$$b$$$ since $$$c$$$ can be disregarded since all those cookies were stolen. The number of good snacks is simply which type of cookie has a smaller number of servings and will run out first.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int x, y, z;
	cin >> x >> y >> z;
	cout << min(x, y) << endl;
}

We can keep track of the number of occurrences of each letter in $$$A$$$. Then we can keep track of the number of occurrences of each letter in $$$B$$$. Since we can rearrange A however we like, we can rearrange $$$A$$$ such that we form the string $$$B$$$ as much as possible as a prefix. To find out the maximum number of copies of $$$B$$$ each letter can form, we should divide the occurrences of each letter in $$$A$$$ by the occurrences of each letter in $$$B$$$, discarding any remainders. The answer is the minimum value of these quotients.

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
        string a, b;
        cin>>a>>b;
        int cnta[26];
        int cntb[26];
        memset(cnta, 0, sizeof(cnta));
        memset(cntb, 0, sizeof(cntb));
        for(char c: a){
                cnta[c-'a']++;
        }
        for(char c: b){
                cntb[c-'a']++;
        }
        int ret = INT_MAX;
        for(int i=0; i<26; i++){
                if(cntb[i]>0){
                        ret = min(ret, cnta[i]/cntb[i]);
                }
        }
        cout<<ret<<endl;
}

An arithmetic sequence can be formed between numbers only if they all have the same common remainder when divided by $$$d$$$. After separating the values of the array based on their modulus $$$d$$$, for each modulus, we sort the array. Then, we can start off with an empty arithmetic sequence and loop through the array, checking if adding the current element to the end of the arithmetic sequence and possibly removing the first element will create a new arithmetic sequence of length $$$m$$$ that will increase our answer by $$$1$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n, d, m; cin >> n >> d >> m;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    map<int, vector<int>> mp;
    for (int i = 0; i < n; i++) {
        int rem = arr[i] % d;
        int b = (arr[i]-rem)/d;
        if (!mp.count(rem)) mp[rem] = vector<int>();
        mp[rem].push_back(b);
    }
    
    int ans = 0;
    for (auto x : mp) {
        vector<int> v = x.second;
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        
        int l = v.size();
        for (int i = l-1; i >= 0; i--) {
            if (l - i == m) {
                l--;
                ans++;
            } 
            if (i > 0 && v[i-1]+1 < v[i]) l=i;
        }
    }
    
    cout << ans << endl;
    
}

To ensure we decrease the monsters health by $$$1$$$, we can either upgrade the tower it is currently at or perform the optimal combination of upgrades for all the node's children, since we don't know which child it will go to. If the current node is a leaf, then the optimal combination is just upgrading the current node. To compute the answer, we can run a depth first search where we calculate the minimum cost to decrease the monster's health by $$$1$$$ by calculating the minimum cost for each node of the tree by comparing it with the sum of the minimum costs for each its children, rooting the tree at node $$$1$$$.

#include <bits/stdc++.h>
using namespace std;
 
const int mn=2e5;
vector<int> adj[mn];
bool visited[mn]={0};
int cost[mn];
 
int dfs(int node) {
	visited[node]=true;
	long long subtree_sum=0;
	for(int u:adj[node]) {
		if(!visited[u]) {
			subtree_sum+=dfs(u);
		}
	}
	if(subtree_sum==0) return cost[node];
	return min((long long)cost[node], subtree_sum);
}
 
int main() {
	int n, h; cin >> n >> h;
	for(int i=0; i<n; i++) cin >> cost[i];
	for(int i=0; i<n-1; i++) {
		int u, v; cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cout << (long long)dfs(0)*h;
}

Notice that since the original deck is sorted, each of the stacks will be in decreasing order from top to bottom. When we stack the stacks on top of each other, each stack will still be in decreasing order. Thus, whenever we see two adjacent cookies $$$a_i$$$ and $$$a_{i+1}$$$ in increasing order ($$$a_i \lt a_i+1$$$) this must mean that $$$a_i$$$ and $$$a_{i+1}$$$ were part of different stacks. So we can loop through the array and count the number of adjacent cookies that are in increasing order, adding $$$1$$$ to get our answer.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) cin >> arr[i];
        int ans=1;
        for (int i = 0; i < n-1; i++) {
            if (arr[i] < arr[i+1]) ans++;
        }
        cout << ans << endl;
    }
}

The number of points on either side of the line is invariant. For the provided input, there is $$$1$$$ point to the left of the line.

Call the convex hull of all the points the \textit{outer hull}, and the convex hull of the remaining points the \textit{inner hull}. The outer and inner hull can be computed in $$$O(N)$$$ with Andrew's algorithm. To maintain the invariant, the line must always cross the outer hull but never cross the inner hull.

At some moment, call the current pivot $$$P$$$. The new pivot must be one of three points:

1. The lone ``invariant'' point $$$Q$$$
2. The point $$$R$$$ on the outer hull with minimum $$$∠QPR$$$
3. The point $$$S$$$ on the inner hull with minimum $$$∠QPS$$$

$$${Q, R, S}$$$ can be maintained by two pointers which are incrementally updated. The line switches pivots $$$O(N)$$$ times before returning to the initial state. Total complexity is therefore $$$O(N)$$$.

Visuals:

• https://www.youtube.com/watch?v=M64HUIJFTZM
• https://www.desmos.com/calculator/eec1g1zfh9
• https://www.desmos.com/calculator/kylvoqkmcs

Bonus:

1. Solve the general case! (pivot is any point to begin)
2. Generate test data! Specifically, generate a set of points in ``seemingly'' uniformly random manner so that no three points are collinear

from functools import cmp_to_key
 
def cross(p, q, r):
    v = (r[0]-p[0], r[1]-p[1])
    w = (q[0]-p[0], q[1]-p[1])
    return (v[1]*w[0] - v[0]*w[1])
 
def convex_hull(pnts):
    lv, li = min((v,i) for i,v in enumerate(pnts))
    cnds = sorted({*pnts}-{lv}, key=cmp_to_key(lambda a, b : cross(lv, a, b)))
 
    hull = [lv]
    for pt in cnds:
        while len(hull) > 1 and cross(hull[-2], hull[-1], pt) >= 0:
            hull.pop()
        hull.append(pt)
    return hull
 
def main():
    N = int(input())
    pnts = [tuple(map(int, input().split())) for i in range(N)]
 
    oh = convex_hull(pnts)
    if len(oh) == len(pnts):
        print(len(oh))
        if pnts[1]==oh[-1]:
            print('\n'.join(f"{p[0]} {p[1]}" for p in [oh[-1],oh[1],oh[0]]+oh[2:-1]))
        else:
            print('\n'.join(f"{p[0]} {p[1]}" for p in [oh[1],oh[0]]+oh[2:]))
        return
 
    ih = convex_hull([*{*pnts} - {*oh}])
 
    pivs = [pnts[1]]
    ii = 0
 
    st = 0
    if pnts[1]==oh[1] and oh[1][1] > oh[0][1]:
        pivs.append(oh[0])
        st = 1
 
    for oi in [*range(st,len(oh))]+[0]:
        if len(ih)==2:
            if cross(oh[oi], ih[ii], ih[(ii+1)%len(ih)]) > 0: ii = (ii+1)%len(ih)
        elif len(ih)>2:
            while cross(oh[oi], ih[ii], ih[(ii+1)%len(ih)]) > 0: ii = (ii+1)%len(ih)
 
        while cross(pivs[-1], ih[ii], oh[(oi+1)%len(oh)]) < 0:
            pivs.append(ih[ii])
            ii = (ii+1)%len(ih)
 
        pivs.append(oh[(oi+1)%len(oh)])
        pivs.append(oh[oi])
        oi = (oi+1)%len(oh)
 
    vis = {pt:len(pivs)-i-1 for i,pt in enumerate(pivs[::-1])}
    print(len(vis))
    print('\n'.join(f"{pt[0]} {pt[1]}" for i,pt in enumerate(pivs) if vis[pt]==i))
 
if __name__=='__main__': main()

The following solutions consider the graph theoretic interpretation of finding the number of permutation graphs of size $$$n$$$ such that all cycles have a length that is a multiple of $$$k.$$$

Solution 1

There are two components to this problem. The first component is deciding which labels go to which cycles (and deciding the cycle sizes themselves), and the second component is deciding how to order labels within their own cycles.

The second component is obvious: given $$$n$$$ labels, it is known that there are $$$(n-1)!$$$ ways to order them into a cycle. This is because there are $$$n!$$$ ways to order them in a line, and $$$n$$$ repetitions due to cyclic shifting.

The first component, however, is more difficult. We now turn to the use of generating functions.

Consider the generating function $$$f(x) = \frac{x^k}{k!} * (k-1)! + \frac{x^{2k}}{(2k)!} * (2k-1)! + \dots.$$$ This is the exponential generating function of the cycle reordering we are allowed to perform. More specifically, given we want to add a cycle of length $$$m$$$ to the graph, the coefficient $$$\left[\frac{x^m}{m!}\right] f(x)$$$ gives us the number of ways to orient the labels within the cycle.

The nice thing about exponential generating functions is that upon exponentiation, they automatically perform partitioning of labels into the corresponding sets, while simultaneously reordering them. This is shown by the fact that

where $$$B = B_0 + \frac{B_1}{1!}x + \frac{B_2}{2!}x^2 + \dots.$$$ This is essentially doing the partitioning and the reordering at the same time.

Now, consider the generating function $$$e^{f(x)} = 1 + \frac{f(x)}{1!} + \frac{f(x)^2}{2!} + \dots.$$$ This gets rid of the labeling that we assign to each "container" when we do the partioning, and represents the exponential generating function of the total number of graphs that have cycles of length all multiples of k.

Notice that $$$f(x) = \frac{x^k}{k} + \frac{x^{2k}}{2k} + \dots = \frac{1}{k}\log{\left(\frac{1}{1-x^k}\right)},$$$ due to the Taylor Series. All that remains is computing the coefficient of $$$x^n$$$ in $$$e^{f(x)} = \left(\frac{1}{1-x^k}\right)^{\frac{1}{k}}.$$$ This can be done easily using the extended binomial theorem, obtaining a closed form as shown in the code of the solution.

Solution 2

Start from the 1st node, and randomly choose $$$a_1,$$$ the node that $$$a_1$$$ points to. Likewise, choose the node that $$$a_{a_1}$$$ points to and so on until you choose $$$k$$$ nodes. Now, you have the option of either closing the cycle or continuing on, meaning that any valid node to walk to is fine. This holds true when we have visited any multiple of $$$k$$$ number of nodes.

Note that when we have visited a number of nodes, $$$x$$$, that is not a multiple of $$$k, $$$ the probability that we don't accidentally close a cycle is $$$\frac{n - x}{n - x + 1}, $$$ as there are $$$n - x + 1$$$ nodes that don't have a node pointing to it, and all nodes are valid to visit except for the node that closes the current cycle.

Therefore, we can compute the total probability of a random walk giving a correct permutation graph as $$$\prod_{x = 1, x \not\equiv 0 \pmod{k}}^{n-1} \frac{n-x}{n-x+1}.$$$ All that remains is to multiply by $$$n!,$$$ giving us our final answer.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define int ll
const int MOD = 1e9+7;
 
template<const int MOD> struct Modular {
    static const int mod = MOD;
    int v; explicit operator int() const { return v; }
    Modular():v(0) {}
    Modular(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
    friend Modular mpw(Modular a, ll p) {
        Modular ans = 1;
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; }
    friend Modular inv(const Modular& a) { return mpw(a,MOD-2);}
    friend bool operator!=(const Modular& a, const Modular& b) { return !(a == b); }
    friend bool operator<(const Modular& a, const Modular& b) { return a.v < b.v; }
    Modular& operator+=(const Modular& o) { if ((v += o.v) >= MOD) v -= MOD; return *this; }
    Modular& operator-=(const Modular& o) { if ((v -= o.v) < 0) v += MOD; return *this; }
    Modular& operator*=(const Modular& o) { v = int((ll)v*o.v%MOD); return *this; }
    Modular& operator/=(const Modular& o) { return (*this) *= inv(o); }
    Modular operator-() const { return Modular(-v); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    friend Modular operator+(Modular a, const Modular& b) { return a += b; }
    friend Modular operator-(Modular a, const Modular& b) { return a -= b; }
    friend Modular operator*(Modular a, const Modular& b) { return a *= b; }
    friend Modular operator/(Modular a, const Modular& b) { return a /= b; }
    friend istream& operator>>(istream& inp, Modular& a) { ll x; inp >> x; a = Modular(x); return inp;}
    friend ostream& operator<<(ostream& out, const Modular& a) { out << a.v; return out; }
};
using Mint = Modular<MOD>;
 
using Mint = Modular<MOD>;
const int mxN = 1e6 + 10;
vector<Mint> f(mxN), invf(mxN);
 
Mint modpow(Mint x, int e) {
    Mint base = x, curr = 1;
    while (e) {
        if (e & 1) {
            curr *= base;
        }
        base = base * base;
        e >>= 1;
    }
    return curr;
}
 
void precompute_factorials() {
    f[0] = 1;
    for (int i = 1; i < mxN; i++) {
        f[i] = f[i-1] * i;
    }
    invf[mxN - 1] = modpow(f.back(), MOD - 2);
    for (int i = mxN - 2; i >= 0; i--) {
        invf[i] = invf[i+1] * (i + 1);
    }
}
 
Mint nCr(int n, int r) {
    return f[n] * invf[n-r] * invf[r];
}
 
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    precompute_factorials();
 
    int n, k; cin >> n >> k;
    if (n % k != 0) {
        cout << 0 << "\n";
        return 0;
    }
    int r = n / k;
    Mint prod = (f[n] * invf[r]) / modpow(k, r);
    for (int i = 1; i < r; i++){
        prod *= (i * k + 1);
    }
    cout << prod << "\n";
 
}

Just print YES if $$$a+b=c$$$ and NO otherwise.

The answer is the sum of $$$a_i \cdot a_{i+1}$$$ over all $$$1 \leq i \lt n$$$, which can be computed in a single for loop.

In this scenario, 'A' and 'T' are equivalent and 'C' and 'G' are equivalent. So we can replace all 'T' with 'A' and all 'G' with 'C' and check if the resulting strings are equal.

Let's loop over all pairs of animals and determine whether or not they have a predator-prey relationship and update the respective counts. This can be checked by seeing if $$$a \leq \lvert p_i - p_j \rvert \lt b$$$.

The previous version is too hard for these constraints. We need a faster way to find the number of predators and prey an animal has. Notice that for animal $$$i$$$, its predators will be in the range $$$[p_i + a, p_i + b)$$$, and its prey will be in the range $$$(p_i - b, p_i - a]$$$. If we sort the array of predator factors, we can binary search for the indexes of the endpoints of these ranges and determine the number of animals in that range. Thus, we can solve the problem in $$$O(n \log n)$$$.

We can notice that it is always better to do less costly tasks before more costly tasks if we consider both. Let's say we know the optimal solution for $$$k=i$$$. When we consider the $$$i+1$$$-th element, there are three cases:

• We can add it to our solution without running out of ATP, which would clearly be optimal if possible.
• We can use it to replace a task in our solution. In this case, we would obviously want to replace the most costly task.
• We do not add it to our solution. In this case, it would have to be worse than the most costly element in our solution, since otherwise option $$$2$$$ would be better.

So we need to be able to add an element to our solution and find/remove the element with the maximum cost. This sounds like a job for a priority queue.

First, we can show that if a wildfire of strength $$$k$$$ is sufficient, so is a wildfire of strength $$$k+1$$$ (try proving this yourself!). So for each forest, we can separately compute the minimum strength needed to burn all of the forests to the left and to the right and take the maximum of those values.

For now, let's only consider the left case; the other case is symmetric. If the minimum strength needed for forest $$$i$$$ is $$$k$$$, then the minimum strength for forest $$$i+1$$$ is $$$k-1$$$ if $$$t_i \geq k$$$ and $$$k+1$$$ otherwise. So we can compute the answer in two linear sweeps, one for the forests to the left and one for the forests to the right.

You might notice that the statement implicitly assumes that the number of linear strands is well-defined regardless of how LOPITAL cuts and splices. Understanding why this is true is the key to the solution.

Claim 1: The number of new linear strands formed from a cut is equal to the number of cuts made (i.e. consecutive occurrences of $$$x$$$ and $$$y$$$). Clearly, this is true when we cut an already linear strand. The first cut we make to a circular strand converts it to linear and increases the answer by $$$1$$$.

Claim 2: During a splice, the number of linear strands reduces by $$$min(a_{1x}, a_{2y})$$$ where the $$$a_{1i}$$$ is the number of linear strands that begin with $$$i$$$ and $$$a_{2j}$$$ is the number of linear strands that end with $$$j$$$. If the $$$x$$$-$$$y$$$ pair that we splice are the beginning and end of the same strand, then the number of linear strands decreases by $$$1$$$. In the other case, we splice two different linear strands, reducing the number of linear strands by $$$1$$$.

Since there are only $$$4$$$ possibilities, we can update the values $$$a_{ij}$$$ and the number of consecutive occurrences of two characters in $$$O(1)$$$ per query.

There are several solutions to this problem. A straightforward approach is to binary search on the smallest possible value of $$$t$$$. For a fixed value of $$$t$$$ to be possible, there needs to be a point $$$(x, y)$$$ that is within a Manhattan distance of $$$t$$$ from each of the $$$n$$$ given points. We can reformulate this by noticing that the set of points that a bacteria can expand to can be represented as a square centered at the point of origin rotated $$$45^\circ$$$ from the coordinate axes.

So to determine if a value of $$$t$$$ is possible, we just need to check if the intersection of these squares is non-empty and contains a point with integer coordinates. Implementation can get tricky. The author's solution rotates the plane by $$$45^\circ$$$ to make all squares axis-aligned. Then finding the intersection of two rectangles is much simpler. Off-by-one errors will most likely happen, so we also recommend checking all possibilities within a certain range around the solution you found.

Let $$$a_i$$$ be the number of evolutionary pathways over $$$i$$$ generations without any OP gene. We can see that this satisfies $$$a_{i+1} = \binom{2^{i+1}-1}{2^i} \cdot a_i^2$$$. The intuitive way to understand this is that the species which splits off in the first generation will have $$$2^i$$$ descendants and each way to choose these descendants is unique.

The second key observation is that the generations in which the OP gene is "activated" depend only on $$$n$$$. (Hint: think about the binary representation of $$$n$$$.) Now, we can go from the first to the most recent generations and follow the OP gene. If the species with the OP gene splits in the $$$i$$$-th generation, then the new species without the OP gene will have $$$a_{i-1}$$$ possibilities, multiplied by the appropriate binomial factor. Otherwise, the species does not evolve and there is no change. So we can compute the answer for each query in $$$O(\log n)$$$.