You are not logged in. Please login at www.codechef.com to post your questions!

×

ROTATION - Editorial

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

This question is marked "community wiki".

asked 15 Sep '14, 15:44

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 15 Sep '14, 15:46

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581


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; }

link

answered 15 Sep '14, 21:14

rajarshi369's gravatar image

2★rajarshi369
25269
accept rate: 0%

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.

(07 Oct '14, 09:43) mskanyal2★

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

(07 Oct '14, 10:16) mskanyal2★

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

In python: -32%5 = 3

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

link

answered 29 Oct '17, 02:45

light_of_orion's gravatar image

1★light_of_orion
202
accept rate: 0%

edited 29 Oct '17, 02:47

-1

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]);
        }

    }

}

}

link

answered 15 Sep '14, 17:20

ankurjain727's gravatar image

2★ankurjain727
0
accept rate: 0%

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.

(07 Oct '14, 09:48) mskanyal2★
-3

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

        }
        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;

}

link

answered 16 Sep '14, 14:40

k1ps's gravatar image

2★k1ps
-2
accept rate: 0%

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) rcsldav20175★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×1,646
×935
×61

question asked: 15 Sep '14, 15:44

question was seen: 4,947 times

last updated: 29 Oct '17, 02:47