1275. The kth Submask in Descending Order
For each of q queries m k, print the submask of m that the descending
enumeration visits at position k, counting from 0. If m has fewer than
k + 1 submasks, print -1.
m=5 k=0 -> 5 the enumeration is 5 4 1 0
m=5 k=1 -> 4
m=5 k=2 -> 1
m=5 k=4 -> -1 only four submasks exist
## What most people try first
Two wrong guesses, both of which look right on the mask m = 15.
The first is m - k. On a FULL mask every value below m is a submask, so the
enumeration really is m, m-1, m-2, ... and m - k is correct. On m = 5 it
gives 5, 4, 3, 2, and 3 and 2 are not submasks of 5 at all.
The second is to treat k as a bit pattern and scatter it into m's set
positions, which IS a valid bijection from 0 .. 2^p - 1 onto the submasks. It
just does not produce this order: scattering gives ascending order by the
scattered pattern, so index 1 lands on m's lowest set bit rather than on the
second-largest submask.
## Walk the enumeration
s = m
for i in 0 .. k-1:
if s == 0: answer -1 and stop
s = (s - 1) & m
answer s
Each step is #1270's, so after i steps s is the i-th submask in
descending order. The guard is the whole subtlety: the enumeration ENDS at 0,
and (0 - 1) & m is m again, so a loop without the zero check silently
wraps around to the top and starts over. A query with k one past the end then
returns m, which is a plausible-looking wrong answer rather than a crash.
## How many submasks there are, and why the bound on k is what it is
m has exactly 2^popcount(m) submasks, since each set bit is independently
in or out. So the valid indices are 0 through 2^popcount(m) - 1, and the
answer is -1 for anything larger. With m up to 1048575 that is at most
1048576 submasks, which is why k is allowed up to 1048576: exactly one
past the largest possible count, so the -1 case is reachable at every popcount.
## Cost
O(k) per query, so O(q * k) in the worst case. There is no shortcut to the
k-th element of this particular order, which is itself the lesson: the
scatter bijection gives O(popcount) access to the k-th submask in a
DIFFERENT order, and if a problem only needs some order, that is the one to use.
Pinning the order, as this problem does, is what makes the walk necessary.
## Width
Masks are at most 1048575, below 2^20, so every mask and every intermediate
fits in a signed 32-bit integer, limit 2147483647. k is at most 1048576
and also fits. JavaScript's & and - are safe on plain Numbers here,
because every value involved already fits in signed 32 bits. No 64-bit type and
no BigInt is needed.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ m ≤ 1048575` - `0 ≤ k ≤ 1048576`
Input
The first line contains an integer q.
Each of the next q lines contains two integers m and k, separated by a space.
Output
For each query print one integer on its own line: the submask at position k of the descending enumeration of m, or -1 if m has no such submask.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.