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