Vlad and an Odd Ordering
Contest: Codeforces Round 928 (Div. 4)
Difficulty rating: 1500
Tags: binary search, bitmasks, data structures, dp, implementation, math, number theory

Vladislav has $$$n$$$ cards numbered $$$1, 2, \dots, n$$$. He wants to lay them down in a row as follows:

- First, he lays down all the odd-numbered cards from smallest to largest.
- Next, he lays down all cards that are twice an odd number from smallest to largest (i.e. $$$2$$$ multiplied by an odd number).
- Next, he lays down all cards that are $$$3$$$ times an odd number from smallest to largest (i.e. $$$3$$$ multiplied by an odd number).
- Next, he lays down all cards that are $$$4$$$ times an odd number from smallest to largest (i.e. $$$4$$$ multiplied by an odd number).
- And so on, until all cards are laid down.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^9$$$) — the number of cards Vlad has, and the position of the card you need to output.

Output format:
For each test case, output a single integer — the $$$k$$$-th card Vladislav lays down.

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

Note:
In the first seven test cases, $$$n=7$$$. Vladislav lays down the cards as follows:

- First — all the odd-numbered cards in the order $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$.
- Next — all cards that are twice an odd number in the order $$$2$$$, $$$6$$$.
- Next, there are no remaining cards that are $$$3$$$ times an odd number. (Vladislav has only one of each card.)
- Next — all cards that are $$$4$$$ times an odd number, and there is only one such card: $$$4$$$.
- There are no more cards left, so Vladislav stops.

Example input:
11
7 1
7 2
7 3
7 4
7 5
7 6
7 7
1 1
34 14
84 19
1000000000 1000000000

Example output:
1
3
5
7
2
6
4
1
27
37
536870912

Editorial:
Idea. The problem is very recursive; after we lay all the odd cards down, we have the same problem as we started with, but every card is multiplied by $$$2$$$. Can you solve the problem from here?
We present two different solutions, which are actually the same idea, but presented a little differently, so you can understand the problem better ;).
Solution 1. Note that we will never lay cards down on moves that are not powers of $$$2$$$. Why? Well, for example, if a number is $$$3 \times \mathrm{odd}$$$, then this number is also $$$1 \times \mathrm{odd}$$$, and similarly for $$$5 \times \mathrm{odd}$$$, $$$7 \times \mathrm{odd}$$$, $$$\dots$$$. This same logic shows that $$$6 \times \mathrm{odd}$$$ numbers will be laid down in the $$$2 \times \mathrm{odd}$$$ step, etc.
This means that all our cards are divided into "blocks":
• $$$1 \times \mathrm{odd}$$$ numbers (odd numbers),
• $$$2 \times \mathrm{odd}$$$ numbers (multiples of $$$2$$$ but not $$$4$$$),
• $$$4 \times \mathrm{odd}$$$ numbers (multiples of $$$4$$$ but not $$$8$$$),
• $$$8 \times \mathrm{odd}$$$ numbers (multiples of $$$8$$$ but not $$$16$$$),
• and so on.
This leads to the solution. We can find the number of cards in each of these groups by repeatedly finding the number of odd cards, removing them, and continuing the process on the remaining deck. So to find the $$$k$$$-th card, we find the first prefix sum that exceeds $$$k$$$, and find the $$$k$$$-th card in this block.
Solution 2. Let's make some observations:
• Of the cards $$$1, 2, \dots, n$$$, there are $$$\lceil \frac{n}{2} \rceil$$$ odd ones.
• The even-numbered cards cannot be laid down on an odd-numbered step ($$$1 \times \mathrm{odd}$$$, $$$3 \times \mathrm{odd}$$$, $$$5 \times \mathrm{odd}$$$, $$$\dots$$$), because all those values are odd.   In other words, even-numbered cards can only be laid down at even-numbered steps $$$2 \times \mathrm{odd}$$$, $$$4 \times \mathrm{odd}$$$, $$$6 \times \mathrm{odd}$$$, $$$\dots$$$.
• In other words, even-numbered cards can only be laid down at even-numbered steps $$$2 \times \mathrm{odd}$$$, $$$4 \times \mathrm{odd}$$$, $$$6 \times \mathrm{odd}$$$, $$$\dots$$$.
Otherwise, once we are finished laying down all the odd numbers, $$$\lceil \frac{n}{2} \rceil$$$ turns have passed, and our remaining cards are the numbers $$$2, 4, 6, \dots$$$ and we will only lay down cards in the steps $$$2 \times \mathrm{odd}$$$, $$$4 \times \mathrm{odd}$$$, $$$6 \times \mathrm{odd}$$$, $$$\dots$$$.
Since all the remaining numbers have a factor of $$$2$$$, we will divide it out and get the following equivalent problem: and our remaining cards are the numbers $$$1, 2, 3, \dots$$$ and we will only lay down cards in the steps $$$1 \times \mathrm{odd}$$$, $$$2 \times \mathrm{odd}$$$, $$$3 \times \mathrm{odd}$$$, $$$\dots$$$. But this is exactly the same as the original problem! Thus we can solve this problem recursively.
More formally, let the answer be $$$\mathrm{ans}(n, k)$$$. Then if $$$k \leq \lceil \frac{n}{2} \rceil$$$, output the $$$k$$$-th odd number; otherwise, output $$$2 \cdot \mathrm{ans}(\lfloor \frac{n}{2} \rfloor, k - \lceil \frac{n}{2} \rceil)$$$. This works in $$$\mathcal{O}(\log n)$$$ per test case.