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