Notice that after performing $$$z$$$ operations, the robot's $$$x$$$-coordinate will be exactly $$$z$$$, while its $$$y$$$-coordinate cannot exceed $$$z$$$.

We will first consider the case $$$b\le a$$$, then handle the special case $$$b=a+1$$$.

Notice that the robot can reach any point $$$(x,y)$$$ where $$$0\le y\le x$$$ and $$$x$$$ and $$$y$$$ have the same parity in exactly $$$x$$$ operations. To do so, we can first move up until reaching $$$y$$$, then alternate between moving up and down.

But what if $$$x$$$ and $$$y$$$ have different parities?

In this case, we can reach $$$(x,y-1)$$$ in exactly $$$x$$$ operations, since $$$x$$$ and $$$y-1$$$ have the same parity.

Now, recall that in each operation, the robot moves vertically before moving horizontally. Therefore, we can perform one additional operation:

The robot visits $$$(x,y)$$$ during this operation, so the answer is $$$x+1$$$.

Now, let's consider the remaining cases:

• If $$$b=a+1$$$, we can use the same construction, since $$$a$$$ and $$$b$$$ have different parities. We reach $$$(a,b-1)=(a,a)$$$ in $$$a$$$ operations, then visit $$$(a,b)$$$ during the next operation. Thus, the answer is $$$a+1$$$.
• If $$$b \gt a+1$$$, reaching $$$(a,b)$$$ is impossible, since the robot can make at most $$$a+1$$$ vertical moves before leaving column $$$a$$$.

Therefore, the answer is:

• $$$-1$$$ if $$$b \gt a+1$$$.
• $$$a$$$ if $$$a$$$ and $$$b$$$ have the same parity.
• $$$a+1$$$ otherwise.

The time complexity is $$$O(1)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int a, b;
    cin >> a >> b;
    if (b > a + 1) cout << -1 << '\n';
    else if (a % 2 == b % 2) cout << a << '\n';
    else cout << a + 1 << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$cnt[x]$$$ be the number of cards containing $$$x$$$.

We will consider the integers $$$x=0,1,2,\ldots$$$ in increasing order, and find the first $$$x$$$ such that $$$cnt[x] \lt 2k$$$.

We claim that Alice wins if and only if $$$cnt[x]=2k-1$$$.

Let's prove this by considering two cases.

Case 1: $$$cnt[x]=2k-1$$$.

We will show that it is impossible for Alice and Bob to have the same $$$\operatorname{mex}_k$$$, regardless of how they play.

Suppose both players have the same $$$\operatorname{mex}_k=y$$$. We consider three cases:

• If $$$y \lt x$$$, both players must have fewer than $$$k$$$ cards containing $$$y$$$. This is impossible because $$$cnt[y]\ge 2k$$$.
• If $$$y=x$$$, both players must again have fewer than $$$k$$$ cards containing $$$x$$$. This is impossible because $$$cnt[x]=2k-1$$$.
• If $$$y \gt x$$$, both players must have at least $$$k$$$ cards containing $$$x$$$. This is also impossible because $$$cnt[x]=2k-1 \lt 2k$$$.

Therefore, there is no possible value of $$$y$$$ for which both players have the same $$$\operatorname{mex}_k$$$.

Thus, Alice always wins, regardless of how either player plays.

Case 2: $$$cnt[x]\le 2k-2$$$.

We will show that Bob can always make both MEX values equal.

Bob can use the following strategy: pair as many cards with the same value as possible, then pair the remaining cards arbitrarily. Whenever Alice takes a card, Bob takes the other card from its pair.

This guarantees that each player receives either $$$\lfloor cnt[y]/2\rfloor$$$ or $$$\lceil cnt[y]/2\rceil$$$ cards containing any integer $$$y$$$.

Now notice that:

• For every $$$y \lt x$$$, we have $$$cnt[y]\ge 2k$$$, so both players receive at least $$$k$$$ cards containing $$$y$$$.
• For $$$y=x$$$, we have $$$cnt[x]\le 2k-2$$$, so both players receive fewer than $$$k$$$ cards containing $$$x$$$.

Therefore, both players have $$$\operatorname{mex}_k=x$$$, and Bob wins.

Thus, we only need to find the first $$$x$$$ with $$$cnt[x] \lt 2k$$$. The answer is "YES" if $$$cnt[x]=2k-1$$$, and "NO" otherwise.

The time complexity is $$$O(n)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    while (t--) {
        int n, k;
        cin >> n >> k;
 
        vector<int> cnt(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            int a;
            cin >> a;
            ++cnt[a];
        }
 
        for (int x = 0; x <= n; ++x) {
            if (cnt[x] < 2 * k) {
                cout << (cnt[x] == 2 * k - 1 ? "YES\n" : "NO\n");
                break;
            }
        }
    }
 
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$x$$$ be the greatest power of $$$2$$$ not exceeding $$$n$$$.

Define the prefix XOR array $$$p$$$ as follows:

• $$$p_0=0$$$.
• $$$p_i=a_1\oplus a_2\oplus\cdots\oplus a_i$$$.

Notice that a subarray $$$[l,r]$$$ has XOR equal to $$$0$$$ if and only if $$$p_{l-1}=p_r$$$.

Also, since $$$a_i\le n \lt 2x$$$, none of the elements has a set bit greater than or equal to $$$2x$$$. Therefore, every prefix XOR belongs to the range $$$[0,2x-1]$$$.

Now, let's see what happens when we add a new prefix XOR $$$p_i$$$:

• If $$$p_i$$$ has never appeared before, no new subarray with XOR $$$0$$$ is created, so the beauty increases by $$$1$$$.
• If $$$p_i$$$ has appeared exactly once, exactly one new subarray with XOR $$$0$$$ is created, so the beauty stays the same.
• If $$$p_i$$$ has appeared at least twice, the beauty decreases.

Since there are only $$$2x$$$ possible prefix XOR values, and $$$p_0=0$$$ already exists, the maximum possible beauty is at most $$$2x-1$$$.

To achieve this beauty with the maximum possible length, we want every prefix XOR from $$$0$$$ to $$$2x-1$$$ to appear exactly twice.

This gives us $$$4x$$$ prefix XORs, corresponding to an array of length $$$4x-1$$$.

Now, let's show how to construct such an array.

Instead of constructing $$$a$$$ directly, we will construct the prefix XOR array $$$p$$$, then recover $$$a$$$ using $$$a_i=p_{i-1}\oplus p_i$$$.

First, visit all integers from $$$0$$$ to $$$x-1$$$ in increasing order, then visit them again in decreasing order:

After that, do the same for all integers from $$$x$$$ to $$$2x-1$$$:

Clearly, every integer from $$$0$$$ to $$$2x-1$$$ appears exactly twice.

We only need to verify that every $$$a_i=p_{i-1}\oplus p_i$$$ is at most $$$n$$$.

Notice that:

• The XOR of any two integers from $$$[0,x-1]$$$ is smaller than $$$x$$$.
• The XOR of any two integers from $$$[x,2x-1]$$$ is also smaller than $$$x$$$, since their highest set bits cancel.
• The only jump between these two ranges is from $$$0$$$ to $$$x$$$, whose XOR is exactly $$$x$$$.

Therefore, every element of $$$a$$$ is at most $$$x\le n$$$, so our construction is valid.

Since every prefix XOR appears exactly twice, we have exactly $$$2x$$$ subarrays with XOR $$$0$$$. Thus, the beauty is

which achieves the maximum possible beauty with the maximum possible length.

The time complexity is $$$O(n)$$$ per test case.

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

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

    int x = 1;
    while (2 * x <= n) x *= 2;

    vector<int> p;
    for (int i = 0; i < x; i++) p.push_back(i);
    for (int i = x - 1; i >= 0; i--) p.push_back(i);
    for (int i = x; i < 2 * x; i++) p.push_back(i);
    for (int i = 2 * x - 1; i >= x; i--) p.push_back(i);

    cout << (int)p.size() - 1 << '\n';
    for (int i = 1; i < (int)p.size(); i++)
        cout << (p[i] ^ p[i - 1]) << " \n"[i == (int)p.size() - 1];
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$f(s)$$$ be the number of infected positions in the segment $$$[s,s+m-1]$$$.

First, notice that when we increase $$$s$$$ by $$$1$$$, we remove the position $$$s$$$ and add the position $$$s+m$$$.

Therefore, $$$f(s)$$$ can change by at most $$$1$$$ when we increase $$$s$$$ by $1.

This observation will be useful later.

Now, let's find the maximum possible value of $$$f(s)$$$.

We claim that the maximum is achieved at some $$$s=l_i$$$.

To see why, consider any starting position $$$s$$$:

• If $$$s$$$ is infected but is not the beginning of an infection interval, we can move $$$s$$$ to the left by $$$1$$$. Since the newly added position is infected, $$$f(s)$$$ cannot decrease. We can repeat this until reaching the beginning of that interval.
• If $$$s$$$ is not infected, we can move $$$s$$$ to the right by $$$1$$$. Since the removed position is not infected, $$$f(s)$$$ cannot decrease. We can repeat this until reaching the beginning of the next infection interval.

Therefore, it is sufficient to check $$$f(l_i)$$$ for every interval.

Let $$$mx$$$ be the maximum value we find, and let $$$pos$$$ be a position where $$$f(pos)=mx$$$.

Now, we have three cases:

• If $$$k \gt mx$$$, the answer is $$$-1$$$, since we cannot infect that many people.
• If $$$k=mx$$$, we can simply output $$$pos$$$.
• Otherwise, $$$k \lt mx$$$, and we will find a valid position using binary search.

Now, suppose $$$k \lt mx$$$. We know that $$$f(pos)=mx \gt k$$$, and we also know that $$$f(10^{15}+1)=0\le k$$$, since there are no infected positions after $$$10^{15}$$$.

Therefore, we have two positions: one where $$$f(s) \gt k$$$, and another where $$$f(s)\le k$$$.

Recall that moving $$$s$$$ by $$$1$$$ changes $$$f(s)$$$ by at most $$$1$$$. This means that somewhere between these two positions, there must be a position where $$$f(s)=k$$$.

We can find such a position using binary search!

Maintain two positions $$$l$$$ and $$$r$$$ such that $$$f(l) \gt k$$$ and $$$f(r)\le k$$$. Initially, set $$$l=pos$$$ and $$$r=10^{15}+1$$$.

Let $$$mid=\lfloor(l+r)/2\rfloor$$$.

• If $$$f(mid) \gt k$$$, set $$$l=mid$$$.
• Otherwise, set $$$r=mid$$$.

Notice that we always keep one position with $$$f(s) \gt k$$$ and another with $$$f(s)\le k$$$, so we never lose the guarantee that a valid answer exists between them.

Continue until $$$r=l+1$$$.

Now, since $$$f(l) \gt k$$$ and $$$f(r)\le k$$$, and these positions are adjacent, we must have $$$f(r)=k$$$. Therefore, we can output $$$r$$$.

Note that $$$f(s)$$$ does not need to be monotonic for this binary search to work! We only need the fact that $$$f(s)$$$ changes by at most $$$1$$$ between consecutive positions.

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

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

    vector<long long> l(n), r(n), pref(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
        pref[i + 1] = pref[i] + r[i] - l[i] + 1;
    }

    auto f = [&](long long s) -> long long {
        long long e = s + m - 1;

        int i = lower_bound(r.begin(), r.end(), s) - r.begin();
        int j = upper_bound(l.begin(), l.end(), e) - l.begin() - 1;

        if (i > j) return 0;

        long long ans = pref[j + 1] - pref[i];
        ans -= max(0LL, s - l[i]);
        ans -= max(0LL, r[j] - e);
        return ans;
    };

    long long mx = -1, pos = 0;
    for (int i = 0; i < n; i++) {
        long long cur = f(l[i]);
        if (cur > mx) {
            mx = cur;
            pos = l[i];
        }
    }

    if (k > mx) {
        cout << -1 << '\n';
        return;
    }

    if (k == mx) {
        cout << pos << '\n';
        return;
    }

    long long low = pos, high = 1000000000000001LL;

    while (high - low > 1) {
        long long mid = (low + high) / 2;
        if (f(mid) > k) low = mid;
        else high = mid;
    }

    cout << high << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, let's solve a relaxed version of the problem, where we are allowed to split any element, even if it is already small enough to be erased.

Let's find a greedy solution for this relaxed version.

Suppose we perform exactly $$$c$$$ splits. Each split increases the number of elements by $$$1$$$, so we will need $$$n+c$$$ erasures.

Therefore, the total number of operations is

Now, notice that we can always perform all splits before any erasures.

We can prove this using an exchange argument. If a split happens after an erasure, we can swap these two operations. The split remains valid because splitting is always allowed in our relaxed version, and the erasure remains valid because $$$k$$$ only increases.

By repeatedly applying this argument, we can rearrange the operations into the following order:

Now, let's binary search on the number of splits $$$c$$$.

To check whether $$$c$$$ splits are sufficient, we will process the erasures in reverse order, starting from the last erasure and moving toward the first.

The value of $$$k$$$ at the last operation is

Let $$$H$$$ be the largest remaining element.

We have two cases:

• If $$$H \gt S$$$, we must split $$$H$$$, since we cannot erase it now, and we certainly cannot erase it at any earlier operation, where $$$k$$$ is even smaller.

• If $$$H\le S$$$, we claim that it is optimal to erase $$$H$$$ now.

Let's prove the second case.

Consider an optimal solution that does not erase $$$H$$$ at this moment. There are two possibilities:

1. It erases $$$H$$$ at an earlier operation. In this case, we can simply swap that erasure with the current one. This is valid because $$$H\le S$$$, and the other element, being no larger than $$$H$$$, can also be erased earlier.

2. It splits $$$H$$$ instead. Suppose it erases some smaller element $$$y$$$ at this moment. We can instead erase $$$H$$$ and split $$$y$$$. Since $$$y\le H$$$, the two elements produced by splitting $$$y$$$ are no larger than those produced by splitting $$$H$$$. Therefore, we can perform the same subsequent operations without making anything harder. If the element erased at this moment was itself produced by splitting $$$H$$$, we can simply erase $$$H$$$ instead and avoid those splits.

Thus, in both cases, there exists an optimal solution that erases $$$H$$$ now.

This proves our greedy strategy.

Whenever we erase an element, we decrease $$$S$$$ by $$$1$$$, since we move to the previous erasure. Whenever we split an element, we replace it with two elements equal to $$$\lceil H/2\rceil$$$, without changing $$$S$$$.

If we need more than $$$c$$$ splits, the check fails. Otherwise, it succeeds.

We can implement this efficiently using a frequency array to maintain the remaining elements.

Now, let $$$X$$$ be the minimum number of operations for the relaxed problem.

Clearly, the answer to the original problem is at least $$$X$$$, since the relaxed problem allows everything the original problem allows.

However, notice something important about our greedy construction: we only split an element when $$$H \gt S$$$.

Since $$$S$$$ is at least the value of $$$k$$$ when that split would actually happen, we also have $$$H \gt k$$$ at that moment.

Therefore, every split performed by our greedy solution is valid in the original problem as well!

This means our solution to the relaxed problem is also a valid solution to the original problem, so the minimum number of operations is the same for both.

Finally, if $$$c$$$ is the minimum number of splits found by binary search, the answer is

The time complexity is $$$O(n\log n)$$$ per test case, and the space complexity is $$$O(n)$$$.

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

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

    vector<int> a(n);
    int mx = 0;
    for (int &x : a) {
        cin >> x;
        mx = max(mx, x);
    }

    vector<int> freq(mx + 1);
    for (int x : a) freq[x]++;

    auto ok = [&](int c) {
        vector<int> cnt = freq;
        int alive = n, used = 0, H = mx;
        long long S = 1LL * k + n + 2LL * c - 1;

        while (alive > 0) {
            while (cnt[H] == 0) H--;

            if (H <= S) {
                cnt[H]--;
                alive--;
                S--;
            } else {
                if (used == c) return false;
                cnt[H]--;
                cnt[(H + 1) / 2] += 2;
                alive++;
                used++;
            }
        }
        return true;
    };

    int l = 0, r = max(0, mx - k);
    while (l < r) {
        int mid = (l + r) / 2;
        if (ok(mid)) r = mid;
        else l = mid + 1;
    }

    cout << n + 2 * l << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, notice that we can always make the array beautiful using at most $$$2$$$ operations, by setting $$$a_1=a_n=10^9$$$.

Now, let's check whether the array is already beautiful. If it is, the answer is $$$0$$$.

Otherwise, the answer must be either $$$1$$$ or $$$2$$$.

We claim that if the answer is $$$1$$$, at least one of the following three operations makes the array beautiful.

Let $$$mx$$$ be the maximum element of the array, and let $$$pos$$$ be any position such that $$$a_{pos}=mx$$$.

The three operations are:

1. Set $$$a_1=mx$$$.
2. Set $$$a_n=mx$$$.
3. Set $$$a_{pos}=1$$$.

We can simply try each operation and check whether the resulting array is beautiful. If any of them works, the answer is $$$1$$$. Otherwise, the answer is $$$2$$$.

Now, let's prove why these three cases are sufficient.

Imagine the array looks like this:

Notice that setting $$$a_1=mx$$$ makes the entire left side covered by good pairs, while setting $$$a_n=mx$$$ does the same for the right side.

If neither operation makes the array beautiful, this means there are still uncovered positions on both sides.

Therefore, if we want to fix everything using only one operation, we must somehow fix both sides at once.

The only remaining possibility is to decrease a maximum element, allowing good pairs to connect across it.

Suppose changing this maximum element to some value $$$X$$$ makes the array beautiful.

We claim that changing it to $$$1$$$ would also work.

Why? Any new good pair that spans this position remains good if we decrease its value even further.

The other possibility is that the new value $$$X$$$ creates two good pairs, one on each side, looking like this:

Here, the middle $$$X$$$ is the element we changed, and both pairs are good.

If we decrease the middle element to $$$1$$$, the two pairs can be replaced by one larger good pair:

Thus, decreasing the maximum element to $$$1$$$ is sufficient.

lets also note if that max element occurs more than once this is useless.

This proves that checking our three operations is enough to find an optimal solution.

Finally, checking whether an array is beautiful can be implemented in $$$O(n\log n)$$$ using several approaches, or in $$$O(n)$$$ using a monotonic stack.

Since we perform only a constant number of checks, the overall time complexity is $$$O(n)$$$ per test case.

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

bool beautiful(vector<int>& a) {
    int n = a.size();
    vector<int> st, diff(n + 1);

    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] < a[i])
            st.pop_back();

        if (!st.empty() && a[st.back()] == a[i]) {
            diff[st.back()]++;
            diff[i + 1]--;
        }
        st.push_back(i);
    }

    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        if (cur == 0) return false;
    }
    return true;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    if (beautiful(a)) {
        cout << 0 << '\n';
        return;
    }

    int pos = max_element(a.begin(), a.end()) - a.begin();
    int mx = a[pos];

    auto check = [&](int i, int x) {
        int old = a[i];
        a[i] = x;
        bool ok = beautiful(a);
        a[i] = old;
        if (ok) {
            cout << 1 << '\n';
            cout << i + 1 << ' ' << x << '\n';
        }
        return ok;
    };

    if (check(0, mx)) return;
    if (check(n - 1, mx)) return;
    if (check(pos, 1)) return;

    cout << 2 << '\n';
    cout << 1 << ' ' << mx << '\n';
    cout << n << ' ' << mx << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, let's determine when it is impossible to fill the grid.

Suppose there are two $$$1\times 1$$$ pieces in the same row, with only $$$1\times 2$$$ pieces between them.

For example:

Since every $$$1\times 1$$$ piece must contain $$$1$$$, the first cell is forced to be $$$1$$$. This forces the next $$$1\times 2$$$ piece to be $$$[2,1]$$$, and the same applies to every following piece.

We end up with:

Clearly, this is invalid because the last two adjacent cells both contain $$$1$$$.

The same argument applies vertically to two $$$1\times 1$$$ pieces with only $$$2\times 1$$$ pieces between them.

We claim that these are the only cases where a valid filling is impossible.

Let's prove this by constructing a valid filling whenever neither case occurs.

Step 1: Fill all thin pieces.

First, put $$$1$$$ in every $$$1\times 1$$$ piece.

Now, let's fill all $$$1\times y$$$ and $$$y\times 1$$$ pieces.

We will only explain the construction for horizontal pieces, since vertical pieces can be handled in exactly the same way.

Consider any two $$$1\times 1$$$ pieces in the same row.

Since our impossible condition does not occur, there must be at least one $$$1\times y$$$ piece between them with $$$y\ge 3$$$.

Choose the first such piece from the left and call it the turning point.

We fill the pieces between the two $$$1\times 1$$$ pieces as follows:

• For every piece before the turning point, write its numbers in decreasing order.
• For every piece after the turning point, write its numbers in increasing order.
• For the turning point itself, use the order $$$[y,1,2,3,\ldots,y-1]$$$.

Notice that this guarantees that adjacent cells contain different numbers, including across the boundaries of the pieces.

For portions of the row before the first $$$1\times 1$$$ piece, after the last one, or rows containing no $$$1\times 1$$$ pieces, we can simply choose a suitable increasing or decreasing order.

We apply the same construction vertically to fill all remaining $$$y\times 1$$$ pieces.

Step 2: Fill the rows containing $$$1$$$.

Notice that by choosing our coloring patterns consistently in the previous step, the already-colored cells in each partially filled row contain the same value.

Now, consider every partially filled row whose already-colored cells contain $$$1$$$.

We can fill the gaps between these $$$1$$$ s using exactly the same turning-point construction from Step 1.

This fills all such rows while ensuring that horizontally adjacent cells contain different numbers.

Step 3: Fill the remaining cells.

Now, let's consider the remaining unfilled rows.

The important observation is that these rows can be handled independently, since the vertical constraints have already been taken care of by our construction.

Furthermore, every gap we need to fill has the same value, say $$$x$$$, on both its left and right boundaries.

Therefore, we only need to arrange the remaining numbers inside each piece so that adjacent values are different and neither boundary creates a conflict.

We can use the same idea as before: arrange the values in increasing or decreasing order, and use a turning point whenever necessary.

Since the required values are available and the vertical constraints are already satisfied, we can fill all remaining gaps.

Thus, we have constructed a valid filling whenever neither of the two impossible configurations occurs, completing the proof.

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Editorial will be Added when Axial isn't tired :(

~~~~

~~~~

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve