B turned out to be harder than expected. I apologize for this, but I hope there are still problems that are fun and educational for you to solve in this round.

Regardless, I hope this round encourages authors to include communication problems in their future rounds, and in earlier positions as well.

Suppose it Kalamaki's turn on some even round $$$2k$$$. Kalamaki can swap element $$$a_{2k}$$$ with $$$a_{2k+1}$$$. If $$$a_{2k} \gt a_{2k+1}$$$, he will not swap the elements, but if $$$a_{2k} \lt a_{2k+1}$$$, he will swap them. In both cases he wins the game, because the array will never be sorted. Therefore, if $$$a_{2k} \neq a_{2k+1}$$$, Kalamaki will win no matter what.

Now assume every time Kalamaki plays, the two elements he can swap have the same value, because otherwise we have shown that he wins. Suppose that it is Souvlaki's turn on round $$$2k+1$$$. We know that $$$a_{2k} = a_{2k+1}$$$ from the previous assumption. If $$$a_{2k+1} \gt a_{2k+2}$$$, we know that $$$a_{2k+1} = a_{2k} \gt a_{2k+2}$$$, but he is unable to swap $$$a_{2k}$$$ and $$$a_{2k+2}$$$, therefore he loses. Otherwise, if $$$a_{2k+1} \le a_{2k+2}$$$ he will not do anything, and he proceeds to the next round.

From these observations, we see that $$$a$$$ is winnable by Souvlaki if and only if: $$$a_1 \le a_2 = a_3 \le a_4 = a_5 \le \ldots$$$, or $$$a_2 \le a_1 = a_3 \le a_4 = a_5 \le \ldots$$$. It is obvious now that Souvlaki, before the start of the game, will sort $$$a$$$ in non-decreasing order. To determine if Souvlaki wins or not it is enough to check the above condition is satisfied after sorting.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n; cin >> n;
    int a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    for (int i = 2; i <= n - 1; i+=2) {
        if (a[i] != a[i+1]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

Let the position of integer $$$x$$$ in the permutation $$$p$$$ be denoted by $$$pos_x$$$.

Let's see for which indices $$$i$$$ we can never set $$$s_i$$$ to $$$1$$$, even with an infinite number of operations. First of all, in an operation $$$(l, r)$$$, we only consider indices $$$i$$$ such that $$$l \lt i \lt r$$$. This means that we can never set $$$s_1$$$ or $$$s_n$$$ to $$$1$$$. In addition, we only consider indices $$$i$$$ such that $$$p_i$$$ is between $$$p_l$$$ and $$$p_r$$$, but not equal to those. This means that we can never set $$$s_{pos_1}$$$ or $$$s_{pos_n}$$$ to $$$1$$$. In general, if $$$x_1 = 1$$$, $$$x_n = 1$$$, $$$x_{pos_1} = 1$$$, or $$$x_{pos_n} = 1$$$, it is impossible to solve the problem.

Now I will show that the problem is always solvable for any binary string $$$x$$$ such that $$$x_1 = x_n = x_{pos_1} = x_{pos_n} = 0$$$, within $$$5$$$ operations.

WLOG, assume $$$pos_1 \lt pos_n$$$. It is natural to think about using $$$pos_1$$$ and $$$pos_n$$$ as endpoints for our operations. For example, by using the operations $$$(1, pos_1)$$$ and $$$(1, pos_n)$$$, we will have set $$$s_i = 1$$$ for every $$$1 \lt i \lt pos_1$$$. Likewise, with the operations $$$(pos_1, n)$$$ and $$$(pos_n, n)$$$, we will have set $$$s_i = 1$$$ for every $$$pos_n \lt i \lt n$$$. By using the operation $$$(pos_1, pos_n)$$$, we have set $$$s_i = 1$$$ for every $$$pos_1 \lt i \lt pos_n$$$.

With these $$$5$$$ operations, we have finally set $$$s_i = 1$$$ for every $$$i$$$ in $$$(1, pos_1) \cup (pos_1, pos_n) \cup (pos_n, n)$$$, which guarantees we have solved the problem.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n; cin >> n;
    vector<int> a(n+1);
    int mn = 1, mx = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < a[mn]) mn = i;
        if (a[i] > a[mx]) mx = i;
    }
    string t; cin >> t;
    t = " " + t;
    if (t[1] == '1' || t[n] == '1') {
        cout << -1 << "\n";
        return;
    }
    if (t[mn] == '1' || t[mx] == '1') {
        cout << -1 << "\n";
        return;
    }
    cout << 5 << "\n";
    cout << 1 << " " << mn << "\n";
    cout << 1 << " " << mx << "\n";
    cout << mn << " " << n << "\n";
    cout << mx << " " << n << "\n";
    cout << min(mn, mx) << " " << max(mn, mx) << "\n";
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

We call a pair of integers $$$(l, r)$$$ good if and only if $$$1 \le l \le r \le 2n$$$ and in $$$f(l, r)$$$ there is a down-right path from $$$(1, 1)$$$ to $$$(2, n)$$$ of cells with value of $$$1$$$. For some fixed left endpoint $$$l$$$ from $$$1$$$ to $$$2n$$$, let $$$r_l$$$ denote the minimum integer such that the pair $$$(l, r_l)$$$ is good. If there does not exist such an integer, for convenience we say $$$r_l = n+1$$$.

The first observation is that if $$$(l, r)$$$ is good, and $$$r \lt 2n$$$, then $$$(l, r+1)$$$ is also good. The reason is obvious: every cell that has value of $$$1$$$ in $$$f(l, r)$$$ has value of $$$1$$$ in $$$f(l, r+1)$$$. Therefore, if we find $$$r_1, r_2, \ldots, r_{2n}$$$, the answer will be $$$(2n - r_1 + 1) + (2n - r_2 + 1) + \ldots + (2n - r_{2n} + 1)$$$. (In other words, we are counting all pairs $$$(l, r_l), (l, r_l+1), \ldots, (l, 2n)$$$, for all $$$1 \le l \le 2n$$$).

The second observation follows: $$$r_1 \le r_2 \le \ldots \le r_{2n}$$$. It is clear that the only difference between grids $$$f(l, r_l)$$$ and $$$f(l+1, r_l)$$$ is that $$$f(l+1, r_l)$$$ has the same or a greater amount of cells with value of $$$0$$$, and if some cell has value of $$$1$$$ in $$$f(l+1, r_l)$$$, it has value of $$$1$$$ in $$$f(l, r_l)$$$. If we do not have a down-right path anymore in $$$f(l+1, r_l)$$$, there is no down right path in any $$$f(l+1, r)$$$ with $$$r \le r_l$$$. It follows that $$$r_{l+1} \ge r_l$$$.

This observation allows us to use two pointers. For some fixed $$$l$$$ and $$$r$$$, if $$$(l, r)$$$ is not good, we will keep increasing $$$r$$$ until it is good, or in other words find $$$r_l$$$. We activate all cells with value of $$$r+1$$$. To check if the pair $$$(l, r+1)$$$ is good, we get the first de-activated cell in the first row and the last de-activated cell in the last row (a cell is de-activated if it does not belong in the range we are currently considering). This can be done by keeping two sets of de-activated cells, one for each row. Suppose that those are at columns $$$a$$$ and $$$b$$$ respectively. There exists a down-right path in $$$f(l, r+1)$$$ if and only if $$$a - 1 \gt b$$$ (we can reach cell $$$(1, a-1)$$$, then go to cell $$$(2, a-1)$$$ and the proceed to $$$(2, n)$$$). Once we find $$$r_l$$$, we will increase $$$l$$$, de-activate every cell with value of $$$l$$$, and keep increasing $$$r_l$$$ until we find $$$r_{l+1}$$$, and so on.

// nifeshe

#ifdef LOCAL
    #include <bits/include_all.h>
#else
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
#endif

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const ll mod = 998244353;
const ll inf = 1e18;
const int MAX = 2e5 + 42;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n));
    for(auto &i : a) {
        for(auto &j : i) {
            cin >> j;
        }
    }

    vector<vector<pii>> pos(2 * n + 1);
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < n; j++) {
            pos[a[i][j]].push_back({i, j});
        }
    }


    array<set<int>, 2> st;
    st[0].insert(inf);
    st[1].insert(-inf);
    for(int i = 0; i < n; i++) st[0].insert(i);
    for(int i = 0; i < n; i++) st[1].insert(i);

    auto add = [&](int x) {
        for(auto [i, j] : pos[x]) {
            st[i].erase(j);
        }
    };

    auto del = [&](int x) {
        for(auto [i, j] : pos[x]) {
            st[i].insert(j);
        }
    };

    auto check = [&]() {
        if(st[0].count(0)) return false;
        if(st[1].count(n - 1)) return false;
        if(*st[0].begin() - 1 <= *st[1].rbegin()) return false;

        return true;
    };

    int ans = 0;
    int r = 0;
    for(int l = 1; l <= 2 * n; l++) {
        while(r + 1 <= 2 * n && !check()) {
            add(++r);
        }
        if(!check()) break;

        ans += 2 * n - r + 1;
        del(l);
    }

    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

First, observe that if a range is completely inside another, it is useless. Specifically, assume we have two ranges $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$. If $$$1 \le l_2 \le l_1 \le r_1 \le r_2 \le n$$$, then we know that $$$\operatorname{MEX}(p[l_1 \ldots r_1]) \le \operatorname{MEX}(p[l_2 \ldots r_2])$$$. So we must only consider the range $$$[l_2, r_2]$$$.

After cleaning out those ranges, we are left with at most $$$n$$$ ranges. This is obvious because for every possible left endpoint, we have at most one possible right endpoint (the maximum one among all given ranges).

Now, suppose we also knew the position of $$$0$$$. Let it be $$$p_0$$$. We know that if some range does not include $$$p_0$$$, it is also useless. I claim that removing these ranges leaves at most $$$\lceil \frac{n}{2} \rceil$$$ possible ranges we must consider. Specifically, if $$$p_0 \le \frac{n}{2}$$$, we only consider ranges with left endpoint before than $$$p_0$$$. Otherwise, if $$$p_0 \ge \frac{n}{2}$$$, we only consider ranges with right endpoint after $$$p_0$$$. In both cases, it is obvious we consider at most $$$\lceil \frac{n}{2} \rceil$$$ ranges.

Finally, notice that we do not care about the exact value of $$$p_0$$$, but only if it is in the first half or the second half. Therefore, we will do a query of the form $$$[1, \frac{n}{2}]$$$, determine which half $$$p_0$$$ is in, clean out useless ranges and query the rest. This results to at most $$$\lceil \frac{n}{2} \rceil + 1$$$ queries, and the problem is solved.

#include <bits/stdc++.h>
using namespace std;
 
int LIM, Q;
 
int ask(int l, int r) {
    Q++;
    assert(Q <= LIM);
    cout << "? " << l << " " << r << endl;
    int ans; cin >> ans;
    return ans;
}
 
bool inside(int l, int r, bool toL, int n) {
    int midL = n / 2;
    if (toL) {
        return l <= midL;
    }
    else return r > midL;
}
 
void solve() {
    int n, q; cin >> n >> q;
    Q = 0;
    LIM = max(30, n / 2 + n % 2 + 5);
    vector<int> maxR(n+1, 0);
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        maxR[l] = max(maxR[l], r);
    }
    bool toL = (ask(1, n/2) > 0);
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        if (maxR[i] > mx && inside(i, maxR[i], toL, n)) {
            ans = max(ans, ask(i, maxR[i]));
        }
        mx = max(mx, maxR[i]);
    }
    cout << "! " << ans << endl;
}
 
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

Please read the first two paragraphs of the solution to the Easy Version first. Suppose we have cleaned out the ranges that are completely inside other ranges.

A useful property to consider, is that for a range $$$[l, r]$$$ it holds that $$$\operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$$$. To prove this, consider the first non-negative integer $$$k$$$ such that it does not appear in $$$p[l...r]$$$. In other words, $$$\operatorname{MEX}(p[l...r]) = k$$$. If $$$k$$$ appears to the left of the range, we have $$$\operatorname{MEX}(p[1...r]) \gt k$$$ and $$$\operatorname{MEX}(p[l...n]) = k$$$. Otherwise, we have $$$\operatorname{MEX}(p[1...r]) = k$$$ and $$$\operatorname{MEX}(p[l...n]) \gt k$$$. In both cases, it holds $$$k = \operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$$$.

Consider a set of ranges $$$S$$$, such that no range is completely inside another. Picking a range $$$[l, r]$$$ of this set splits $$$S$$$ to two subsets: one set $$$L$$$ includes all ranges $$$[l_1, r_1]$$$ such that $$$l_1 \lt l$$$, and the other set $$$R$$$ includes all ranges $$$[l_2, r_2]$$$ such that $$$l \lt l_2$$$. If we could find the best subset to keep searching in depending on $$$[l, r]$$$, we could perform binary search and find the answer quickly.

So we now have the subproblem: given a range $$$[l, r]$$$, figure out if the oprimal subset to search is $$$L$$$ or $$$R$$$. We will use the following properties:

• $$$\operatorname{MEX}(p[1...i]) \le \operatorname{MEX}(p[1...i+1])$$$.
• $$$\operatorname{MEX}(p[i+1...n]) \le \operatorname{MEX}(p[i...n])$$$.
• $$$\operatorname{MEX}(p[l...r]) = \min(\operatorname{MEX}(p[1...r]), \operatorname{MEX}(p[l...n]))$$$

Suppose $$$a = \operatorname{MEX}(p[1...r])$$$ and $$$b = \operatorname{MEX}(p[l...n])$$$. If $$$a \lt b$$$, we have no reason to go to $$$L$$$. This is because the prefix $$$\operatorname{MEX}$$$ will keep decreasing, but the suffix $$$\operatorname{MEX}$$$ will keep increasing, so we will always pick the prefix which is definitely not as great as the current $$$a$$$. Therefore, we will move to $$$R$$$. Likewise, if $$$a \gt b$$$, we will move to $$$L$$$. Note that the case $$$a = b$$$ is only possible if $$$[l..r] = [1...n]$$$, in which case the answer is $$$n$$$.

Therefore, for each range we consider we make $$$2$$$ queries, and we do this with binary search at most $$$\log{n}$$$ times. We have solved the problem in $$$2\log{n}$$$ queries.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int ask(int l, int r) {
    cout << "? " << l << " " << r << endl;
    int ans; cin >> ans;
    return ans;
}
 
void solve() {
    int n, q; cin >> n >> q;
    vector<int> maxR(n+1, -1);
    for (int i = 1; i <= q; i++) {
        int u, v; cin >> u >> v;
        maxR[u] = max(maxR[u], v);
    }
    vector<pair<int, int>> ranges;
    int mr = 0;
    for (int i = 1; i <= n; i++) {
        if (maxR[i] > mr) {
            mr = maxR[i];
            ranges.push_back({i, maxR[i]});
        }
    }
    q = ranges.size();
    int lo = 0, hi = q-1;
    int ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        int l = ranges[mid].first;
        int r = ranges[mid].second;
        int pref = ask(1, r);
        int suff = ask(l, n);
        ans = max(ans, min(pref, suff));
        if (pref > suff) {
            hi = mid-1;
        }
        else lo = mid+1;
    }
    cout << "! " << ans << endl;
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy

First, we consider an easier version of the problem: what if every cell of the first column had the same value?

Suppose that every cell of the first column has value of $$$1$$$. We have the following information:

• No matter which row Player A sends, the first cell of that row has value of $$$1$$$.
• Player A has the choice of sending a column full of $1$s.
• If $$$C = 0$$$, there exists a cell with value of $$$0$$$. ($$$C = 0$$$ and every cell having value of $$$1$$$ is a contradiction).

This information leads us to the following strategy. If $$$C = 1$$$, Player A may send any row and the first column. Otherwise, if $$$C = 0$$$, he can send any row and find a column that has a $$$0$$$ in it. Then, Player B can simply compare the first cell of the row with every cell of the column; if they all match, the answer is $$$1$$$, and otherwise it is $$$0$$$.

If every cell of the first column is $$$0$$$, the solution is the same. Note there must exist at least one $$$1$$$ in the grid, as mentioned in the statement (connectivity would not be well defined otherwise). So if $$$C = 0$$$ Player A sends any row and the first column, and otherwise if $$$C = 1$$$ he sends any row and finds a column which includes a $$$1$$$. Again, Player B will compare the value of the first cell of the row with the value every cell of the column, and if they match he answers $$$0$$$ and $$$1$$$ otherwise.

Now we can generalize this solution the case where there exists both a $$$0$$$ and a $$$1$$$ in the first column. Player B always compares the first cell of the row he received: if there exists a cell with different value in the column he determines the answer is the opposite of the value of the first cell of the row. We know the following:

• Player A can send a column with both a $$$0$$$ and a $$$1$$$ (The first column).
• Player A can choose a row, such that its first cell has value $$$0$$$.
• Player A can choose a row, such that its first cell has value $$$1$$$.

Therefore, Player A can always choose the first column and the appropriate row according to $$$C$$$ such that the previous strategy still works for Player B.

#include <bits/stdc++.h>
using namespace std;
 
int ask(vector<vector<bool>> &grid, vector<pair<int, int>> arr, int op) {
    int ans = 0;
    if(op==0) ans=1;
    for (auto [a, b]: arr) {
        if(op) ans=ans||grid[a][b];
        else ans=ans&&grid[a][b];
    }
    return ans;
}
 
void ans(bool x) {
    cout << x << endl;
}
 
int find_row(vector<vector<bool>> &grid, int need, int n) {
    int lo = 1, hi = n;
    int fin = 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        vector<pair<int, int>> qr;
        for (int i = 1; i <= mid; i++) qr.push_back({i, 1});
        if (need == ask(grid, qr, need)) {
            fin = mid;
            hi = mid-1;
        } 
        else lo = mid+1;
    }
    return fin;
}
 
int find_col(vector<vector<bool>> &grid, int need, int n) {
    int lo = 1, hi = n;
    int fin = 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        vector<pair<int, int>> qr;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= mid; j++) {
                qr.push_back({i, j});
            }
        }
        if (need == ask(grid, qr, need)) {
            fin = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    return fin;
}
 
void send_grid() {
    int n; cin >> n;
    bool ans; cin >> ans;
    vector<vector<bool>> grid(n+1, vector<bool>(n+1));
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++) if(s[j]=='1') grid[i+1][j+1]=1;
    }
    vector<pair<int, int>> qr;
    for (int i = 1; i <= n; i++) {
        qr.push_back({i, 1});
    }
    int o = ask(grid, qr, 1), a = ask(grid, qr, 0);
    int col, row;
    if (o == 1 && a == 0) {
        col = 1;
        row = find_row(grid, !ans, n);
    }
    else if (o == 0) {
        row = 1;
        if (ans == 0) col = 1;
        else col = find_col(grid, 1, n);
    }
    else {
        row = 1;
        if (ans == 1) col = 1;
        else col = find_col(grid, 0, n);
    }
    cout << row << " " << col << endl; 
}
 
void receive_grid() {
    int n; cin >> n;
    string row,col;
    cin >> row >> col;
    bool diff = false;
    for (int i = 0; i < n; i++) {
        if (col[i] != row[0]) diff = true;
    }
    if (diff) {
        ans(!(row[0]=='1'));
    }
    else {
        ans((row[0]=='1'));
    }
}
 
void solve() {
    string run; cin >> run;
    int t; cin >> t;
    if (run == "first") for (int i = 1; i <= t; i++) send_grid();
    else for (int i = 1; i <= t; i++) receive_grid();
}
 
int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}

• Amazing
• Good
• Average
• Bad

• Very Hard
• Hard
• Average
• Easy
• Very Easy