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

×

TAVISUAL - Editorial

2
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Ad Hoc

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

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 26 Mar '13, 17:06


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.

link

answered 25 Mar '13, 00:44

bit_cracker007's gravatar image

3★bit_cracker007
5.7k266868
accept rate: 17%

edited 25 Mar '13, 00:50

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).

link

answered 25 Mar '13, 04:36

chrono's gravatar image

3★chrono
161
accept rate: 0%

1

Good suggestion. I was busy the last two days. Have made the change now :)

(26 Mar '13, 17:06) gamabunta1★
link

answered 22 Dec '17, 15:18

llgokull_007's gravatar image

2★llgokull_007
144
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:

×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