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

Graph Theory – Breadth-first Traversal and Depth-first Traversal

Hello all – given that myself and many other students worldwide are currently in the midst of the exam season, I haven’t been very active on this blog. I hope that you all will bear with me for the time being – when my exams are complete, I will be able to start making blog posts more frequently again.

As the title suggests, this post will be about graph theory, a very interesting and useful aspect of mathematics and computer science which is also encountered frequently in competitive programming. The graphs which we will encounter in this post are not the graphs one may associate with high school statistics! Instead, these graphs consist of a series of ‘nodes’ (sometimes called ‘vertices’), connected by ‘edges’.

graph

These graphs are commonly used to represent a set of points in space, and the connections between them. For example, a problem encountered in a programming contest may involve a set of towns connected by roads – these towns can be represented by graph nodes, and the roads can be represented by the edges in between the nodes. Edges in a graph can be both ‘directed’ and ‘undirected’. To illustrate this concept, we can think of two nodes x and y – if the edge between them is undirected, x can be reached from and y and be reached from x. On the other hand, if the edge is directed, only one of the two nodes can be reached from the other node (if we refer back to the analogy with towns and roads, a directed edge could represent a one-way street).

There are various ways of representing graphs in code, however, we will focus on using an ‘adjacency list’. This is a method of storing a graph by representing each node as a set of edges to other nodes – for example, in C++, an adjacency list could be a vector of vectors of integers, where each vector of integers holds the indices of all of the nodes connected to the node represented by the vector in question. Moreover, if the edges of the graph are undirected, the vectors representing two connected nodes would contain the indices of each other (that is, if the two nodes were x and ythe vector representing x would contain the index of the vector representing y, and vice versa). In the programs used in this post, we will construct our graph by first taking the number of nodes as input, and then taking the number of edges. For each edge, we take two integers – these integers represent the indices of the two nodes connected by an edge.

inputgraph.png

Many problems in programming contests require graphs to be ‘traversed’ through – this means that the problem’s answer will need to be obtained by moving through a generated graph. Two methods of traversing through graphs will be discussed in this post: depth-first traversal and breadth-first traversal. When these methods are applied in a program, the nodes of a graph are ‘visited’ in a certain sequence determined by the traversal technique. When we say that we have visited a node, we mean that we have obtained its index. An undirected graph will be used in our demonstrations – we will move through this graph and print the index of each node as we visit them.

The depth-first traversal technique moves through a graph in the manner suggested by the name – it goes ‘deep’ into the graph before looking at adjacent routes. The image below shows every node in a graph being traversed using a depth-first traversal starting at the node with an index of 0 (note that we could have started the traversal at any node).

DFSTraversal.png

A simple way of implementing a depth-first traversal is through recursion – if we represent the graph as a vector of vectors of integers, we first call a recurring function and pass it the index of the starting node as an argument. Then, we recur for every integer in the vector indexed by the function’s argument (since each integer in this vector represents the index of a node connected to the current node). In order to prevent our traversal algorithm from continuously revisiting the same sets of nodes (this could potentially cause a stack overflow), we can use an array of boolean variables which represents the ‘state’ of each node (that is, whether each node has been visited or not). If the boolean at index i of this array is set to true, then the node at index i of the adjacency list has been visited. Every time we are about to recur, we check to ensure that the index we are about to recur with has not already been visited. Furthermore, every time we recur, we mark the newly-visited node as visited by changing its corresponding boolean value in the array.

An implementation of a depth-first traversal using recursion can be found here.

Alternatively, we can also implement a depth-first traversal in C++ using a stack of integers (these integers represent the indices of the graph nodes) – the main operations we are concerned with here are the ‘push’, ‘top’ and ‘pop’ operations. A stack is a data structure which is available in the C++ – it can be used to store and retrieve variables in the same manner objects can be stored and retrieved from a stack in real life. If we imagine our stack as a stack of sheets of paper, the ‘push’ operation adds a sheet of paper to the top of the stack, the ‘top’ operation retrieves the sheet of paper which is currently at the top of and the ‘pop’ operation removes the sheet of paper which is currently at the top.

stackanalogy.png

To perform a depth-first-traversal using a stack in C++, we initially push the index of the starting node onto the stack. Then, we use a ‘while’ loop which runs as long as the stack contains some integers. Every time we run an iteration of this loop, we use the ‘top’ operation to retrieve the index at the top of the stack (clearly, this index would be the newest index which has been pushed) and then the ‘pop’ operation to remove this index from the top. Then, we loop through all of the connecting indices at this index of the adjacency list and push them onto the stack where appropriate. Note that we still should use an array of boolean variables here – we need to check this array before pushing any indices onto the stack in order to ensure that we do not revisit any previously-visited nodes. Since we are using this array, we will eventually reach a point in the algorithm where we stop pushing any new indices, and we will thus empty the stack and finish the traversal.

An implementation of a depth-first traversal using a stack can be found here.

A breadth-first traversal works in a different manner to a depth-first traversal – here, we check every adjacent node in turn before moving onto the next level of depth (hence why the technique is referred to as breadth-first).

BFSTraversal.png

An elegant way to program a breadth-first traversal in C++ is to use a queue – this data structure is vaguely similar to the stack structure in terms of usage, however, we can think of a queue structure as an actual queue of people in real life (as opposed to a stack of papers). Instead of having a ‘top’ operation, we have a ‘front’ operation (which retrieves the person at the front of the queue). Moreover, the ‘pop’ operation removes the person at the front of the queue. Pieces of data can thus be retrieved from a queue in the order they were added – therefore, we can use a ‘while’ loop to program a breadth-first traversal in the same way we use this loop to perform a depth-first traversal. We can begin by pushing the starting node index onto a queue and then pushing each of the nodes connecting to it onto the queue in turn (while still ensuring that we do not revisit previously-visited nodes by checking and updating an array of boolean variables) – this process can be repeated in the loop until there is nothing left to push onto the queue and we run out of nodes which need to be visited. Since the node indices are retrieved from the queue in the order they were pushed, all nodes adjacent to a given node are visited before the other nodes connected to each adjacent node are visited.

An implementation of a breadth-first traversal using a queue can be found here.

That concludes this post! In future posts, we will work through some graph-related problems on competitive programming websites, in addition to continuing the ‘Tetris for Android’ project.

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";
    }
}