TAVISUAL - Editorial

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.

2 Likes

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.

19 Likes

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

2 Likes

CodeChef: Practical coding for everyone why am i getting time out?

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

2 Likes