2227AUnreviewedunratedGPT-5.4 (high)

Koshary

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

implementation math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Try ignoring the exact values for a second and look at parity. What kinds of coordinates can long steps produce starting from $(0,0)$ ?

A long step adds $2$ to exactly one coordinate, so it never changes that coordinate’s parity. Starting from $(0,0)$ , after any number of long steps you are always at some point of the form $(2a,2b)$ .

Now think about the single short step. It adds $1$ to one coordinate, and you can use it at most once. So how many coordinates can change parity during the whole trip?

That means the only parity patterns you can end with are:

(\text{even},\text{even}),\quad (\text{odd},\text{even}),\quad (\text{even},\text{odd}).

What parity pattern is impossible?

The only impossible case is when both $x$ and $y$ are odd. If at least one of them is even, just use long steps to build the even parts, and if needed spend your one short step on the odd coordinate. So the answer is NO iff

x \bmod 2 = 1 \quad \text{and} \quad y \bmod 2 = 1.

Observation 1

Long steps are boring in the best possible way: they add exactly $2$ to one coordinate.

So from $(0,0)$ , after any number of long steps, Yousef can reach any point of the form

(2a, 2b)

for nonnegative integers $a,b$ .

In other words, with only long steps, both coordinates must stay even. Parity does not budge. Zero drama.

Observation 2

A short step adds $1$ to exactly one coordinate, and Yousef may use it at most once.

That means during the whole journey, he can flip the parity of at most one coordinate.

So the final reachable parity patterns are exactly:

(\text{even},\text{even}),\quad (\text{odd},\text{even}),\quad (\text{even},\text{odd}).

The one pattern that cannot happen is

(\text{odd},\text{odd}),

because that would require flipping both coordinates’ parity, and he only gets one short step. Life is cruel.

Conclusion

Yousef can reach $(x,y)$ iff not both $x$ and $y$ are odd.

So the condition is simply:

\text{reachable} \iff \neg(x\text{ is odd }\land y\text{ is odd}).

Equivalently:

if $x$ and $y$ are both odd, print NO
otherwise, print YES

Why this is sufficient

If both are even, just use long steps only.

If exactly one is odd, say $x$ is odd and $y$ is even, then:

use long steps to reach $(x-1, y)$ , which has even coordinates,
then use one short step in the $x$ direction.

Same idea if $y$ is the odd one.

So the parity condition is not just necessary — it’s also sufficient.

Complexity

Each test case is answered in constant time:

O(1)

For $t$ test cases, total complexity is:

O(t)

with

O(1)

extra memory.

Nice little implementation/math problem. Blink and you’ll overcomplicate it.

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;

        // Reachable unless both coordinates are odd.
        cout << ((x % 2 == 1 && y % 2 == 1) ? "NO" : "YES") << '\n';
    }

    return 0;
}

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;

        // Reachable unless both coordinates are odd.
        cout << ((x % 2 == 1 && y % 2 == 1) ? "NO" : "YES") << '\n';
    }

    return 0;
}

View on Codeforces Back to the list