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 Leapfrog Problem

My mathematics teacher recently presented my class with an interesting problem he named the ‘Leapfrog Problem’. The idea revolves around a frog positioned on an infinitely large 2D plane – this frog can ‘leap over’ another point in this plane. When the frog performs this action, it covers the distance from its current position to the point, and then makes the same movement a second time. This motion can be thought of as the frog moving along a line where the point is the line’s midpoint.

Leapfrog1.png

In the ‘Leapfrog Problem’, the plane contains four points – one initial position for the frog, and three other points named A, B and C. These four points can be positioned anywhere on the plane. The frog first leaps over point A – after this has been done, the frog leaps over point B starting from its current position after its leap over point A. Then, the frog leaps over point C. This cycle repeats itself, with the frog leaping over A, B and C in turn once more. However, when the frog leaps over C a second time, it will always land at its initial position, regardless of how the origin and points A, B and C have been positioned. The objective of the problem is to prove why this is the case. In the images below, a relatively simple example of the frog’s movement is illustrated:

leapfrogaction1

leapfrogaction2

leapfrogaction3

leapfrogaction4

leapfrogaction5

leapfrogaction6

Solution 

Proving why the sequence of jumps always returns the frog to its starting position can be done elegantly using vectors. The key insight is that if we represent the position of the frog using a position vector (with the starting point as the origin) and we define three vectors (with each vector leading from the origin to one of the three points A, B or C), we can always calculate a route from the frog’s position to one of the three defined points. The vector representing this route can then be multiplied by 2, in order to give a vector which describes the ‘leaping’ motion.

Leapfrog7.png

In order to calculate a route from the frog’s position to one of the three defined points, we first invert the frog’s position vector (this gives a vector which leads from the frog’s position back to the origin) and then add the vector which leads from the origin to the target point. The vector which leads from the origin to point A can be defined as a, while the vector which leads from the origin to point B can be defined as b, and the vector which leads from the origin to point C can be defined as c. If we model the movement of the frog using vector manipulation, we can see that the frog’s position vector always evaluates to 0 after its second leap over the point C – this proves that the frog will always return to the origin.

LeapfrogVectorManipulation.PNG

Since we have not given any of our variables specific values – that is, we have only defined our vectors using the arbitrarily positioned points specified by the problem, and they always cancel each other out – neither the magnitude nor the direction of any of our vectors has any effect on the final outcome of the manipulation, we have shown that the frog will always return to the origin regardless of how its starting position and the points A, B and C have been positioned.

The original source for the Leapfrog Problem can be found here.

Interesting Geometry Questions from the Intermediate Maclaurin Mathematical Olympiad (Part 2 – 2010)

This post covers a second set of geometry problems from the Intermediate Maclaurin Mathematical Olympiad (a mathematics competition run by the UK Mathematics Trust, aimed at students of age 16). Like the problems in the previous post, these problems do not require knowledge beyond that of a GCSE-level student, they are more a test of one’s creativity and insight than a test of one’s knowledge of the subject.

Problem 1

geometrymaclaurinp1

The two key pieces of information in this problem’s description are that all three shapes are regular, and that they have an edge in common. Another way of phrasing this is that every visible line in the question’s diagram has the same length. Additionally, since all three shapes are regular, they all have their own sets of equal internal angles. We can calculate the size of a single internal angle from all three shapes using the formula below (where n is the number of sides the polygon has):

Sum of the interior angles of a polygon (degrees) = (n-2) * 180

Single internal angle (degrees) = Sum of the interior angles of a polygon (degrees) / n

Using this procedure, we acquire the following sizes for a single internal angle of each polygon:

  • 15-gon: 156 degrees
  • Heptagon: 900/7 degrees
  • Decagon: 144 degrees

In order to find the size of angle XYZ, we need to take into account two ideas: one being that the sum of the angles around a single point is 360 degrees, and another being that the sum of the angles inside a triangle is 180 degrees. To progress further towards a solution, we can first focus on the lower point of the side the three polygons have in common (this point will be named P). We can find the size of the angle XPY by subtracting 900/7 degrees and 144 degrees from 360 – doing this gives the value 612/7. Additionally, we can also find the size of the angle ZPY by subtracting 900/7 degrees from 156 degrees – doing this gives the value 192/7. Given that the lengths of the lines PZ and PY are equal (since every visible line in the question’s diagram has the same length), we can state that the triangle ZPY is an isosceles triangle, and we can find the angle PYZ by subtracting  192/7 degrees from 180 degrees and dividing the result by 2 – this gives the value 534/7. To find the size of the angle XYZ, we can subtract the size of the angle XYP from the size of the angle PYZ. Getting the size of the angle XYP can be done by subtracting the size of the angle XPY from 180, and dividing the result by 2. To find the size of the angle XPY, we can subtract the values 144 degrees and 900/7 degrees from 360 degrees to obtain the value 612/7. Subtracting this value from 180 degrees and dividing the result by 2 gives the value 324/7 for the size of the angle XYP. We can now find the size of the angle XYZ by subtracting 324/7 from 534/7; doing this gives the value 210/7, which simplifies to 30 degrees.

geometrymaclaurinp1working1

Problem 2

geometrymaclaurinp2

In order to tackle this question, we must be aware of the circle theorem which states that a triangle drawn inside a semicircle with the longest side being said semicircle’s diameter will always be a right-angled triangle. Therefore, the triangle formed by the three points C, A and D is a right-angled triangle. Given that we know that the length of this right-angled triangle’s hypotenuse is 4, we can use the Pythagoras Theorem to find the length of CD if we know the distance between the two points A and C.

A kite can be drawn inside the circle if a radius is drawn to the point C. A key characteristic of this kite is that the length from its lowest point to its highest point is 2 (because this length is the radius of the circle).

geometrymaclaurinp2working2

This kite can then be split into four right-angled triangles, with the side lengths shown in the image below:

geometrymaclaurinp2working1

In the drawing above, we acknowledge that the distance from the lowest point of the kite to the highest point is 2, and we split this distance at the line AC to form two lines of length x and 2-x. Additionally, we know that the shape above is symmetrical, so the line from its lowest point to its highest point bisects the line AC into two smaller lines of length y. Focusing on one of the two sides of the kite, we can use the Pythagoras Theorem to form the following equations:

geometrymaclaurinp2working3

geometrymaclaurinp2working4geometrymaclaurinp2working5

First we observe that x^2 and y^2 sum to 1, and then we can subtract this expression from the sum of y^2 and (2-x)^2 to obtain a linear equation which we can then solve to find the value of x. We can then substitute this value of x into our first equation in order to acquire the positive value of y (obviously, a negative value of y does exist, but here we disregard it because we are dealing with length).

Now we can go back to our original image of the circle – given that the line AC has a length of 2y, we can apply the Pythagorean Theorem as follows to find the length of CD (bearing in mind that the circle theorem mentioned at the start of the explanation for this problem states that the triangle ACD is right-angled).

geometrymaclaurinp2working7

Problem 3

geometrymaclaurinp3

This problem initially appears quite complex – it requires a crucial insight in order for it to be solved, however, with this insight, the solution to the problem is arguably the most concise and elegant out of the three solutions on this post. The various regions in the diagram are created by the intersections of two triangles with equal area, shown below:

We can see that these two triangles have equal area by looking at the formula below:

Area of a triangle = (base * perpendicular height) / 2

Given that the length of the base of one of the triangles is the perpendicular height of the other triangle, and that the multiplication operation is commutative, this formula returns the same value for the area of both triangles (we do not need to know any specific values for either the base or the height in order to see that this is the case). Additionally, this value for the areas of the triangles is equal to half the area of the entire diagram, because the triangles share their dimensions with the rectangle, and therefore the white area on the right diagram is equal to the shaded area on the left diagram – if we label the regions on the diagram in the manner shown below, we can form and solve a new equation based on this idea.

geometrymaclaurinp3working3

Looking at the two previous diagrams, the shaded area of the one on the left contains the regions ab and c, while the white area of the one on the right contains the regions of a and c, along with three regions of sizes 1, 2 and 3. Given that both sections have equal area, we can form and solve the following equation to find the area of region b, which is the shaded area in the original question’s diagram.

geometrymaclaurinp3working4

Conclusion

As the Maclaurin Olympiad draws closer, I will continue to make more posts on the problems it has given in the past. Additionally, I will also begin writing about an interesting computing-related side project of mine in the coming weeks – more about this project will be revealed soon.

Interesting Geometry Questions from the Intermediate Maclaurin Mathematical Olympiad (Part 1 – 2008)

Due to certain circumstances related to other extra-curricular activities which I am participating in over the next several months, I will be unable to compete in the Intermediate Maclaurin Mathematical Olympiad (a British mathematics competition aimed at students of age 16 and under – pupils qualify to compete in it through achieving high scores in the UKMT Intermediate Challenge; more information on it can be found here). This would have been the last year I would have been young enough to participate in the competition, so I will be unable to attempt it ever again. However, several requests from fellow students of mine have led me to write about some of the questions which have been presented in this olympiad, in hopes of assisting any potential competitors both this year and in the future. The problems I will be exploring in this series of posts will have all come from past Maclaurin Olympiads, and have all been written by its organisers. This post will be focused on the problems related to geometry – no knowledge of any advanced theorems is required (the problems can be solved with a knowledge of GCSE-level mathematics).

Problem 1

Screen Shot 2017-01-24 at 9.27.27 AM.PNG

This question can be answered quite cleanly using several GCSE-level ideas about circles and polygons. The idea of this answer is to prove that the triangle DEF is an isosceles triangle with DE and DF as the two equal sides. Our first step is to observe that each angle within the pentagon has a size of 108 degrees. We can come to this conclusion using the following formula:

Sum of the interior angles of a polygon (degrees) = (n-2) * 180

In this formula, n denotes the number of sides the polygon has, so in our case, n has a value of 5, and thus the sum of the sizes of the interior angles of the pentagon is 540 degrees. Furthermore, from this figure, we can calculate the size of a single interior angle by dividing 540 by 5 – this calculation gives 108 degrees as the size of single angle.

Our next step is to calculate the angle DEF (so that we can then proceed to prove that it is equal to the angle DFE later on). The angles DEF and DEA lie on a straight line and thus have sizes that sum up to 180 degrees, and given that DEA is one of the interior angles of the pentagon, we can state that the size of the angle DEF is 72 degrees.

We must now proceed to prove somehow that the angle DFE also has a size of 72 degrees. A very simple way of doing this would be to apply the alternate segment theorem, shown below:

BlogAlternateSegmentTheorem.png

The theory states that in a circle boasting a tangent and an inscribed triangle (formed by three chords),  the angle between this tangent and a given chord is equal to the angle which is made by that same chord in the segment of the circle alternate to the segment containing the angle at the tangent. Therefore, in the diagram above, the blue angles are equal and the gold angles are equal.

Note that an inscribed triangle can be drawn on the circle in the problem, using points D, A and F. Drawing an inscribed triangle in this manner also forms a second isosceles triangle connecting points D, E and A. Remembering that the each interior angle of the pentagon has a size of 108 degrees, we can calculate the sizes two smaller angles of this newly formed isosceles triangle – both of them have a size of 36 degrees. Moreover, we can now calculate the angle CDA on the inscribed triangle by subtracting 36 from 108. We now know that the angle CDA has a size of 72 degrees, and the alternate segment theorem shows that the angle DFA also has a size of 72 degrees (as they lie on the same chord, but in alternate segments of the circle). Given that we now know that angle DEF and angle DFA both have the same size, we can state that the triangle DEF is an isosceles triangle, with DE and DF as its two equal sides. The image below illustrates this idea:

BlogPostMaclaurinGeometry1.png

Problem 2

Screen Shot 2017-01-24 at 9.27.37 AM.PNG

We can start tackling this problem by clearly defining the area of the triangle with a formula. First, we should declare that the base of the triangle is represented by b, and the height of the triangle is represented by h. Furthermore, we can use the following equation to denote the area of the triangle:

bgequations4

The path ahead is clear; we want to use the variables and y to represent both b and h, and if the above equation is true (and the question firmly states it is), the expression on the left will simplify to xy, giving an equation with two identical sides.

A key insight is that the height of the triangle is equal to x plus a certain value (let’s call this value z), and that the base of the triangle is equal to y plus this value. This is the case because when two tangents of a circle meet at a certain point, the lengths between the contact point of each tangent and the meeting point are equal. Using this theorem, three lines can be drawn on the circle: one to the base tangent, one to the height tangent and one to the longest tangent, like so:

blogmaclauringeometry2

The image shows that two kites and a square are formed when three radii are drawn, with one connecting to the base tangent and another to the height tangent. From this, we can write the following equations:

 

bgequations5

We can then proceed to apply the Pythagoras theorem to represent xy in a different manner, like so:bloggeometryequations1

We can now write a single equation using the variables xy and z to link our two separate values of xy.

bloggeometryequations2

 

Note that xy makes yet another appearance here, so we can substitute one of our known values for this term in to complete the equation.

 

bloggeometryequations3

To summarise our ideas, we can state that we have proven the area of the triangle is equal to xy by initially using both the Pythagoras theorem and a set of circle theorems to create a second expression for xy, before completing our proof by simplifying our expression for the area of the triangle such that it becomes equal to our second expression for xy.

Conclusion

I will continue to make more posts exploring various questions from the Maclaurin Olympiad as its date draws closer. The next post on the topic will come soon, and will most likely explore a second pair of geometry questions, from more recent years.