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

‘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!