You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 17 Nov '14, 18:57

elfus's gravatar image

3★elfus ♦♦
0112527
accept rate: 0%

edited 18 Nov '14, 17:57

admin's gravatar image

0★admin ♦♦
19.8k350498541

unable to find this problem on practice page!!!

(26 Nov '14, 22:40) grvana1★
1
(26 Nov '14, 23:00) achaitanyasai5★

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

(28 Nov '14, 09:35) grvana1★

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 2 . Using library function
IMO execution time for left-shift should be less but it's not.

link

answered 17 Nov '14, 20:24

sonunitw's gravatar image

3★sonunitw
11
accept rate: 0%

edited 17 Nov '14, 20:37

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

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

link

answered 20 Nov '14, 11:44

mkkhedawat's gravatar image

2★mkkhedawat
233
accept rate: 0%

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

link

answered 21 Nov '14, 09:56

bicepjai's gravatar image

2★bicepjai
11
accept rate: 0%

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: code

link

answered 21 Oct '17, 16:17

bhagirathi08's gravatar image

3★bhagirathi08
01
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,173
×952
×179

question asked: 17 Nov '14, 18:57

question was seen: 3,448 times

last updated: 21 Oct '17, 16:17