PROBLEM LINKS
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.
