Reverse
Contest: Codeforces Round 760 (Div. 3)
Difficulty rating: 2000
Tags: bitmasks, constructive algorithms, dfs and similar, implementation, math, strings

You are given two positive integers $$$x$$$ and $$$y$$$. You can perform the following operation with $$$x$$$: write it in its binary form without leading zeros, add $$$0$$$ or $$$1$$$ to the right of it, reverse the binary form and turn it into a decimal number which is assigned as the new value of $$$x$$$.

For example:

- $$$34$$$ can be turned into $$$81$$$ via one operation: the binary form of $$$34$$$ is $$$100010$$$, if you add $$$1$$$, reverse it and remove leading zeros, you will get $$$1010001$$$, which is the binary form of $$$81$$$.
- $$$34$$$ can be turned into $$$17$$$ via one operation: the binary form of $$$34$$$ is $$$100010$$$, if you add $$$0$$$, reverse it and remove leading zeros, you will get $$$10001$$$, which is the binary form of $$$17$$$.
- $$$81$$$ can be turned into $$$69$$$ via one operation: the binary form of $$$81$$$ is $$$1010001$$$, if you add $$$0$$$, reverse it and remove leading zeros, you will get $$$1000101$$$, which is the binary form of $$$69$$$.
- $$$34$$$ can be turned into $$$69$$$ via two operations: first you turn $$$34$$$ into $$$81$$$ and then $$$81$$$ into $$$69$$$.

Your task is to find out whether $$$x$$$ can be turned into $$$y$$$ after a certain number of operations (possibly zero).

Input format:
The only line of the input contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^{18}$$$).

Output format:
Print YES if you can make $$$x$$$ equal to $$$y$$$ and NO if you can't.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you don't even need to do anything.

The fourth example is described in the statement.

Example input:
3 3

Example output:
YES

Example input:
7 4

Example output:
NO

Editorial:
There are two main approaches to this problem.
Approach $$$1$$$. Let's analyze how the binary representation of $$$x$$$ changes after the operation. If there are no zeroes at the end of it, appending $$$0$$$ just reverses the binary representation; if there are any trailing zeroes, we remove them and reverse the binary representation. If we append $$$1$$$, we just reverse the binary representation and add $$$1$$$ at the beginning. No matter which action we choose on the first step, the resulting binary representation will have $$$1$$$ at its beginning and $$$1$$$ at its end, so no bits can be removed from it (no zero from the resulting binary representation can become leading). It means that every number we can obtain from $$$x$$$ will have the following form: several ones (maybe none), then $$$s$$$, then several ones (again, maybe none), where $$$s$$$ is one of the following four strings:
• the binary representation of $$$x$$$ after appending $$$1$$$ in the first operation;
• the binary representation of $$$x$$$ after appending $$$0$$$ in the first operation;
• one of the aforementioned representations, but reversed.
We can check that $$$y$$$ meets one of these four templates, but since we only considered the case when we apply at least one operation, we also have to verify if $$$x = y$$$.
Approach $$$2$$$. Run something like implicit BFS or DFS to generate all possible values you can obtain, pruning when the length of the binary representation we get becomes too large (say, greater than $$$100$$$). Why does this work fast? As we have shown in our first approach, the numbers we can get from $$$x$$$ have a very specific form, and if we limit their lengths to $$$100$$$, we will consider only about $$$400$$$ different numbers. Note that if you try this approach, you have to store the obtained numbers in some associative data structure (I use a set of strings in my solution).