• Great:
• Good:
• Average:
• Bad:
• Trash:

• A:
• B:
• C1:
• C2:
• C3:
• D:
• E:
• F:

• A:
• B:
• C1:
• C2:
• C3:
• D:
• E:
• F:

A report array can be genuine only if it meets both of these conditions:

• There must be at least one player who reported $$$0$$$ — there are $$$n - 1$$$ duels and $$$n$$$ players.
• There cannot be two adjacent players who both reported $$$0$$$ — one of them must have won the duel between them.

If either condition fails, the answer is YES (there is definitely a liar); otherwise, the answer is NO.

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (accumulate(a.begin(), a.end(), 0) == n) {
        cout << "YES" << "\n";
        return;
    }

    for (int i = 0; i < n - 1; i++) if (!a[i] && !a[i + 1]) {
        cout << "YES" << "\n";
        return;
    }

    cout << "NO" << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

We restructure the game by grouping each move (Fouad's move) with the following cut (Mouf's cut). After Mouf performs his initial cut, each combined turn consists of Fouad first moving to any remaining cell, followed by Mouf cutting the grid.

Now, let's temporarily set aside the initial cut and focus on the state of the grid just before Fouad's first move in this new structure. Suppose the remaining Grid has dimensions $$$n' \times m'$$$. Since each cut affects only one dimension, we can handle the row and column reductions independently. Thus, the number of required turns is:

where $$$f(l)$$$ denotes the number of turns required to reduce a $$$1 \times l$$$ grid to a single cell. The function $$$f(l)$$$ can be defined recursively as:

Given that $$$f$$$ is non-decreasing, the minimum between $$$f(i)$$$ and $$$f(l − i + 1)$$$ is maximized when $$$i = \left\lfloor \frac{l}{2} \right\rfloor$$$. Thus, we simplify the recurrence as:

Now returning to the initial cut, note that it is in Mouf's best interest to minimize $$$n'$$$ and $$$m'$$$ since $$$f$$$ is non-decreasing. To do so, he should ensure Fouad ends up on the boundary of the remaining grid after the first cut. This yields four possible configurations:

The total number of turns, including the initial cut, is:

The overall time complexity is: $$$O(\log(n) + \log(m))$$$.

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;

    vector<pair<int, int>> rec({
    make_pair(a, m), make_pair(n - a + 1, m),
    make_pair(n, b), make_pair(n, m - b + 1)});

    int ans = n + m;
    for (auto [n1, m1] : rec) {
        int res = 0;
        while (n1 > 1) {
            ++res;
            n1 = (n1 + 1) / 2;
        }
        while (m1 > 1) {
            ++res;
            m1 = (m1 + 1) / 2;
        }
        ans = min(ans, res);
    }

    cout << 1 + ans << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

• Apply $$$\texttt{"digit"}$$$ $$$\rightarrow$$$ $$$x \in [1, 81]$$$.
• Apply $$$\texttt{"digit"}$$$ $$$\rightarrow$$$ $$$x \in [1, 16]$$$.
• Apply $$$\texttt{"add -8"}$$$ $$$\rightarrow$$$ $$$x \in [1, 8]$$$.
• Apply $$$\texttt{"add -4"}$$$ $$$\rightarrow$$$ $$$x \in [1, 4]$$$.
• Apply $$$\texttt{"add -2"}$$$ $$$\rightarrow$$$ $$$x \in [1, 2]$$$.
• Apply $$$\texttt{"add -1"}$$$ $$$\rightarrow$$$ $$$x$$$ becomes exactly $$$1$$$.
• Finally, apply $$$\texttt{"add n-1"}$$$.

#include<bits/stdc++.h>

using namespace std;

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

    cout << "digit" << endl;
    int x;
    cin >> x;

    cout << "digit" << endl;
    cin >> x;

    for (int i = 8; i >= 1; i /= 2) {
        cout << "add " << -i << endl;
        cin >> x;
    }

    cout << "add " << n - 1 << endl;
    cin >> x;

    cout << "!" << endl;
    cin >> x;
    assert(x == 1);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

• Apply $$$\texttt{"mul 9"}$$$.
• Apply $$$\texttt{"digit"}$$$ $$$\rightarrow$$$ $$$x \in [9, 18, 27, 36, 45, 54, 63, 72, 81]$$$.
• Apply $$$\texttt{"digit"}$$$ $$$\rightarrow$$$ $$$x$$$ becomes exactly $$$9$$$.
• Finally, apply $$$\texttt{"add n-9"}$$$.

#include<bits/stdc++.h>

using namespace std;

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

    cout << "mul " << 9 << endl;
    int x;
    cin >> x;

    cout << "digit" << endl;
    cin >> x;

    cout << "digit" << endl;
    cin >> x;

    cout << "add " << n - 9 << endl;
    cin >> x;

    cout << "!" << endl;
    cin >> x;
    assert(x == 1);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Let's prove that

Observe that

The first term represents $$$(x - 1)$$$ shifted $$$d$$$ places to the left (i.e. multiplies by $$$10^d$$$). The second term is the $$$d$$$-digit string of nines minus $$$(x - 1)$$$, namely

Therefore, for every $$$i$$$ ($$$1 \le i \le d$$$), the $$$i$$$-th digit of the second term and the $$$(i + d)$$$-th digit of the first term complement each other to sum to $$$9$$$.

Drumroll, please! The number we're about to use is $$$999\,999\,999$$$. With just three commands, we can turn any $$$x$$$ into $$$n$$$:

• Apply $$$\texttt{"mul } 999\,999\,999 \texttt{"}$$$.
• Apply $$$\texttt{"digit"}$$$ $$$\rightarrow$$$ $$$x$$$ becomes exactly $$$81$$$.
• Finally, apply $$$\texttt{"add n-81"}$$$.

There's one special case: if $$$n = 81$$$, you only need the first two commands — meaning $$$f(81) = 2$$$.

Now let’s see why no other $$$n$$$ can get away with just two commands. First, note that the digit‑sum function $$$S(i)$$$ always changes when you add $$$1$$$, so $$$S(i) \neq S(i + 1)$$$.

Consider your choice of first command:

• $$$\texttt{"add y"}$$$: When $$$y$$$ is positive, it shifts the entire range of possible $$$x$$$-values. Otherwise, it shrinks the range but never cuts it down below half its size. In either case, it can’t force $$$x$$$ into a single value.
• $$$\texttt{"div y"}$$$: It fails even on small $$$x$$$-values (e.g. $$$1 \le x \le 4$$$) — it doesn’t force a single outcome.
• $$$\texttt{"digit"}$$$: After the first application, it only restricts $$$x$$$ to $$$[1, 81]$$$, and a second application only narrows it to $$$[1, 16]$$$. You still don’t get a single fixed value.

That leaves only one candidate to start with, which is $$$\texttt{"mul y"}$$$. Suppose some other multiplier $$$y \neq 999\,999\,999$$$ made $$$S(x \cdot y)$$$ constant. Test it against $$$x = 1$$$ and $$$x = 999\,999\,999$$$:

They can’t both be the same, so no such $$$y \neq 999\,999\,999$$$ exists.

Similar to the above reasoning, keeping in mind that $$$S(i) \neq S(i + 1)$$$, the only possible second command is $$$\texttt{"digit"}$$$ (as this is the only way to shrink the range, since no other command can do so). Hence, only $$$n = 81$$$ can reach a fixed result in two commands; every other $$$n$$$ requires three.

#include<bits/stdc++.h>

using namespace std;

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

    cout << "mul 999999999" << endl;
    int x;
    cin >> x;

    cout << "digit" << endl;
    cin >> x;

    if (n != 81) {
        cout << "add " << n - 81 << endl;
        cin >> x;
    }

    cout << "!" << endl;
    cin >> x;
    assert(x == 1);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

We hid the command limits in C3 so people wouldn’t just guess wildly. We used C1 to bridge the gap between B and C2. This problem was originally a D, but testers found what was then D1 (now C1) way easier than C (which got moved to D). The neat trick for C3 happened by chance — Kaitokid used $$$\texttt{"mul 99"}$$$ instead of the intended $$$\texttt{"mul 9"}$$$ in C2, and that's where MOUFLESS's guessing skills kicked in and saw it could be extended to $$$999\,999\,999$$$! After we worked through a formal proof, we decided it was too good not to include in the final problem set.

Let us temporarily set aside the multiset $$$A$$$. Starting from vertex $$$1$$$, define

Since any walk of length $$$d$$$ can be extended to $$$d + 2$$$ by inserting a back-and-forth move $$$[i \to j \to i]$$$ at any vertex $$$j$$$ adjacent to $$$i$$$, only the minimal even and odd distances matter. By performing a breadth-first search from vertex $$$1$$$, we derive $$$\mathrm{dist}$$$.

Now reintroduce the multiset $$$A$$$ with total sum $$$S = \sum A$$$. We would like to select a sub-multiset whose sum $$$S'$$$ satisfies both

• $$$S' \ge \mathrm{dist}[i][p];$$$
• $$$S' \bmod 2 = p.$$$

Taking all elements gives $$$S' = S$$$. Let $$$p = S \bmod 2$$$, then any vertex with $$$\mathrm{dist}[i][p] \le S$$$ is reachable by a walk of parity $$$p$$$. Otherwise, we must find a suitable $$$S' \bmod 2 = 1 - p$$$ satisfying $$$\mathrm{dist}[i][1 - p] \le S'$$$, and the minimal way to flip parity is to remove the smallest odd element $$$\min_{\mathrm{odd}}$$$ from the multiset $$$A$$$. Parity change is impossible if no such odd element exists, since removing any even element leaves the parity unchanged. Setting $$$S' = S - a_{\mathrm{odd}}$$$, any vertex with $$$\mathrm{dist}[i][1 - p] \le S'$$$ is reachable by a walk of parity $$$1 - p$$$.

In conclusion, vertex $$$i$$$ is attainable by a walk using the original multiset $$$A$$$ if and only if either

• $$$\mathrm{dist}[i][p] \le S \text{ when } p = S \bmod 2 \text{, or}$$$
• $$$\mathrm{dist}[i][p] \le S - \min_{\mathrm{odd}} \text{ when } p \neq S \bmod 2 \text{ and the smallest odd element } \min_{\mathrm{odd}} \in A \text{ exists.} $$$

The overall time complexity is: $$$O(n + m + \ell)$$$.

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, l;
    cin >> n >> m >> l;

    int const inf = 2e9 + 1;
    int sum = 0, min_odd = inf;
    vector<int> a(l);
    for (int i = 0; i < l; ++i) {
        cin >> a[i];
        sum += a[i];
        if (a[i] % 2) {
            min_odd = min(min_odd, a[i]);
        }
    }

    vector adj(n, vector<int>());
    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);
    }

    vector<array<int, 2>> dist(n, {inf, inf});
    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 0;
    while (q.size()) {
        auto [u, p] = q.front();
        q.pop();
        for (auto v : adj[u]) {
            if (dist[v][!p] > dist[u][p] + 1) {
                dist[v][!p] = dist[u][p] + 1;
                q.push({v, !p});
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        bool found = 0;
        for (int p = 0; p < 2; ++p) {
            int s = sum - (p == sum % 2 ? 0 : min_odd);
            if (dist[i][p] <= s) {
                found = 1;
            }
        }
        cout << found;
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Some useful insight is to see that if you operate on an element, then every element after it will be unaffected; similarly, the state of an element in the string depends only on the number of operations used on the suffix after it. More specifically, an element's state flips with each operation applied to a suffix that includes it, so its value depends entirely on the number of operations done to its suffix.

This inspires the following $$$dp$$$ state:

Now, regarding transitions — the number of ways to move from state $$$dp[i][j]$$$ to $$$dp[i - 1][j + k]$$$ (in other words the number of ways to add $$$k$$$ operations at the $$$(i - 1)$$$-th index) can be thought of in terms of forming strings composed of characters $$$A$$$ and $$$B$$$, where $$$A$$$ represents making a move on $$$s_{i - 1}$$$ and $$$B$$$ represents making a move on $$$s_i,...,s_n$$$. Each valid string with $$$j$$$ $$$B$$$s and $$$k$$$ $$$A$$$s represents a unique sequence of moves, so the total number of transitions corresponds to the number of such valid strings. Notice that a string will be valid if and only if every $$$A$$$ occurs when $$$s_{i - 1}$$$ is $$$0$$$, because $$$s_{i - 1}$$$ flips every operation, meaning that every $$$A$$$ should occur on either only even indices or only odd indices depending on the initial value of $$$s_{i - 1}$$$.

This means that the transition will be either $$$\displaystyle\binom{\left\lfloor \frac{j + k}{2} \right\rfloor}{k}$$$ or $$$\displaystyle\binom{\left\lceil \frac{j + k}{2} \right\rceil}{k}$$$.

Finally, the answer can be found in $$$dp[1][k]$$$.

The overall time complexity is: $$$O(n \cdot k^2)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://mirror.codeforces.com/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

struct Combi{
    vector<mint> _fac, _ifac;
    int n;
    
    Combi() {
        n = 1;
        _fac.assign(n + 1, 1);
        _ifac.assign(n + 1, 1);
    }
    
    void check_size(int m){
        int need = n;
        while (need < m) need *= 2;
        m = need;
        if (m <= n) return;
        
        _fac.resize(m + 1);
        _ifac.resize(m + 1);
        for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1];
        
        _ifac[m] = _fac[m].inv();
        for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
        n = m;
    }
    
    mint fac(int m){
        check_size(m);
        return _fac[m];
    }
    
    mint ifac(int m){
        check_size(m);
        return _ifac[m];
    }
    
    mint ncr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r) * ifac(r);
    }
    
    mint npr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r);
    }
} comb;

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

    string s;
    cin >> s;

    vector<vector<mint>> dp(n, vector<mint>(k + 1));
    dp[n - 1][0] = 1;
    if (s[n - 1] == '0')
        dp[n - 1][1] = 1;

    for (int i = n - 2; i >= 0; i--){
        for (int j = 0; j <= k; j++){
            for (int c = 0; j + c <= k; c++){
                int spaces = (j + c + (s[i] == '0')) / 2;
                dp[i][j + c] += dp[i + 1][j] * comb.ncr(spaces, c);
            }
        }
    }

    cout << dp[0][k] << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

First, find $$$\mathrm{dis}_M$$$ using Dijkstra's algorithm or DSU.

Define $$$can(x)$$$ to be true if you can make $$$\mathrm{dis}_F$$$ greater than or equal to $$$x$$$, and false otherwise. It's clear that if $$$can(x)$$$ is true, then $$$can(x−1)$$$ is also true, which leads us to perform a binary search on the value of $$$x$$$.

Suppose we choose a set $$$S$$$ of black cells with values strictly less than $$$x$$$ and decide to apply operations on them; the optimal strategy is to make the values of all chosen cells equal to $$$x$$$.

Now, suppose we don't care about $$$\mathrm{dis}_M$$$. How can we find the maximum possible $$$\mathrm{dis}_F$$$?

We need to create a cage that separates Fouad from the exit. The cage consists of the borders of the grid, in addition to cells with values greater than or equal to $$$x$$$ (after applying operations), forming a connected chain such that every two consecutive cells in the chain share an edge or corner.

By using multi-source Dijkstra's algorithm, start from one border and try to reach another, where the weight of each cell represents how many operations are needed to raise its value to at least $$$x$$$. If it cannot be reached (e.g., if the cell is white and its value is less than $$$x$$$), then set the weight to infinity.

We have six cases to build the cage, as described in the picture below:

Now we have two cases to consider:

• $$$x \le \mathrm{dis}_M$$$: In this scenario, $$$\mathrm{dis}_M$$$ will remain unchanged regardless of the set $$$S$$$ we choose.

• $$$x \gt \mathrm{dis}_M$$$: Here, we must ensure that at least one path for Mouf has a cost equal to $$$\mathrm{dis}_M$$$, while ensuring that no cell in this path is included in $$$S$$$.

But which path should we retain?

Suppose Mouf takes a path $$$P$$$. This action divides the grid into two parts:

• Every cell reachable from $$$(n,1)$$$ without passing through any cell in $$$P$$$. This portion belongs to Fouad (if $$$(n, 1)$$$ is already in $$$P$$$, then there are no cells that belong to Fouad's part).

• The remaining cells belong to Mouf.

As we observe, the more cells allocated to Fouad's part, the greater the options we have for constructing a cage. Therefore, we define a super path as a path that leaves the maximum number of cells available for Fouad's part. But how many super paths exist?

In fact, there is only one super path; the proof can be found below.

Proof

Suppose we have two super paths that intersect at certain cells (including the first and last cells). In this case, we have two scenarios to consider:

• They only intersect at the first and last cells. In this situation, one of the paths cannot be a super path, leading to a contradiction.

• They intersect at other cells: If this is the case, then neither of the paths can be considered a super path. We can take the optimal segments from each path to construct a superior path, which also leads to a contradiction.

For further clarification, please refer to the illustration below.

Now, how do we identify that super path?

We begin by performing a multi-source BFS, initializing the queue with the cells in the first row and the first $$$r$$$ cells of the last column (as they always belong to Mouf's part). When visiting a cell, we mark it. If its value is less than or equal to $$$\mathrm{dis}_M$$$, we pop it from the queue and continue; otherwise, we spread to the eight neighboring cells.

Through this process, we will have certainly marked the super path (and potentially some additional cells from Mouf's part). If $$$x \gt \mathrm{dis}_M$$$, it becomes impossible to utilize any marked cell to construct the cage — therefore, we set the weight for these cells to infinity. While you might consider the marked cells that are not part of the super path, this is inconsequential since any cage utilizing these cells will invariably pass through the super path.

The overall time complexity of this approach is: $$$O(n^2 \cdot \log(A_{MAX} + k) \cdot \log(n))$$$.

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int inf = 1e9;
array<int, 8> dx{0, 0, 1, -1, 1, 1, -1, -1};
array<int, 8> dy{1, -1, 0, 0, -1, 1, -1, 1};

void solve() {
    int n, r, k;
    cin >> n >> r >> k;
    --r;
    
    vector a(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    
    vector b(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < n; ++j) {
            b[i][j] = s[j] - '0';
        }
    }
    
    auto in = [&](int i, int j) {
        return (0 <= i && i < n && 0 <= j && j < n);
    };
    
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    pq.push({a[0][0], 0, 0});
    vector dis(n, vector<int>(n, inf));
    dis[0][0] = a[0][0];
    while (pq.size()) {
        auto [mx, i, j] = pq.top();
        pq.pop();
        if (dis[i][j] != mx) {
            continue;
        }
        for (int dir = 0; dir < 4; ++dir) {
            int ni = i + dx[dir];
            int nj = j + dy[dir];
            if (in(ni, nj) && dis[ni][nj] > max(mx, a[ni][nj])) {
                int nmx = max(mx, a[ni][nj]);
                dis[ni][nj] = nmx;
                pq.push({nmx, ni, nj});
            }
        }
    }
    int mouf = dis[r][n - 1];
    
    vector dont(n, vector<int>(n));
    auto run = [&](auto &&run, int i, int j) -> void {
        for (int dir = 0; dir < 8; ++dir) {
            int ni = i + dx[dir];
            int nj = j + dy[dir];
            if (in(ni, nj) && dont[ni][nj] == 0) {
                dont[ni][nj] = 1;
                if (a[ni][nj] > mouf) {
                    run(run, ni, nj);
                }
            }
        }
    };
    
    for (int j = 0; j < n; ++j) {
        dont[0][j] = 1;
        if (a[0][j] > mouf) {
            run(run, 0, j);
        }
    }
    for (int i = 0; i <= r; ++i) {
        dont[i][n - 1] = 1;
        if (a[i][n - 1] > mouf) {
            run(run, i, n - 1);
        }
    }
    
    int L = 1, R = 2e6;
    while (L <= R) {
        int mid = (L + R) / 2;
        for (int j = 0; j < n; ++j) {
            if ((mid > mouf && dont[n - 1][j]) || (mid > a[n - 1][j] && b[n - 1][j] == 0)) {
                continue;
            }
            pq.push({max(0, mid - a[n - 1][j]), n - 1, j});
        }
        for (int i = r; i < n; ++i) {
            if ((mid > mouf && dont[i][n - 1]) || (mid > a[i][n - 1] && b[i][n - 1] == 0)) {
                continue;
            }
            pq.push({max(0, mid - a[i][n - 1]), i, n - 1});
        }
        fill(dis.begin(), dis.end(), vector<int>(n, inf));
        while (pq.size()) {
            auto [cost, i, j] = pq.top();
            pq.pop();
            dis[i][j] = min(dis[i][j], cost);
            if (dis[i][j] != cost) {
                continue;
            }
            for (int dir = 0; dir < 8; ++dir) {
                int ni = i + dx[dir];
                int nj = j + dy[dir];
                if (in(ni, nj)) {
                    if ((mid > mouf && dont[ni][nj]) || (mid > a[ni][nj] && b[ni][nj] == 0)) {
                        continue;
                    }
                    if (dis[ni][nj] > cost + max(0, mid - a[ni][nj])) {
                        int ncost = cost + max(0, mid - a[ni][nj]);
                        dis[ni][nj] = ncost;
                        pq.push({ncost, ni, nj});
                    }
                }
            }
        }
        int minCost = inf;
        if (mid <= mouf) {
            for (int j = 0; j < n; ++j) {
                minCost = min(minCost, dis[0][j]);
            }
            for (int i = 0; i <= r; ++i) {
                minCost = min(minCost, dis[i][n - 1]);
            }
        }
        for (int i = 1; i < n; ++i) {
            minCost = min(minCost, dis[i][0]);
        }
        if (minCost <= k) {
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
            
    cout << mouf << " " << R << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

When MOUFLESS came up with F, the intended solution was based on flows — then, thanks to the efforts of ApraCadabra, Kaitokid, and Wael_Zaiback, they helped us refine the problem until we got here.