PROBLEM LINK:
Author: Dmytro Berezin
Tester: Sergey Kulik
Editorialist: Florin Chirica
DIFFICULTY:
simple
PREREQUISITES:
ad hoc
PROBLEM:
You’re given a segment and need to do several steps. One step consist in picking the largest segment which does not contain any point in it and adding a point. What’s the coordinate of the last added point?
QUICK EXPLANATION:
This task is all about patterns: we need to observe that after some steps, all segments have equal length. Then, middle coordinate between two segments of the same length differs by the length of the segments.
EXPLANATION
Spoiler given by the limits
Let’s look at the limits. We see K <= 10^12. In problems like this, it should be a spoiler for finding a pattern. A pattern is best found by taking some examples. So let’s see what happens for X = 10.
In 1st step, there is only one segment, so we pick it.
In 2nd step, that segment is divided in two parts, so there are two segments of equal length.
Then, 3rd and 4rd steps will pick them as two largest. Each of those 2 segments will be divided into 2 smaller segments, so there’ll be 4 segments in total. Also, those 2 segments were equal. Dividing each of them in two equal parts will result 4 equal segments.
From 5th to 8th step we’ll pick previously formed segments. By the same logic, each of the segments will form two more smaller segments. So, we get 8 segments with equal length.
Then, 9th step we pick one of those small new segments.
We can notice a pattern. If x is a power of two plus one (x = 2^k + 1), the size of picked segment after xth step changes (it becomes previous size divided by two).
Let’s find the coordinates now
Suppose we are at kth step, a power of two plus one. What would be the coordinate now? Suppose smallest segment has length len. We know that it starts at 0. So it will be [0, len]. Point is added at len / 2. How about (k+1)-th step? We know segment is [len, 2 * len], so point is added at 3 * len / 2. Next, points are added at 5 * len / 2, 7 * len / 2 and so on.
We can do a simple algorithm from here: first, try to find the length of segment of kth step. How to do this? We can simulate the process. Suppose there are cnt segments of equal length now. If cnt is greater than number of steps left, we’ve fount our length. Otherwise, even after using all cnt segments, we’ll still have steps to do. We can subtract from number of steps left value of cnt, divide length of segments by 2 and multiply cnt by 2 (length of all segments becomes half, but segments become twice).
Now we fount length. More, by doing subtractions we also know how many steps we need to do only with segments of good length. If we have k steps left, then using logic from above coordinate at kth step should be (2 * k - 1) * len / 2.
The complexity of the presented approach is logarithmic.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon
To be updated soon
