PROBLEM LINKSDIFFICULTYCAKEWALK PREREQUISITESAd Hoc PROBLEMN 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 L^{th} position and ending at R^{th} position, inclusive Output the position of the ball after all the operations. QUICK EXPLANATIONThe 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 EXPLANATIONIf 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 <0LxR> x Step 1: Shift everything to the range [0, RL] This can be performed by subtracting L from all the positions. L R <0(xL)(RL)> 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 <(LR)(Lx)0> x Step 3: Shift back to the range [0, RL] This can be performed by adding RL to all the positions. R L <0(Rx)(RL)> x Step 4: Shift back to the range [L, R] This can be performed by adding L to all the positions. R L <0L(L+Rx)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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 25 Mar '13, 00:10

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 CL = RX => X = L+RC, where X = current swapped position of ball. answered 25 Mar '13, 00:44

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

https://www.codechef.com/viewsolution/16623346 why am i getting time out? answered 22 Dec '17, 15:18
