Olya and magical square
Contest: Codeforces Round 524 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, implementation, math

Recently, Olya received a magical square with the size of $$$2^n\times 2^n$$$.

It seems to her sister that one square is boring. Therefore, she asked Olya to perform exactly $$$k$$$ splitting operations.

A Splitting operation is an operation during which Olya takes a square with side $$$a$$$ and cuts it into 4 equal squares with side $$$\dfrac{a}{2}$$$. If the side of the square is equal to $$$1$$$, then it is impossible to apply a splitting operation to it (see examples for better understanding).

Olya is happy to fulfill her sister's request, but she also wants the condition of Olya's happiness to be satisfied after all operations.

The condition of Olya's happiness will be satisfied if the following statement is fulfilled:

Let the length of the side of the lower left square be equal to $$$a$$$, then the length of the side of the right upper square should also be equal to $$$a$$$. There should also be a path between them that consists only of squares with the side of length $$$a$$$. All consecutive squares on a path should have a common side.

Obviously, as long as we have one square, these conditions are met. So Olya is ready to fulfill her sister's request only under the condition that she is satisfied too. Tell her: is it possible to perform exactly $$$k$$$ splitting operations in a certain order so that the condition of Olya's happiness is satisfied? If it is possible, tell also the size of the side of squares of which the path from the lower left square to the upper right one will consist.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of tests.

Each of the following $$$t$$$ lines contains two integers $$$n_i$$$ and $$$k_i$$$ ($$$1 \le n_i \le 10^9, 1 \le k_i \le 10^{18}$$$) — the description of the $$$i$$$-th test, which means that initially Olya's square has size of $$$2^{n_i}\times 2^{n_i}$$$ and Olya's sister asks her to do exactly $$$k_i$$$ splitting operations.

Output format:
Print $$$t$$$ lines, where in the $$$i$$$-th line you should output "YES" if it is possible to perform $$$k_i$$$ splitting operations in the $$$i$$$-th test in such a way that the condition of Olya's happiness is satisfied or print "NO" otherwise. If you printed "YES", then also print the $$$log_2$$$ of the length of the side of the squares through space, along which you can build a path from the lower left square to the upper right one.

You can output each letter in any case (lower or upper).

If there are multiple answers, print any.

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

Note:
In each of the illustrations, the pictures are shown in order in which Olya applied the operations. The recently-created squares are highlighted with red.

In the first test, Olya can apply splitting operations in the following order:

Olya applies one operation on the only existing square.

The condition of Olya's happiness will be met, since there is a path of squares of the same size from the lower left square to the upper right one:

The length of the sides of the squares on the path is $$$1$$$. $$$log_2(1) = 0$$$.

In the second test, Olya can apply splitting operations in the following order:

Olya applies the first operation on the only existing square. She applies the second one on the right bottom square.

The condition of Olya's happiness will be met, since there is a path of squares of the same size from the lower left square to the upper right one:

The length of the sides of the squares on the path is $$$2$$$. $$$log_2(2) = 1$$$.

In the third test, it takes $$$5$$$ operations for Olya to make the square look like this:

Since it requires her to perform $$$7$$$ splitting operations, and it is impossible to perform them on squares with side equal to $$$1$$$, then Olya cannot do anything more and the answer is "NO".

Example input:
3
1 1
2 2
2 12

Example output:
YES 0
YES 1
NO

Editorial:
At first let's check if the value of $$$k$$$ is not too large. This can be done greedily in the folllowing way:
First splitting operation would be applied on the only existing inital square.
After that we have $$$4$$$ squares with sides $$$2^{n-1}$$$. Now we will do $$$4$$$ spliiting operations each on one of them. Then we will have $$$16$$$ squares with sides $$$2^{n-2}$$$. If we repeat the action $$$n-1$$$ times we would end up having $$$4^n$$$ squares with size $$$1$$$. After that we can't do any more operations. Of course we don't do this manually — we just substract the number of splitting operations we did on each step from the number $$$k^{'}$$$ (that's the variable that is a copy of variable $$$k$$$ — we will need the value of $$$k$$$ later).
If at some point of the algorithm we have to do more splitting operations than there remains to, then the value of $$$k$$$ is smaller than the maximum number of operations we can apply, thus $$$k$$$ is not too large, so we can just stop checking. If the algorithm successfuly did $$$n-1$$$ iterations and $$$k^{'}$$$ is still greater than $$$0$$$, it means that $$$k$$$ is greater than the maximum number of operations we can apply, so the answer is "NO". It can easily proven that for any $$$n > 30$$$ there are no too large numbers $$$k$$$ for them within the constraints of the task.
Now we know that we can do $$$k$$$ operations, but can we do them in such a way the the condition of Olya's happiness is fuldilled?
Let's imagine that the constraints are not so big and we can emulate the process. We can do it in the following way:
Step 0. We split the only existing square.
Step 1. If we can apply splitting opertation to all of the squares on the path from leftmost bottom point to rigthmost top point with the reamining operations, we should do it and after that we return to Step 1. Otherwise, the size of the squares of which the path consists is equal to the size of the squares the path consits now. Go to Step 2.
Step 2. When we first did Step 1, we left one square of size $$$2^{n-1}$$$ untouched. All the remaining spliiting operations will be used in arbitrary way on it or the squares that appear from it.
Let's prove that with relatively big $$$n$$$ we can always solve the problem with the following algorithm.
If we can build the path from leftmost bottom point to rightmost top point with squares of size $$$2^0$$$ than everything is ok, since the remaining splitting operations can be done (we already checked that the value of $$$k$$$ is not too large).
Otherwise, we can easily see that the number of squares to which you need to apply the splitting operation on each step changes like this: $$$3,7,15, \cdots$$$. It can be proven that the number of splitting operations on the $$$i$$$-th step is equal to:
$$$$$$need_i = 4 * 2^{i-1} - 1$$$$$$
Let's assume that we stopped on $$$x$$$-th iteration of Step 1. It means that the number of splitting operations remaining is less than $$$4 * 2^{x-1} - 1$$$. It also means that we can do at least $$$1 + 4 + 16 + \cdots + 4^{x-1}$$$ operations on the $$$2^{n-1}$$$ square that was left untouched after the first iteration of the algorithm. Let's find the set of such numbers $$$x$$$ that $$$1 + 4 + 16 + \cdots + 4^{x-1}$$$ is greater or equal to $$$4 * 2^{x-1} - 1$$$:
$$$$$$1 + 4 + 16 + \cdots + 4^{x-1} \ge 4 * 2^{x-1} - 1$$$$$$
Since, in numerical system with base $$$4$$$ $$$1 + 4 + 16 + \cdots + 4^{x-1}$$$ can be represented as number with length $$$x+1$$$ that consists only of ones, it follows that:
$$$$$$1 + 4 + 16 + \cdots + 4^{x-1} = \frac{4^{x} - 1}{3}$$$$$$
Now, back to our inequality:
$$$$$$\frac{4^{x} - 1}{3} \ge 4 * 2^{x-1} - 1$$$$$$
$$$$$$4^{x} - 1 \ge 12 * 2^{x-1} - 3$$$$$$ $$$$$$4^{x} \ge 12 * 2^{x-1} - 2$$$$$$
It's obvious that function $$$f_1(x) = 4^{x}$$$ grows faster than $$$f_2(x) = 12 * 2^{x-1} - 2$$$, so once the value of $$$f_1$$$ becomes greater than the value of $$$f_2$$$ it will never beome smaller. For $$$x = 3$$$:
$$$f_1(3) = 4^{3} = 64$$$, $$$f_2(3) = 12 * 2^2 - 2 = 46, f_1(3) > f_2(3)$$$
For $$$x = 2$$$:
$$$f_1(3) = 4^{2} = 16$$$, $$$f_2(3) = 12 * 2^1 - 2 = 22, f_1(2) < f_2(2)$$$
Now we know that the following algorithm always finds solution for all $$$n \ge 3$$$. The rest tests cases can be solved with if's, but still the algorithms works for them. The only exception is test "2 3" — there is no solution for this test, though $$$k$$$ is smaller than the maximum number of splitting operations you can apply.
Like the first part of the solution we shouldn't do the algorthm manually – we can just on each step substract the length of the path from the variable $$$k$$$. (For $$$i$$$-th step it's $$$need_i$$$).
Overall complexity $$$O(logn + logk)$$$.