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?

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.