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