Trees, Permutations, and Number Theory
Algorithmically Speaking - #15: The first example of a problem involving bipartite graphs in disguise.
Hello there!
Welcome to Algorithmically Speaking, where we discuss topics on the intersection of Computer Science, Software Engineering, and life.
Today’s topic is an example of the types of problems that can be solved in computer science using bipartite graphs. In this post, I will present one purely academic problem and guide you through the whole thought process of solving it efficiently.
This post is taken directly from my upcoming book, The Competitive Programmer Graphs Handbook, a graph theory book focusing on three main topics: bipartite graphs, functional graphs, and Euler paths. You can read all the details here:
You can play a crucial role in bringing this book to life by preordering your digital, DRM-free copy. By doing so, you'll receive early and frequent updates, including all future editions.
In my years as a competitive programmer, I usually focused on two main types of training: team training, where I sat down with my team for about 5 hours to simulate competition, and individual training, where I either participated in a solo contest or solved problems I could not solve live during a competition (upsolving).
The most efficient way to do both was to go to one of the competitive programmer websites and either look for live competitions or individual problems to tackle. The problem I will present to you today comes from AtCoder, a Japanese website that hosts weekly competitions.
I chose AtCoder many times to do my individual practice because their staff of problem setters usually craft problems in which the solution is not obvious at first glance. Some other competition sites will sneak one or two really easy-to-solve problems, maybe as a way to get people motivated, but AtCoder is all about thinking from the very beginning.
Next, we will look at one of those examples where creativity is as important as technical knowledge. A problem that combines pieces of the fields of graph theory with the basics of number theory.
If that sounds enticing, please read to the end. I will also link to the original problem so you can test your skills.
Before we begin, if you think you need a refresher on the basics of graph theory to take the most out of today’s discussion, please look at the previous articles of this series:
Statement
Today, the problem we will analyze will be presented with a formal statement. This is the original text in AtCoder’s website:
Given a tree with n vertices numbered from 1 to n. The distance between two vertices is defined as the number of edges in the shortest path between them. You must find a permutation p, with values between 1 and n, such that the following condition is satisfied:
For every pair of vertices u and v, such that the distance between them is 3, it must hold that pu + pv ≡ 0 mod 3, or pu * pv ≡ 0 mod 3.
If you are not familiar with the notation above, this is what it means:
If we have an expression of the form X ≡ Y mod Z, the term X leaves a reminder of Y when divided by Z.
This definition comes from the field of number theory, particularly modular arithmetic.
In other words, the statement above says that we need to assign a number from 1 to n to each vertex in a tree so that for every pair of vertices at distance 3, either the sum or the product of the numbers assigned to them is divisible by 3.
If you desire, you can pause here and think about how you would solve this problem before moving on to the next section, where I will reveal the solution. In my opinion, this is the best way to take advantage of these posts.
Analysis
The problem is set on a tree. Because trees are a very particular type of graph, problems usually have solutions that involve simpler algorithms than those used in more general graphs. Even some algorithms defined for graphs are often easier to implement when the graph in question is a tree.
This does not mean trees are any less attractive from a theoretical and practical standpoint. The observations and ideas needed to solve a problem involving trees are often clever and, in many cases, lead to the implementation of a simple and elegant algorithm.
One of the most important properties of trees is that they are a type of bipartite graph. Indeed, suppose a root s is designated for the tree, and the BFS algorithm is executed starting from that vertex. In that case, the nodes belonging to even levels will be assigned one color, while those belonging to odd levels will have the opposite color. Because trees are acyclic graphs, they present no cycle of odd length.
This fact is the key to solving the problem at hand and is always something to keep in mind when facing a tree-related task. For example, in this case, the problem enforces certain restrictions between vertices at a distance of 3. Analyzing in detail what happens with these vertices might be crucial for the solution of the problem.
Proposition 1. Given a bipartition (A, B) of the vertices of a tree, every pair of vertices at a distance of 3 belongs to different sets.
Proof. Let v1, v2, v3, and v4 be the vertices that belong to a path of length 3. Consecutive vertices on this path belong to different sets, as there is an edge between them. Without loss of generality, assume that vertex v1 belongs to set A, then the sets to which each vertex belongs are A, B, A, and B, respectively. ∎
Knowing this, the solution likely uses the graph's bipartite nature. Moreover, as with any constructive problem, where it is necessary to build something subject to constraints (in this case, a permutation), it is essential to ask ourselves whether it is always possible to find a solution.
Proposition 2. The given problem always has a solution.
Proof. Let |A| and |B| denote the cardinalities of the sets A and B belonging to the bipartition of the tree. Without loss of generality, assume that |A| ≤ |B|. Let X be the number of multiples of 3 in the interval from 1 to n. Let’s show that it is possible to construct a valid solution in either of these two cases:
|A| ≤ X: In this case, if each vertex belonging to set A is assigned a number of the form 3k and the remaining numbers are distributed arbitrarily, the given restriction is satisfied. Since in each pair of vertices at a distance of 3, one belongs to set A, the product of the numbers assigned to these vertices will be a multiple of 3.
In the image above, we see a tree that meets the criteria described in the first case. The set A is formed by the vertices 1 and 4; therefore, we assign the numbers 3 and 6, respectively. The rest of the numbers are assigned arbitrarily to the rest of the vertices.
Take any two vertices at a distance of 3 in this tree; one of them will always have a multiple of three assigned to it.
|A| > X: If this occurs, the following construction will be made:
Numbers of the form 3k+1 will be assigned to vertices belonging to set A.
Numbers of the form 3k+2 will be assigned to vertices belonging to set B.
The numbers of the form 3k will be distributed arbitrarily among the vertices that have not yet been assigned a number.
Let (u, v) be two vertices at a distance of 3. Two things can happen:
One of the two has been assigned a number of the form 3k. In this case, the product of both numbers is a multiple of 3.
Neither has been assigned a number of the form 3k. Since u and v belong to different sets, one has been assigned an integer of the form 3k + 1 and the other one of the form 3q + 2. Adding both values, we get:
(3k + 1) + (3q + 2) = 3k + 3q + 3 = 3(k + q + 1) = 3m
Therefore, the sum of both numbers is a multiple of 3.
In the image above, we can see a tree that meets the criteria described in the second case. Take any two vertices at a distance of 3, and check that either one has been assigned a multiple of 3 or none of them has.
In both cases, the sum or product of the numbers assigned to vertices at a distance of 3 is a multiple of 3.
Since both cases are mutually exclusive and cover all possible scenarios, there is always a solution. ∎
I hope you enjoyed today’s post, where I presented a practical application of bipartite graphs to a non-trivial problem involving number theory concepts and trees.
I omitted the implementation details here because I believe there is more value in sharing the theoretical aspects of this problem than the actual code to construct the desired output. The pseudocode and my implementation of this problem will be available in my upcoming book, The Competitive Programmer Graphs Handbook.
If you wish to try this problem on the official AtCoder website, here’s the link: Problem ThREE. Let me know in the comments below if you attempted to solve it and how it went.
And that’s it for today! If you are finding this newsletter valuable, consider doing any of these:
1) ✉️ Subscribe to the newsletter — if you aren’t already, consider becoming a free or paid subscriber.
2) 💛 Get early access to my book— thanks to all of you who have contributed to support my writing. The book I'm writing covers this and similar topics in more depth.
3) 🍻 Read with your friends — this newsletter grows because readers share. I don’t use social media too much to advertise my writing. I’m counting on you!
Have a great day! ☀️
Alberto