CodeChef Matrix Rotation

Question

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(' ')[0];
 string m = nm.Split(' ')[1];
 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(' ')[0]);
 int distance = int.Parse(optionanddistance.Split(' ')[1]);
 if (option == 'C')
 {
 ArrayList tempAL = new ArrayList();
 tempAL.AddRange(arr);
 tempAL.CopyTo(distance, arr, 0, arr.Length - distance);
 tempAL.CopyTo(0, arr, arr.Length - distance, distance); 
 }
 if (option == 'A')
 {
 ArrayList tempAL = new ArrayList();
 tempAL.AddRange(arr);
 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?

• Martin R: Here is a question about solving the same challenge in Java: "Fun with Rotation" - Codechef September Challenge. The general idea of 200_success' answer can be applied here as well.
• Tigga: @Martin R Is there any Tweaks that can be done in this Program? So as to improve its performance?
• Martin R: Here is the source of the challenge (which runs until Sep 15) codechef.com/SEPT14/problems/ROTATION.

Answer 1

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

Answer 2

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.

Answer 3

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.

• Tigga: I have already stored the array as strings
• user33306: 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.