Even Tree [HackerRank]

Hi all, I’m sorry about not posting very frequently – thankfully, however, my exams will be coming to a close in the next two weeks, so I will be able to return to regular posting soon.

If you are unfamiliar with graph theory, I recommend that you read my previous post on the subject – it gives an introduction into the topic and the ways in which it appears in competitive programming.

Today, we will solve a relatively simple problem on graph theory which can be found on the ‘HackerRank’ website – given a tree (a graph with no cycles and where any node can be reached from any other node) of N nodes numbered from 1 (which is the root node) to N, our program must find the maximum number of edges it can remove from this tree to obtain a set of trees (commonly called a ‘forest’) where every tree has an even number of nodes.

The source code of my final solution to this problem can be found here.

The problem statement states that it is always possible to remove edges from the main tree to create a forest consisting of only trees with even numbers of nodes, so we do not need to concern ourselves with difficult edge cases. This brings us to a relatively simple solution: any ‘subtree’ (a smaller tree which is part of the main tree – it may have its own root separate from the main root) with an even number of nodes can be separated from the node connecting to its root – therefore, the maximum number of edges which can be removed from the tree to satisfy the problem statement is equal to the number of subtrees with even numbers of nodes. We have now reduced the problem to counting the number of nodes in each subtree.

Our first course of action is to devise a method for storing the tree – the technique I used is known as an ‘adjacency list’. In C++, this is essentially a vector where each element represents a node. For simple graphs like the ones used in this problem, each node can be represented by a vector of integers, with each integer representing a node which can be reached from the node represented by the vector itself. Initially our adjacency list will be empty, however, we will fill it by taking each edge from input as two integers (which represent the two nodes connected by the edge in question) connecting the deeper of the two nodes to the node closer to the root (not vice-versa! The edges in our list only need to be unidirectional).

EvenTree1.png

After creating the adjacency list, we can write a function which performs a depth-first traversal of the tree, counting the number of nodes in each subtree by travelling to each node in turn and counting the number of children it has and adding 1 to this value (this addition represents the current node, which acts as the root). We can do this elegantly using recursion – the numbers of nodes in the subtrees rooted at the deepest points of the tree are always 1 (as these nodes have no child nodes). By this logic, we can have our recurring function return 1 when it reaches a node with no child nodes, and in order to calculate the numbers of nodes in the other subtrees, we recur for every child node of each potential root node and save the sum of the results.

EvenTree2.png

Once we have calculated the number of nodes in every possible subtree of the main tree, we can just iterate through our results and increment our final answer by 1 every time we find a subtree with an even number of nodes. Once this process is complete, we can print out our final value.

EvenTree3.png

The Coin Change Problem Solved with Dynamic Programming

The ‘Coin Change Problem’ is a well-known exercise in computer science. The idea is simple – given a certain number amount of money in cents (we will call this amount n), and infinite numbers of defined coin denominations, we want to calculate the number of ways we can make n by combining the coins we have been given.

For example, if we want to make 4 cents (n = 4), and the denominations available to us are 1, 2 and 3, we could make 4 cents in the following four ways:

{2,2}, {1,1,1,1}, {1,3}, {1,1,2}

Another example – if we want to make 10 cents (n = 10), and the denominations available to us are 2, 3, 5 and 6, we could make 10 cents in the following five ways:

{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}, {5,5}

The code I have written which solves the Coin Change Problem can be found here.

The most effective solution design for this problem uses a technique known as dynamic programming (we can also develop a program that finds solutions by brute force, but this is incredibly slow). The key idea to this technique is that certain large problems (say, finding the number of ways to make a large number of cents from a wide variety of different coin denominations) can be broken down into smaller sub-problems. These sub-problems can then be broken down further, until very small, easily-solvable problems with optimal solutions are obtained. From this logic, problems of this nature can be tackled by finding and solving the most trivial sub-problems, and extending the solutions to these sub-problems to more complex sub-problems until the final solution is obtained.

To apply dynamic programming to the Coin Change Problem, we first need to observe that there is only 1 way of making a sum of 0 (no matter what denominations we have available to us). Moreover, if we only have access to 1 coin denomination, then it is clear that there can be no more than 1 possible way to make every single sum (if a given number is divisible by the denomination, then there is 1 way to make that number, and if the number is not divisible by the denomination, then there is no possible way to make that number).

The next observation we can make is that we can represent the problem as a table – with a row for each coin denomination and (n+1) columns. The numbers in a given column represent the number of ways the index value of the column can be made using the coin denominations from each number’s row and the rows above. To solve the problem, we need to find the value at the bottom right of this table. We already know that there is only 1 way of making a sum of 0, so the first column can be filled with ones. Additionally, we have also already proven that there can be a maximum of 1 way of making every possible sum using only one coin denomination – therefore, the first row can be filled with either ones (for the columns with indices which are divisible by the first coin denomination) or zeroes (for the columns with indices which are not divisible by the first coin denomination).

After filling in the first column and the first row, we can progress onto filling the rest of the table, row-by-row. When we fill the second row of the table, we find the number of ways to make each column index using the first two coin denominations available to us. If the second coin denomination is greater than a given column index, we can set the value of the cell to the corresponding cell value in the row above (because the second coin denomination has no effect on the number of ways we can make the sum, since it has a greater value). However, if the second coin denomination is equal to or less than a given column index, we need to look at the number of ways we can include the second coin denomination in the sum. If the second coin denomination is equal to the sum, then we can set the value of the cell to the value of the corresponding value in the cell above incremented by 1 (since one new possible way of making the sum has been found – a single coin of the denomination equal to the target). Furthermore, if the second coin denomination is of a smaller value than the sum, we need to find the number of ways we can group the coins of the first two denominations together such that they sum to the difference between the sum and the second coin denomination. The key insight here is that we have already calculated this value previously (since we are iterating through the columns from left-to-right, with smaller sums being positioned towards the left). Therefore, we can set the value of our current cell to the sum of the value of the corresponding cell in the row above added to the value of the cell in the current row in the column indexed by the difference between the value of the current column and the value of the second coin denomination. This set of operations can be repeated for every single row in order to generate a full table. We can express this algorithm in a more concise form below (note that since every value in the first column is 1, we do not need to program any additional functionality for when the values of a given combination and the desired sum are equal):

  • For every row r:
    • Save the value of the coin denomination represented by the current row as v.
    • If r is the first row in the table:
      • For every column c:
        • If the index of c is evenly divisible by v:
          • Set table[r][c] to 1.
        • Else:
          • Set table[r][c] to 0.
    • Else
      • For every column c:
        • If v > column index:
          • Set table[r][c] to table[r-1][c].
        • Else if <= column index:
          • Set table[r][c] to (table[r-1][c] + table[r][cv]

 

When this algorithm is used to solve our first example (where we attempt to make 4 cents using coins with the denominations for 1, 2 and 3), the following table is generated:

CoinChangeTable.png

We can see that the value of table[2][2] is set to (table [1][2] + table[2][0]). This shows that it is possible to make a sum of 2 cents using two 1-cent coins, or one 2-cent coin. This algorithm is repeated to construct the whole table, resulting in the value of table[3][4] being set to (table[2][4] + table[3][1]). The final value for table[3][4] shows that there are 3 possible ways to use only 1-cent coins and 2-cent coins to create a sum of 4, along with another single possible way which includes a 3-cent coin (resulting in the coin set {3,1}).

 

Enumerating Boolean Sets Using Bit Arrays

Certain problems in computer science call for the complete search of all of the possible permutations of a set of Boolean values. For example, consider a set of x counters, from which we can ‘take’ any combination of counters, and leave the rest – that is, any given counter in the set containing x of them can be either ‘taken’ or left behind. Each of these counters could have a certain numeric ‘value’, and our program is tasked with finding all of the combinations of taken counters whose values sum up to a certain target number (which we will call s).

blogpiccounters

Obviously, there are same fairly elegant methods which can be used to do this efficiently, however, for the purpose of this post, we will focus on the ‘naive’ method.

We have already observed that each counter can either be taken or left – expanding on this idea, we can say that each counter has one of two states. Remember that a bit also only has one of two possible values (either 0 or 1). Additionally, binary numbers (numbers in base 2) also only contain digits with values of either 0 or 1 – notice that as we count up from 0 to 3 (note that this is 2^2 – 1) in binary, we enumerate all possible combinations of the bit values in a set of 2 bits.

Binary (Base 2)  |  Denary (Base 10)

00                               0

01                                1

10                                2

11                                 3

This is a pattern that is repeated for all positive powers of 2 – counting up to 2^2 – 1 in binary will give all of the possible combinations of bit values in a set of 2 bits, and counting up to 2^3-1 in binary will give all of the possible combinations of bit values in a set of 3 bits, and so forth. To generalise the idea:

Counting up to 2^n-1 in base 2 (binary) gives all of the possible combinations of bit values in a set of n bits.

Given that a bit can only have a value of either 0 or 1, we can use the value of a given bit to represent a yes/no decision. Therefore, in our original problem dealing with counters, we could describe a set of chosen counters by using an array of bits where a single bit with a value of 0 denotes a counter which has not been chosen, while a bit with a value of 1 denotes a counter a counter which has been chosen. This array of bits would have a length of x, as each individual bit represents an individual counter.  Furthermore, we can then obtain all of the possible combinations of chosen bits by counting up to 2^x-1 in base 2, and parse through every resulting binary number in turn to find the sum of the chosen counter scores in each combination, and print the selections which have a sum of s.

Obviously, given that this technique is a complete search of a full range, we can come to the conclusion that it is highly inefficient. The time complexity of the algorithm creating the bit arrays is 2^n; so having a value of n much higher than 20 to 30 can result in incredibly long running times.

The code below uses this algorithm by counting up to 2^x-1 in base 10 and converting each number to binary – in order to ensure that each resulting bit array has a length of x, the program ‘pads’ every base 2 number with leading zeroes (in the interest of maintaining the scope of this post, the problem of converting a denary number to base 2 will not be looked at in detail here). Each binary number is represented by a string, which the program parses through in order for a ‘counter selection score’ to be calculated. The binary numbers which have a  ‘counter selection score’ of s are printed to the standard output.

 

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//This function converts the denary number num
//to binary, padding the resulting bit array
//with leading zeroes such that it is returned
//from the function with a length of x.
string CreateBitArray (int num, int x) {
    int dividedNum = num;
    string bitArray = "";
    while (dividedNum > 0) {
        int rem = dividedNum % 2;
        char remChar = '0' + rem;
        bitArray += remChar;
        dividedNum /= 2;
    }
    while (bitArray.length() < x) {
        bitArray += "0";
    }
    reverse (bitArray.begin(), bitArray.end());
    return bitArray;
}

//Return a 'counter selection score' given a bit array
//denoting which counters to take and which counters to leave.
int GetCounterSelectionScore (string bitArray, vector &lt;int&gt; counters) {
    int score = 0;
    for (int i = 0; i < counters.size (); i++) {
        if (bitArray[i] == '1') {
            score += counters[i];
        }
    }
    return score;
}

int main () {
    int x; //We are dealing with a set of x counters.
    cin >> x; //Take x from the standard input.

    //Take the value of each counter in turn from the standard input.
    vector <int> counters;
    for (int i = 0; i < x; i++) {
        int c;
        cin >> c;
        counters.push_back (c);
    }

    int s; //s denotes the target 'counter selection score'.
    cin >> s;

    //Now, begin counting up to 2^x-1 in denary,
    //converting each number to binary
    //and padding the resulting bit array in order
    //to get all of the possible selection combinations.
    for (int i = 0; i <= (pow(2, x) - 1); i++ ) {
        string bitArray = CreateBitArray (i, x);
        int score = GetCounterSelectionScore (bitArray, counters);
        //Print out this bit array if it has the required score.
        if (score == s) {
            cout << bitArray << "\n";
        }
    }
    return 0;
}

Another potential method of enumerating boolean a set of boolean decisions using a bit array involves recursion – this technique allows the program to bypass any conversions between number bases. Instead, a single function repeatedly calls itself twice such that all of the possible bit combinations are generated in a ‘tree’ format.

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//Store all of our possible bit arrays in a single vector,
//which we will built using recursion.
vector <string> bitArrays;
void ConstructBitArrays (string curArray, int targetArraySize) {
    if (curArray.length () == targetArraySize) {
        bitArrays.push_back (curArray);
    } else {
    string newCurArray0 = curArray + "0";
    string newCurArray1 = curArray + "1";
    ConstructBitArrays (newCurArray0, targetArraySize);
    ConstructBitArrays (newCurArray1, targetArraySize);
    }
}

//Return a 'counter selection score' given a bit array
//denoting which counters to take and which counters to leave.
int GetCounterSelectionScore (string bitArray, vector <int> counters) {
    int score = 0;
    for (int i = 0; i < counters.size (); i++) {
        if (bitArray[i] == '1') {
            score += counters[i];
        }
    }
    return score;
}

int main () {
    int x; //We are dealing with a set of x counters.
    cin >> x; //Take x from the standard input.

    //Take the value of each counter in turn from the standard input.
    vector <int> counters;
    for (int i = 0; i < x; i++) {
        int c;
        cin >> c;
        counters.push_back (c);
    }

    int s; //s denotes the target 'counter selection score'.
    cin >> s;

    //Create all of the possible bit combinations using the
    //recurring function, and then iterate through all of
    //the generated combinations and give those that
    //have a score equal to s.
    ConstructBitArrays ("", x);
    for (int i = 0; i < bitArrays.size (); i++) {
        if (GetCounterSelectionScore (bitArrays[i], counters) == s)
            cout << bitArrays[i] << "\n";
    }
    return 0;
}

‘Ad-hoc’ Problems and ‘The Grid Search’ [HackerRank]

What are ‘Ad-hoc’ Problems?

In competitive programming (the form of programming which is usually done in websites such as HackerRank and CodeForces), ‘ad-hoc’ problems are exercises which generally cannot be solved through application of specific algorithms. Instead, the programmer is usually tasked with implementing exactly what is given in the problem statement. The problems which I have been through so far on this blog have all been ad-hoc problems (I have not had to use any ‘textbook’ algorithms to create solutions for them).

‘The Grid Search’ Problem

The HackerRank exercise named ‘The Grid Search’ is another example of an ad-hoc problem. The submitted program is given two character grids, and is tasked with finding if there are any copies of the second character grid within the first character grid (the constraints state that the second grid will always be smaller than or of equal size to the first character grid). If copies exists, then the program must output “YES”, and if this is not the case, then the program must output “NO”.

gridsearchdesc

My solution to this problem is a complete search of the entire first grid (the maximum number of rows/columns the grids can possibly have is 1000, so a complete search can still be completed relatively quickly). The program begins at the first character on the first row of the first grid, and checks if it matches the first character on the first row of the second grid. If this is the case, then the program proceeds to the character to the right of this character checks if it matches the corresponding character on the second grid. This process then continues until a full row of the second grid has been checked (or until a pair of non-matching characters is found, in which case the entire procedure ends and starts again at the next character on the first grid). When a full row has been checked, the program moves down a row and repeats the process for this row. If the entire second grid matches this section, then this process can be executed until the program reaches the end of the second grid – if this is the case, the program prints “YES” and terminates itself. If this never happens, the program will complete its movement through the first grid and print “NO” before it completes execution. The following is a flowchart explaining this technique further:

thegridsearchsolutionv1

This is the code for my solution:


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//This function performs a complete search of grid,
//looking for any copies of targetGrid - if one is
//found, it immediately returns true, while if none
//are found, it returns false.
bool findString (vector <string> grid, vector <string> targetGrid) {
    int sx = 0, sy = 0;
    while (sy < (grid.size () - targetGrid.size ())) {
        sx = 0;
        string row = grid [sy];
        while (sx < (row.length () - targetGrid[0].length())) {
            int cx = 0, cy = 0;
            while (cy < targetGrid.size ()) {
                cx = 0;
                bool notFound = false;
                string curCheckRow = targetGrid [cy];
                while (cx < curCheckRow.size ()) {
                    if (grid [sy+cy] [sx+cx] != targetGrid [cy] [cx]) {
                        //Break out and move to the next starting position
                        notFound = true;
                        break;
                    }
                    cx++;
                }
                if (notFound) {
                    break;
                }
                cy++;
                if (cy < targetGrid.size ()) {
                    return true;
                }
            }
            sx++;
        }
        sy++;
    }
    return false;
}

int main () {
    int T;
    cin >> T;
    //The entire process is repeated T times
    //(where 'T' is defined as the number of 'test cases').
    for (int t = 0; t < T; t++) {
        //Read both grids from input.
        vector <string> grid;
        vector <string> targetGrid;
        int R, r, C, c;
        cin >> R >> C;
        for (int cr = 0; cr < R; cr++) {
            string crs;
            cin >> crs;
            grid.push_back (crs);
        }
        cin >> r >> c;
        for (int cr = 0; cr < r; cr++) {
            string crs;
            cin >> crs;
            targetGrid.push_back (crs);
        }

        bool result = findString (grid, targetGrid);
        if (result)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

Cut the Sticks [HackerRank]

Nature of the Problem

‘Cut the Sticks’ is a programming exercise on the website HackerRank (read the previous post for an explanation as to what this website is and how it functions). It is a relatively simple problem that can be tackled in multiple ways (two of which I will be discussing here).

The first line of input given to the submitted program consists of a single integer, referred to as N. The second line then provides the a list of N integers separated by spaces. This list represents a collection of sticks, which can be cut. However, in the problem, they can only be cut in a specific manner – they can only be cut all at once, and each stick can only be cut such that its length is reduced by the length of the smallest stick which is currently in the collection (the length of a given stick can be reduced to 0 – this removes it from the collection). We call the process of cutting the sticks in this manner a cut operation.

Consider a list of the following six sticks:

9 3 5 8 4 4

After a single cut operation, the length of each stick gets reduced by 3, because that is the length of the shortest stick in the list. Additionally, because of this, the stick of length 3 is removed from the list. This is the appearance of the array after the operation:

6 2 5 1 1

In the problem, cut operations are repeatedly performed until the list is empty (that is, the values of all of the elements have been reduced to 0 or below). The task of the submitted program is to output the number of remaining sticks before each cut operation. The problem statement can be found here.

Approach 1 – A Simplistic Method

This approach first sorts the array by order of ascending stick length before simulating the cutting operations and counting the number of sticks which get their lengths reduced, repeating this process until the value of every element in the array is below or equal to 0. This method does produce a solution which gives correct answers and passes the time constraint, but it can be made considerably more straightforward and efficient through several changes which will be discussed in approach 2.

This is the C++ code for this approach (note that a vector is being used instead of an array):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//This function loops through the vector
//in order to check if there are any elements
//with values above 0 (and thus whether
//there are any sticks left to cut).
bool HasRemainingSticks (vector <int> a) {
    for (int i = 0; i < a.size(); i++) {         if (a[i] > 0)
            return true;
    }
    return false;
}

int main () {
    //Take N as the first line of input, and then
    //fill the vector from the second line of input.
    int N;
    cin >> N;
    vector <int> a;
    for (int i = 0; i < N; i++) {         int x;         cin >> x;
        a.push_back (x);
    }

    //Sort the array before the cut operations.
    sort (a.begin (), a.end ()); 

    //Keep performing cut operations while there
    //are still elements in the vector with values above 0.
    while (HasRemainingSticks (a)) {
        //Find the first positive element of the array, then
        //reduce each of the positive elements by the value of the
        //first (and thus lowest-value) positive element,
        //and record the total number of sticks which have been cut.
        int firstPositive = -1;
        int totalCut = 0;
        for (int i = 0; i < N; i++) {             if (a[i] > 0) {
                if (firstPositive == -1)
                    firstPositive = a[i];
                a[i] -= firstPositive;
                totalCut++;
            }
        }
        cout << totalCut << "\n";
    }
}

Approach 2 – A Faster, Single-loop Solution

This approach takes into account several observations which can be made about the nature of the cutting operations – it is based upon the idea that all of the shortest sticks get removed from the array after each operation (because the length of every stick in the list gets reduced by the length of the shortest stick). First, the array is sorted (so that the elements can be looped through in order of ascending length). Then, the program begins a loop through the list and selectively cuts each stick depending on whether enough sticks have been cut beforehand to remove the stick in question from the array. After every cut operation, the current shortest element with a positive value and every element positioned after it would have had its value changed, so the total number of elements minus the index of the current element is printed (that is, Ni is printed, where N is the size of the array given in the input and i is the index of the current shortest element with a positive value). This system works because the array is sorted by order of ascending stick length (so as we iterate through the array, we will always cut the shorter sticks first).

This approach results in a considerably shorter and faster solution than approach 1, because there is no need for the program to check if there are elements in the array with values less than or equal to 0. The following C++ code uses this method:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    //Take N from the first line of input and then
    //take N integers from the second line to fill the list.
    int N;
    cin >> N;
    vector <int> a;
    for (int i = 0; i < N; i++) {         int x;         cin >> x;
        a.push_back (x);
    }

    //Sort the vector before performing any cutting operations.
    sort (a.begin (), a.end ());
    int totalCut = 0;
    int savedSum = 0;
    for (int i = 0; i < N; i++) {
        if (savedSum < a[i]) {
            totalCut += (N-i);
            savedSum += (a[i]-savedSum);
            cout << (N-i) << "\n";
        }
    }
}

Circular Array Rotation [HackerRank]

What is HackerRank?

HackerRank is a website containing a wide array of different programming exercises. When a programmer attempts an exercise, they submit their code to the website, which then runs it against a list of predefined inputs (known as ‘test cases’). If the submitted program gives the expected output to each predefined input within a certain time limit (around 2 seconds per test case), then the submission is successful. There are many other websites which function similarly to HackerRank, and many posts on this blog will involve analyses of the exercises on these websites.

Circular Array Rotation

One of the exercises on Hackerrank is named ‘Circular Array Rotation’ – the task is relatively clear-cut: the program is given an array of integers containing n elements, and this array can be ‘rotated’ (that is, it can have each one of its elements shifted forward by one index, with the final element being moved back to the start of the list).

circulararrayrotationdiagram

Additionally, the program is also given two other integers: k and qk is merely the number of times the rotation operation described above is performed on the array (so, if the value of k in the input was 3, each element would be shifted three times). q is used to represent the number of ‘queries’ the program is given – the next section of the input contains a series of q integers, with each integer representing an index in the rotated array. For each query, the program is required to print the value of the element in the rotated array at the given index.

The full problem statement (including the input constraints and sample test cases can be found here).

Approach 1 – Data Manipulation (The ‘Bad’ Solution)

One way of approaching this problem is by developing a program which can store the array and perform the described rotating operation through the manipulation of the array’s elements. A function can be written to perform a single rotation by saving the last element of the array and then looping backwards (through the whole list) and setting the value of each element to the value of the element positioned before it. When the element at index 0 is reached, its value can then be set to the saved value of the final element. This function can then be called k times in order to create the final, rotated array. After this is done, the program can proceed to take respond to each query in turn by checking the elements at the given indices in the rotated array.

This C++ code applies this approach:

#include <iostream>
using namespace std;

//This function is called to rotate the array once.
void RotateArray (int a[], int n) {
    //The variable 'le' holds the last element of the array.
    int le = a[n-1];
    for (int i = n-1; i >= 0; i--) {
        a[i] = a[i-1];
    }
    a[0] = le;
}

int main() {
    //Take the integers n, k, and q from the input.
    int n, k, q;
    cin >> n >> k >> q;
    int a[n];
    //Take the list of integers from the input.
    for (int i = 0; i < n; i++) {         cin >> a[i];
    }
    //Rotate the array k times.
    for (int i = 0; i < k; i++) {
        RotateArray (a, n);
    }
    //Take each query and look at the elements at the given
    //indices in the final rotated array.
    for (int i = 0; i < q; i++) {         //The variable 't' holds the target index.         int t;         cin >> t;
        cout << a[t] << "\n";
    }
    return 0;
}

This solution does provide correct answers, however, it does not do so within the time constraints when presented with very large arrays and/or very large numbers of test cases. The reason for this is quite apparent: every time the function ‘RotateArray’ is called, the program loops through the contents of the array, and given that k rotations are performed, the program loops through the entire array times. The values of n and k can be anything up to 100000, so it is possible for the program to be forced to perform 100000*100000 calculations before the queries are even considered! This is the root cause of this solution failing to meet the time constraints.

Approach 2 – Performing the Rotation as Input is Given (A Shorter, Faster Solution)

One may notice that since all of the elements are shifted by the same number of places (and that this number is provided in the input before the array), it is possible to completely avoid having to perform the rotation operation – this can be done by appropriately setting the index of each given element as they are given in the input. If the value of k were to be 2, the index of each element in the array would be its position in the input plus 2 (because it is shifted twice). To accommodate for the numbers towards the end of the array wrapping around to the beginning, the modulo (%) operation can be used – this is because the index of the final element is always n-1, and if the value of k were to be 1, the final element would (theoretically) be shifted to position n, and nn is equal to 0. By the same token, (n+1) % n is equal to 1, so the modulo operation can be used to account for the elements which are shifted from the end to beyond the beginning of the array.

These ideas can be used to form a single expression to calculate the resulting index of each element after k rotations, while input is given. The expression is as follows:

(i+k) % n

Where and n are as described in the problem statement, and i is the initial index of the element in the array. The array can then immediately have its elements saved into their calculated rotated indices while the input is being given, resulting in a significantly shorter, simpler and faster program than approach 1.

This C++ code applies this approach:

#include <iostream>
using namespace std;

int main() {
    //Take the integers n, k and q from the input.
    int n, k, q;
    cin >> n >> k >> q;
    int a[n];
    //Create the rotated array while the input is being given.
    for (int i = 0; i < n; i++) {         cin >> a[(i+k)%n];
    }
    //Print the values at the given indices in the rotated array.
    for (int i = 0; i < q; i++) {         //t is used to represent the target index.         int t;         cin >> t;
        cout << a[t] << "\n";
    }
    return 0;
}

That’s it for this post! In other news, at the time and location of writing, 2017 is around 9 minutes away, so Happy New Year to all of you!