CHEFSEG - Editorial

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

1 Like

I have used same method. In first method left-shift is used to find k and in 2nd method library function is used like log , floor , pow .can some body explain why execution time is almost same in the both cases?
1 .[Using left shift ][1]
2 . [Using library function][2]

IMO execution time for left-shift should be less but it’s not.
[1]: http://www.codechef.com/viewsolution/5390260
[2]: http://www.codechef.com/viewsolution/5317017

1 Like

I am getting wrong answer in Third Task every time :frowning:

Can Anybody please tell , What is wrong with this :
http://www.codechef.com/viewsolution/5390669

I have tried using long double here but still no help :
http://www.codechef.com/viewsolution/5439428

1 Like

what might be wrong, fails for subtask 3
http://www.codechef.com/viewsolution/5441582

unable to find this problem on practice page!!!

@grvana This is the link : http://www.codechef.com/problems/CHEFSEG

1 Like

@achaitanyasai allright may be this is not the right question to ask but why it is not being shown in the problems easy part ??

Hi All,An O(1) time approach ,I have used the idea that at Kth cut (where K is of the form 2^P -1) divides the given interval into equal segments.Then, given an X I found the last cut which evenly divides the segment and then after that I am making the remaining cuts till the last one.

Here is my Solution:


[1]


  [1]: https://www.codechef.com/viewsolution/15911546