CodeChef Matrix Rotation

I am new to C# and have tried to solve a problem statement from CodeChef:

Problem statement

You are given an array A of N integers. You are to fulfill M queries. Each query has one of the following three types:

• C d : Rotate the array A clockwise by d units.
• A d : Rotate the array A anticlockwise by d units.
• R d : Query for the value of the element, currently being the d-th in the array A.

Input

The first line contains two numbers - N and M respectively.

The next line contains N space separated Integers, denoting the array A.

Each of the following M lines contains a query in the one of the forms described above.

Output

For each query of type R output the answer on a separate line.

Constraints

• $1 \le N \le 100000$
• $1 \le M \le 100000$
• $1 \le d \le N$, in all the queries
• $1 \le$ elements of A $\le 1000000$

The array A and the queries of the type R are 1-based.

Example

Input:

5 5
5 4 3 3 9
R 1
C 4
R 5
A 3
R 2

Output:

5
3
3

My Code:

using System;
using System.Collections;
using System.Text;

namespace RotationSeptChallenge
{

class Program
{
public static void Main(string[] args)
{

string nm = Console.ReadLine();
string n = nm.Split(' ');
string m = nm.Split(' ');
int loopvar = int.Parse(m);
string[] arr = new string[int.Parse(n)];
var temp = Console.ReadLine().Split(' ');
for (int i = 0; i < temp.Length; i++)
{
arr[i] = temp[i];
}
for (int loop = 0; loop < loopvar; loop++)
{
var optionanddistance = Console.ReadLine();
char option = char.Parse(optionanddistance.Split(' '));
int distance = int.Parse(optionanddistance.Split(' '));

if (option == 'C')
{
ArrayList tempAL = new ArrayList();
tempAL.CopyTo(distance, arr, 0, arr.Length - distance);
tempAL.CopyTo(0, arr, arr.Length - distance, distance);
}

if (option == 'A')
{
ArrayList tempAL = new ArrayList();
tempAL.CopyTo(arr.Length - distance,arr,0,distance);
tempAL.CopyTo(0,arr,distance,arr.Length - distance);
}

if (option == 'R')
{
Console.WriteLine(arr[distance - 1]);
}

}

}
}
}

My solution seems to be right when I tried with a few sample outputs. However, Time Limit Exceeded was the result of my Submission. The time Limit is set to 1 sec and my solution takes >1sec. What seems to be the problem? How can I optimize this code to perform better?

You don't need all that copying and rearranging, all you need is to keep a pointer to where array starts and adjust your index calculation based on that. Suppose you have an array of integers: [0, 1, 2, 3, 4], current start index is 0. If you rotate 2 to the left, your start index becomes 3: [2, 3, 4, 0, 1]. If you rotate this to the right 4 times, your start index is changed to 2. You can see a pattern here: moving n cells to the left decreases start index by n and moving right increases start index.

Here's a sample pseudo-code:

startIndex = 0;
foreach operation
if operation is print
transformedIndex = operation.index - startIndex
if(transformedIndex < 0)
transformedIndex += inputArray.length
print inputArray[transformedIndex]

else
if operation is rotate left
startIndex -= operation.index
else
startIndex += operation.index
startIndex = startIndex mod inputArray.length
if startIndex < 0
startIndex += input.Length

Never use ArrayList, it's not type-safe.

If you need a resizable collection, use List<T> with the appropriate T (e.g. List<string>).

But if all you want is to copy the array, you can use ToArray() from LINQ.

Anyway, any performance tweaks to your code most likely won't affect the performance significantly. What you need is a completely different approach, as Martin R suggested.

A few things I noticed:

1. When you're splitting the input line, put it into into an array and use those values instead of splitting it twice.
2. Don't convert the input array to integers keep them as strings.
• I have already stored the array as strings – Tigga Sep 10 '14 at 7:35
• Sorry I didn't look at that loop close enough. The point still stands though. You're copying the strings to another array which is not needed. – tinstaafl Sep 10 '14 at 21:38