Common Number
Contest: Codeforces Round 608 (Div. 2)
Difficulty rating: 2100
Tags: binary search, combinatorics, dp, math

At first, let's define function $$$f(x)$$$ as follows: $$$$$$ \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix} $$$$$$

We can see that if we choose some value $$$v$$$ and will apply function $$$f$$$ to it, then apply $$$f$$$ to $$$f(v)$$$, and so on, we'll eventually get $$$1$$$. Let's write down all values we get in this process in a list and denote this list as $$$path(v)$$$. For example, $$$path(1) = [1]$$$, $$$path(15) = [15, 14, 7, 6, 3, 2, 1]$$$, $$$path(32) = [32, 16, 8, 4, 2, 1]$$$.

Let's write all lists $$$path(x)$$$ for every $$$x$$$ from $$$1$$$ to $$$n$$$. The question is next: what is the maximum value $$$y$$$ such that $$$y$$$ is contained in at least $$$k$$$ different lists $$$path(x)$$$?

Formally speaking, you need to find maximum $$$y$$$ such that $$$\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$).

Output format:
Print the only integer — the maximum value that is contained in at least $$$k$$$ paths.

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

Note:
In the first example, the answer is $$$5$$$, since $$$5$$$ occurs in $$$path(5)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the second example, the answer is $$$4$$$, since $$$4$$$ occurs in $$$path(4)$$$, $$$path(5)$$$, $$$path(8)$$$, $$$path(9)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the third example $$$n = k$$$, so the answer is $$$1$$$, since $$$1$$$ is the only number occuring in all paths for integers from $$$1$$$ to $$$20$$$.

Example input:
11 3

Example output:
5

Example input:
11 6

Example output:
4

Editorial:
Let's introduce a function $$$count(x)$$$ — the number of $$$y \in [1, n]$$$ such that $$$x \in path(y)$$$. The problem is now to find the greatest number $$$x$$$ such that $$$count(x) \ge k$$$.
How can we calculate $$$count(x)$$$? First, let's consider the case when $$$x$$$ is odd. $$$x$$$ is contained in $$$path(x)$$$; then $$$x$$$ is contained in $$$path(2x)$$$ (since $$$\frac{2x}{2} = x$$$) and in $$$path(2x + 1)$$$ (since $$$2x + 1$$$ is odd, $$$f(2x + 1) = 2x$$$). The next numbers containing $$$x$$$ in their paths are $$$4x$$$, $$$4x + 1$$$, $$$4x + 2$$$ and $$$4x + 3$$$, then $$$8x$$$, $$$8x + 1$$$, ..., $$$8x + 7$$$, and so on. By processing each segment of numbers containing $$$x$$$ in their paths in $$$O(1)$$$, we can calculate $$$count(x)$$$ for odd $$$x$$$ in $$$O(\log n)$$$.
What about even $$$x$$$? The first numbers containing $$$x$$$ in their paths are $$$x$$$ and $$$x + 1$$$, then $$$2x$$$, $$$2x + 1$$$, $$$2x + 2$$$ and $$$2x + 3$$$, then $$$4x$$$, $$$4x + 1$$$, ..., $$$4x + 7$$$, and so on. So the case with even $$$x$$$ can also be solved in $$$O(\log n)$$$.
We can also see that $$$count(x) \ge count(x + 2)$$$ simply because for each number containing $$$x + 2$$$ in its path, there is another number that is less than it which contains $$$x$$$ in its path. And this fact means that if we want to find the greatest $$$x$$$ such that $$$count(x) \ge k$$$, we only have to run two binary searches: one binary search over odd numbers, and another binary search over even numbers.