Karen and Neighborhood
Contest: Codeforces Round 419 (Div. 1)
Difficulty rating: 2900
Tags: binary search, constructive algorithms, implementation

It's been long after the events of the previous problems, and Karen has now moved on from student life and is looking to relocate to a new neighborhood.

The neighborhood consists of n houses in a straight line, labelled 1 to n from left to right, all an equal distance apart.

Everyone in this neighborhood loves peace and quiet. Because of this, whenever a new person moves into the neighborhood, he or she always chooses the house whose minimum distance to any occupied house is maximized. If there are multiple houses with the maximum possible minimum distance, he or she chooses the leftmost one.

Note that the first person to arrive always moves into house 1.

Karen is the k-th person to enter this neighborhood. If everyone, including herself, follows this rule, which house will she move into?

Input format:
The first and only line of input contains two integers, n and k (1 ≤ k ≤ n ≤ 1018), describing the number of houses in the neighborhood, and that Karen was the k-th person to move in, respectively.

Output format:
Output a single integer on a line by itself, the label of the house Karen will move into.

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

Note:
In the first test case, there are 6 houses in the neighborhood, and Karen is the fourth person to move in:

1. The first person moves into house 1.
2. The second person moves into house 6.
3. The third person moves into house 3.
4. The fourth person moves into house 2.

In the second test case, there are 39 houses in the neighborhood, and Karen is the third person to move in:

1. The first person moves into house 1.
2. The second person moves into house 39.
3. The third person moves into house 20.

Example input:
6 4

Example output:
2

Example input:
39 3

Example output:
20

Editorial:
Surprisingly, it is possible to solve this problem without knowledge of any sophisticated algorithms or data structures; this problem can be solved completely through observations, brutal case analysis and grunt work, which we will try to summarize here.
The first and most obvious observation: the first person always goes to house 1, and the second person always goes to house n. Consider these two guys as special cases; now, we're solving the problem on a segment of length n - 2.
Note how we define segments here; a segment of length l is a row of l unoccupied houses, with the two houses just before and after both endpoints occupied.
Notice that, for any segment, if a person moves into any house in this segment it will be the middle one; if there are two middles, it will be the left of the two middles. So, if we have a length 3 segment, the person will move into the 2-nd house in the segment. If we have a length 6 segment, the person will move into the 3-rd house in the segment, and so on.
When a person moves into a house in a given segment of length l, if l > 2, it will also create two new segments; the left segment will be length $$\left\lfloor \frac{l-1}{2} \right\rfloor$$ and the right segment will be length $$\left\lfloor \frac { 7 } { 2 } \right\rfloor$$.
Let's write down the segments in a binary tree, where the i-th layer contains all segments spawned by the (i - 1)-th layer, and the first layer contains precisely the segment of length n - 2.
For example, consider n = 46. The binary tree will look like this:
From this, we can make a number of observations.
We can see that there are at most 2 different segment lengths in any layer. Additionally, these values are always l and l + 1, where l is the smaller one.
Let the two lengths in a given layer be l and l + 1 (if there is only one, it's just l). Now, consider the following:
• If l is odd, the segments of length l and l + 1 will be processed in order from left to right.
• If l is even, all segments of length l + 1 will be processed first, from left to right, then all segments of length l will be processed, also from left to right.
This makes sense; the "minimum distance" is actually just the smaller of the two children, and you can observe that in the above first case, the smaller of the two children is equal, while in the second case, the smaller of the two children of l is smaller than the smaller of the two children of l + 1.
Additionally, all segments in any particular layer are always processed before the segments in the next layer (except in the case l = 2—we will discuss the special cases later.) We can therefore determine, rather straightforwardly, what layer the k-th segment is. Since all the layers above this layer are now irrelevant, we can just subtract all the taken layers from k. Now, the problem has been reduced to finding what house the k-th guy in a fixed layer moves into.
How will we find this? Well, note that there is exactly one house separating any two segments in a given layer. If we go to the k-th segment, the label of the house we actually went into is k (number of houses occupied on previous layers), plus the total length of segments 1, 2, 3, ..., k - 1 (unoccupied houses before this one), plus $$\left\lfloor \frac{k+1}{2} \right\rfloor$$ (the middle house in the k-th segment).
It is easy to determine l and the number of length l and length l + 1 segments for any particular layer. What's harder to compute are two crucial details:
1. What's the relative position of the k-th processed segment in this layer?
2. How many layers have length l + 1 before the segment at this relative position?
If we can answer these two questions efficiently, we are basically done with the core of the solution, and just have to handle special cases.
Let's answer the first question. If l is odd, this is trivial; the k-th processed segment is precisely that at position k.
If l is even, things get a lot trickier. Luckily, we can perform more observations. Draw the tree with root segment 39 (n = 41), and observe the fourth row. Now, draw the trees with root segments 40, 41, 42, ..., 47.
Observe how the fourth row changes from root segment 39 to 47:
• Root segment is 39: 4, 4, 4, 4, 4, 4, 4, 4
• Root segment is 40: 4, 4, 4, 4, 4, 4, 4, 5
• Root segment is 41: 4, 4, 4, 5, 4, 4, 4, 5
• Root segment is 42: 4, 4, 4, 5, 4, 5, 4, 5
• Root segment is 43: 4, 5, 4, 5, 4, 5, 4, 5
• Root segment is 44: 4, 5, 4, 5, 4, 5, 5, 5
• Root segment is 45: 4, 5, 5, 5, 4, 5, 5, 5
• Root segment is 46: 4, 5, 5, 5, 5, 5, 5, 5
• Root segment is 47: 5, 5, 5, 5, 5, 5, 5, 5
In what order are the numbers increased? It's not immediately obvious, but we can try to write down the binary representations of the (zero-indexed) positions in the order they are increased:
• 7: 111
• 3: 011
• 5: 101
• 1: 001
• 6: 110
• 2: 010
• 4: 100
• 0: 000
Actually, this is just the reversed binary numbers in reverse order! Remember that our goal is to find the relative position of the k-th processed element. Without loss of generality, suppose that the k-th processed element is of length l + 1 (the analysis when it is length l is almost the same.)
This is equivalent to asking for the k-th smallest element among the first m numbers in that list (m is the number of l + 1 segments in the given layer, which is easy to compute).
Let's take root segment equal to 44, as in the illustration earlier. Let's say we want the position of the k = 4-th occurrence of 5. That's equivalent to finding the 4-th smallest element in this list (obviously we never get to generate this list explicitly):
• 7: 111
• 3: 011
• 5: 101
• 1: 001
• 6: 110
Consider these binary numbers digit by digit starting from the largest. Notice that, at any point, the number of ones is always equal to or one more than the number of zeroes; above, there are 3 ones and 2 zeroes.
We want the 4-th smallest, and there are only 2 zeroes, so we know it has to start with 1. We throw out (again, not explicitly) all the numbers that start with zero, and we are now left with finding the 2-nd smallest in this list:
Our number so far: 1??
• 7: 11
• 5: 01
• 6: 10
Now, there are 2 ones and 1 zero. We want the 2-nd smallest, and there is only 1 zero, so we know the next digit is 1. We throw out all the numbers that start with zero, and we are now left with finding the 1-st smallest in this list:
Our number so far: 11?
• 7: 1
• 6: 0
Now, there is 1 one and 1 zero. We want the 1-st smallest, and there is 1 zero, which is enough. So, this is the next digit. The final number is 6, which means that the position of the 4-th 5 is at 6. (7 if one-indexed).
This process works for any arbitrary numbers in $${\mathcal {O}}(\log n)$$, and now we are able to answer the first required question in just $${\mathcal {O}}(\log n)$$ time.
Now, we need to answer the second question. How many layers have length l + 1 before the segment at this relative position?
Actually, this question can be solved using almost the exact same binary digit analysis! The problem is equivalent to asking for how many numbers, among the first m numbers in the earlier list, have a position less than k. We will omit the analysis here for brevity, but it uses virtually the same idea and also solves this question in $${\mathcal {O}}(\log n)$$.
Now, we have solved both questions, and have essentially finished the core of the problem. But we're not yet done! We still have to handle the corner cases.
There are actually only two corner cases: l = 1 and l = 2.
When l = 1, note that every segment of length 2 is basically treated as two segments of length 1.
When l = 2, segments of length 3 are handled first, each creating segments of length 1. Then, the segments of length 1 and 2 are treated like with l = 1, despite the segments of length 1 technically being on the next layer.
Both of these cases can be solved using the same binary digit analysis, with some grunt-work formulas that can be a bit hard to get precisely correct. These cases can also be solved in $${\mathcal {O}}(\log n)$$.
Overall, the runtime of the solution is just $${\mathcal {O}}(\log n)$$.