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

×

CAKEWALK

# PROBLEM

N cups are arranged in a line. There is a ball under one of the cups. You know initially which cup it was under.

Several operations of the following type are performed

Flip the order of the cups starting from Lth position and ending at Rth position, inclusive

Output the position of the ball after all the operations.

# QUICK EXPLANATION

The cups are numbered 1 to N from left to right. For some given L and R, if the ball is currently at position x, such that

L ≤ x ≤ R

Then the new position of the ball is going to be

L + R - x

We will see why this is so below. The problem can thus be solved by the following snippet of code

Let x be the initial position of the ball

for each operation [L, R]
if L ≤ x ≤ R
x = L + R - x


# EXPLANATION

If x lies between L and R, let us derive the expression for the new position of x.

For this, we will imagine that we have a number line and each one of L, R and x are points on this number line. We will mark these points as 'L', 'R' and 'x' respectively.

                   L            R
<----------0-------L--------x---R--------------->
x


Step 1: Shift everything to the range [0, R-L]

This can be performed by subtracting L from all the positions.

           L                 R
<----------0--------(x-L)---(R-L)--------------->
x


Step 2: Flip all positions to the range [-R+L, 0]

This can be performed by multiplying all the positions with -1.

             R                   L
<-----------(L-R)---(L-x)--------0-------------->
x


Step 3: Shift back to the range [0, R-L]

This can be performed by adding R-L to all the positions.

           R                 L
<----------0--------(R-x)---(R-L)--------------->
x


Step 4: Shift back to the range [L, R]

This can be performed by adding L to all the positions.

                   R                  L
<----------0-------L--------(L+R-x)---R--------->
x


Hence, we can solve the problem by finding the new position after each operation. Note that we do not need to perform any change if x does not fall within the boundaries of an operation.

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 25 Mar '13, 00:10 2.4k128183169
accept rate: 14%

 12 In one liner if current position of ball falls under L and R then absolute distance between C and R after swapping will be equal to absolute distance between L and C before swapping. i.e C-L = R-X => X = L+R-C, where X = current swapped position of ball. answered 25 Mar '13, 00:44 5.7k●26●68●68 accept rate: 17%
 1 Although this problem is very simple, I think in the diagrams L and R should consistently label their original cup. (i.e. in the end they should be reversed). answered 25 Mar '13, 04:36 3★chrono 16●1 accept rate: 0% 1 Good suggestion. I was busy the last two days. Have made the change now :) (26 Mar '13, 17:06)
 0 https://www.codechef.com/viewsolution/16623346 why am i getting time out? answered 22 Dec '17, 15:18 14●4 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×1,688
×968
×12

question asked: 25 Mar '13, 00:10

question was seen: 4,455 times

last updated: 22 Dec '17, 15:18