ROTATION - Editorial

editorial
, , ,
1

Problem link : Contest Practice

Difficulty : CakeWalk

Pre-requisites : 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 N-K 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+1-th element of the initial array. The second element of this rotated array will be equal to (K+1) mod N+1-th element of the initial array, the third will be equal to the (K+2) mod N+1-th one, and so on (of course, we use 1-indexation in our considerations). So, using this facts one can simply get the M-th 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 M-th element of the current array as A[(R+M-1) 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

1 Like
2

import java.io.BufferedReader;
import java.io.InputStreamReader;

class ROTATION {

public static void main(String[] args) throws Exception{

	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	String input[] = in.readLine().split(" ");
	int n =   Integer.parseInt(input[0],10);
	int m =   Integer.parseInt(input[1],10);
	int arr[] = new int[n];
	input  = in.readLine().split(" ");
	
	for(int i = 0;i<n;i++)		arr[i] =   Integer.parseInt(input[i],10);
	input = null;
	int index=0;
	int tempIndex = 0;
	while(m-->0)
	{
		input  = in.readLine().split(" ");
		char c[] = input[0].toCharArray();
		char a = c[0];
		
		if(a=='C')
		{
			index = index + Integer.parseInt(input[1],10) ;
			if(index>=n) index = index -n;
			
		}
		else if(a=='A')
		{
			index = index - Integer.parseInt(input[1],10) ;
			if(index<0) index = index + n;
		}
		else if(a=='R')
		{
			tempIndex = index;
			tempIndex = tempIndex + Integer.parseInt(input[1],10) -1;
			if(tempIndex>=n) tempIndex = tempIndex-n;
			if(tempIndex<0) tempIndex = tempIndex + n;
			System.out.println(arr[tempIndex]);
		}
		
	}

}

}

3

where I’m getting Wrong in this answer :\

#include<stdio.h>
int main()
{
    int n,m,i,start=1,inp,index;
    char ch[1];
    static int a[100001];
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=m;i++)
    {
            scanf("%s %d",&ch,&inp);
            if(ch[0]=='C')
            {
                start=(start+inp);
                if(start>n)
                    start-=n;
            }
            else if(ch[0]=='A')
            {
                start=(start-inp);
                if(start<1)
                    start+=n;
            }
            else
            {
                index=start+inp-1;
                if(index>n)
                    index-=n;
                if(index<1)
                    index+=n;
                printf("%d\n",a[index]);
            }
    }
    return 0;
}
4

Hi ,

Could you let me know what is wrong.

My code is shown below

#include
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");

        }
        else if ( operation == 'A')
        {
			j = 1;
              for ( int i =1;i<unit;i++)
              {
                    A[(N-(unit-i))+1] = B[i];
              }
			  for ( int i=unit;i<=N;i++)
			  {
				  A[j] = B[i];
				  j++;
			  }
			  for ( int i =1;i<=N;i++)
              {
                    B[i] = A[i];
					printf("%d ",B[i]);
              }
			  printf("\n");

        }
  }
  return 0;

}

5

if(index>n)
index-=n;
But what if index=11 and n=5, then index=11-5=6, which is still greater. So instead use % operator, index=11%5=1,the correct ans. Hope this will help.

6

if(tempIndex>=n) tempIndex = tempIndex-n;
what is tempindex=11, and n=5, tempIndex=11-5=6, which is not a valid array index in this situation… Hope this will help, and happy coding.

7

You should use indexing with 0, since there are some mod(%) operation and index%n=0, if index==n.

8

#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…

1 Like
9

WOW! Got to know an interesting fact while looking for this problem!

In python: -32%5 = 3

and in c/c++: -32%5 = -2