Problem link : Contest Practice Difficulty : CakeWalk Prerequisites : basic language data structures Solution: At first, let's note that if we rotate the array by K units anticlockwise, it's the same as the rotation by NK units clockwise. So, from now on, we will consider only clockwise rotations. In case we have any anticlockwise rotation query, it can be reduced to the clockwise one. When we rotate the array by K units anticlockwise, its' first element becomes equal to the K mod N+1th element of the initial array. The second element of this rotated array will be equal to (K+1) mod N+1th element of the initial array, the third will be equal to the (K+2) mod N+1th one, and so on (of course, we use 1indexation in our considerations). So, using this facts one can simply get the Mth element of the array after a rotation. What happens when we have several rotations? One can note that the rotations are "additive", so we only need to maintain is the current "shift" variable that points to the first element of the current array after all the rotations. If this "shift" variable equals to R before some clockwise turn, it will be equal to (R+K) mod N after this turn. Basically, like it is described in the previous paragraph, we can get the Mth element of the current array as A[(R+M1) mod N], where A is the array that was given initially. In this solution we don't actually rotate the array, we only operate with out "shift" variable (R above). So each operation is performed in O(1) time, so we get the total complexity of O(N+Q) where N is the size of the array and Q is the number of queries. Setter's solution: link Tester's solution: link
This question is marked "community wiki".
asked 15 Sep '14, 15:44

WOW! Got to know an interesting fact while looking for this problem! In python: 32%5 = 3and in c/c++: 32%5 = 2answered 29 Oct '17, 02:45

import java.io.BufferedReader; import java.io.InputStreamReader; class ROTATION {
} answered 15 Sep '14, 17:20
if(tempIndex>=n) tempIndex = tempIndexn; what is tempindex=11, and n=5, tempIndex=115=6, which is not a valid array index in this situation... Hope this will help, and happy coding.
(07 Oct '14, 09:48)

Hi , Could you let me know what is wrong. My code is shown below include <iostream>using namespace std; int main() { int M, N; int A[100001]; int B[100001]; char operation; int unit; scanf("%d %d",&N, &M); int j; for ( int i = 1; i<= N; i++) { scanf("%d", &A[i]); B[i] = A[i]; } for ( int k = 0; k<M; k++) { fflush(stdin); scanf("%c %d",&operation, &unit); if ( operation == 'R') { printf("%d\n",A[unit]); } else if ( operation == 'C') { j = 1; //A[0] = A[unit]; for ( int i = unit+1; i<=N; i++) { A[j] = B[i]; j++; } for ( int i = 1; i<=unit; i++) { A[j] = B[i]; j++; } for ( int i =1;i<=N;i++) { B[i] = A[i]; printf("%d ",B[i]); } printf("\n");
} answered 16 Sep '14, 14:40
2
k1ps .your solution is not working even for sample test case....for more info refer editorial and my solution....link http://www.codechef.com/viewsolution/7069096.....
(03 Jun '15, 10:22)
