Zookeeper and The Infinite Zoo
Contest: Codeforces Global Round 13
Difficulty rating: 1800
Tags: bitmasks, constructive algorithms, dp, greedy, math

There is a new attraction in Singapore Zoo: The Infinite Zoo.

The Infinite Zoo can be represented by a graph with an infinite number of vertices labeled $$$1,2,3,\ldots$$$. There is a directed edge from vertex $$$u$$$ to vertex $$$u+v$$$ if and only if $$$u\&v=v$$$, where $$$\&$$$ denotes the bitwise AND operation. There are no other edges in the graph.

Zookeeper has $$$q$$$ queries. In the $$$i$$$-th query she will ask you if she can travel from vertex $$$u_i$$$ to vertex $$$v_i$$$ by going through directed edges.

Input format:
The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.

The $$$i$$$-th of the next $$$q$$$ lines will contain two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i < 2^{30}$$$) — a query made by Zookeeper.

Output format:
For the $$$i$$$-th of the $$$q$$$ queries, output "YES" in a single line if Zookeeper can travel from vertex $$$u_i$$$ to vertex $$$v_i$$$. Otherwise, output "NO".

You can print your answer in any case. For example, if the answer is "YES", then the output "Yes" or "yeS" will also be considered as correct answer.

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

Note:
The subgraph on vertices $$$1,2,3,4,5,6$$$ is shown below.

Example input:
5
1 4
3 6
1 6
6 2
5 5

Example output:
YES
YES
NO
NO
YES

Editorial:
Firstly, we can show that the reachability graph is equivalent if we restrict to a directed edge between vertices $$$u$$$ and $$$u+v$$$ if $$$u\&v=v$$$ and that $$$v=2^k$$$ for some $$$k$$$.
This is because we can add each bit from $$$v$$$ from $$$u$$$ from the highest bit as adding a bit to a number will not affect lower bits.
Now, we observe that such as operation converts a binary string of the form $$$01\ldots11$$$ into $$$10\ldots00$$$ for some substring when we represent $$$u$$$ as a binary string. (more significant bits are to the left).
Now, we consider $$$s$$$ and $$$t$$$ as binary strings.
If and only if there is a matching from bits in $$$t$$$ to a lower bit in $$$s$$$ and $$$t$$$ > $$$s$$$, then $$$t$$$ is reachable from $$$s$$$.
Turning $$$01\ldots11$$$ into $$$10\ldots00$$$ means that we can move a bit ($$$01$$$->$$$10$$$) or we can squish multiple bits ($$$0111$$$->$$$1000$$$).
Let us show it is necessary. If $$$s>t$$$, it is impossible. And if there is no such matching, we are not able to put a position in $$$t$$$ as bits cannot move back, or there are not enough bits in $$$s$$$ to form $$$t$$$ (since the number of bits cannot increase).
Let is show it is sufficient. Since $$$s<t$$$ ($$$s=t$$$ is trivial), the strings have some common prefix and the most significant different bit has $$$0$$$ in $$$s$$$ and $$$1$$$ and $$$t$$$. Now, we can shift every bit in s into a position in t and squish the most significant bits.
To check if there is a matching, we find the least significant bit ($$$lsb$$$) of $$$t$$$ and $$$s$$$. if $$$lsb(t) < lsb(s)$$$ or if $$$s = 0$$$, then it is impossible. Else, we remove the $$$lsb$$$ from both $$$t$$$ and $$$s$$$ and repeat. If we're able to remove bits until $$$t=0$$$, then it is possible to go from $$$s$$$ to $$$t$$$.