It was great preparing a hard problem for Counter Code hosted by HackerRank. Competition was great, and during 24 hours 26 participants manage to solved it. This is the most detailed editorial that I have written so far.
The problem is available here: Long Narrow City
Statement
Problem statement is quite clear, we are given a graph for which we have to count the number of its spanning trees, containing at most k distincted roads. can be any number in range
and there are at most
distincted roads given in the input.
However, the graph can be really huge! It can have up to vertices - definitely way too big to store them in the memory.
The good news is that is has a very specific structure. As the name of the problem suggests, it is very long, but fortunately a narrow one
Specifically, it has layers: top, middle and bottom, each consisting of
vertices. Layers along with graph edges are presented in the below drawing. Notice, that there are
edges between consecutive layers and each layer contains
internal edges:
Now we know what we are dealing with, so let's start solving it. What I like often to do, is to start with some simpler problem, derive a solution to it, and then adapt it further to the original problem. Let's give it a try here!
Simplified problem
First, let's assume that there are no distincted edges.
Simplified graph
Moreover, let's assume, that the graph has only layers instead of
. It is even more narrow, isn't it? From now we are referring only to simplified graphs unless we call the graph original explicitly.
Our simplified graph looks like this:
Since we assumed that there are no distincted edges, our task is to find the number of all spanning trees of it.
First, let's define what a segment it our narrow graph is. We call a segment a set of vertices with numbers
for original graph, and a set of
vertices with numbers
for a simplified one.
An example segments, for original graph and simplified graph, are presented it the below drawing. Green vertices belong to the current segments, while red ones belong to the previous ones. Edges connecting these segments are also presented:
Let tail be the last segment of the graph.
Now we are ready to count the number of spanning trees of simplified graph. A great way to do that, is to try to extend a solution for a smaller graph by adding a new segment to it as a tail.
Let be a simplified graph with
vertices. We can extend
to
by adding a new segment to it and connect it to the tail of
.
This is the incremental method to build our graphs.
In order to count the number of spanning trees of , let's assume that we know the number of spanning trees of
. How does it help? Well, let
be any spanning tree of
. We can extend
to a spanning tree of
by adding some edges of the tail of
to
.
The crucial observation is that we can count spanning trees incrementally as well.
But be aware here. Does any spanning tree of can be produced from a spanning tree of
? Let's consider the below drawing presenting a valid spanning tree of
.
If you look closely, you will notice that this spanning tree cannot be produced from any spanning tree of , because vertices
and
are connected in it through the tail of
.
However, the good news is that it can be producted from a spanning forest of with two connected components in which the top layer is the first connected component and the bottom layer is the second connected component. What is more important, the following fact is true:
Every spanning tree of can be produced by extending a spanning tree of
or a spanning forest of
, in which top and bottom layers are different connected components, by adding a new layer and connecting it with some edges to the previous structure.
This is true, because in any valid spanning tree of , vertices
and
have to be connected by exactly one path. They can be connected by a path which does not use vertices
and
or by a path which uses them. In the first case, the T_{N+1} is formed from
, while is the second case, it is formed from a forest of
in which the top and the bottom layers are distinct connected components.
This is a good news, because we can count the number of spanning trees of by just knowing the number of spanning trees of
and the number of specific spanning forests of
.
Let be the number of spanning trees of
and
be the number of spanning forests of
in which top and bottom layers are distinct connected components. In order to get the exact equation for
, we have to examine below cases and count the number of possible extensions in each case.
- Any
can be extended to
in
different ways, because we can add any
of
edges which are adjacent to vertices from the last segment of
- Any
can be extended to
in just one way, because we have to add all
edges adjacent to vertices from the last segment to
.
- Any
can be extended to
in
ways, because we have to add just one horizontal edge adjacent to vertices from the last segment of
to
and there are two ways to do that.
- Any
can be extended to
in just one way, because we have to add
horizontal edges adjacent to vertices from the last segment of
to
.
Let be the number of valid graphs of type
and
be the number of valid graphs of type
.
Clearly, and
. From the above analysis, we know that:
These two equations helps us to compute the number of spanning trees of simplified graphs.
Original graph
That is great, but what does it have to do with our original graph with layers of vertices? Well, the same analysis works, but we have more cases to consider. From now we are referring to original,
layer graphs, unless we call the graph explicitly simplified.
First some definition, which will helps us to refer to some things.
Let be vertices in the last layer of
. We define the following graphs:
Let be a spanning forest of
, in which vertex
belongs to one connected component, vertices
and
belong to the other one, and there are only two connected components in this forest.
Let be a spanning forest of
, in which vertex
belongs to one connected component, vertices
and
belong to the other one, and there are only two connected components in this forest.
Let be a spanning forest of
, in which vertex
belongs to one connected component, vertices
and
belong to the other one, and there are only two connected components in this forest.
Let be a spanning forest of
, in which vertices
belong to 3 different connected components, and there are 3 connected components in this forest
is defined as before, i.e. it is a spanning tree of
, so all vertices
belong to the only connected component.
All above graphs are presented below - vertices belonging to the same connected component have the same color and there are as many connected components as colors of vertices in the last segments (notice that I did not draw any edges between these vertices just for generality - we don't assume by what path they are connected, we just indicate that they are connected - might be by direct edges and might be by longer paths):
Let also be the number of graphs of corresponding types defined just above.
Based on these values, we can compute in a similar way that we did it in for simplified graphs. There are just more cases to consider and each of the above
functions has its own recursive relation. The exact relations are presented below. You can compute them either by hand or write a small program to do it for you. I decided to do it by hand first and then double check it by a program:
You have to derive values to also.
Having these relations, we are able to compute the number of spanning trees of our graphs of any reasonable size. Even if is as big as
, we can still use matrix exponentiation to do that quickly.
So far so good, but remember that we simplified the problem to not having any distincted edges. Let's now get back to our original problem.
Original problem
In the original problem, we have at most distincted edges and we want to know the answer to how many spanning trees of
are there, such that they have at most
distincted edges, where
is at most
.
How do deal with that problem? Well, do you remember how we extend, let's say to
? From the recursive equations derived before, we know that there are
ways to do that i.e. there are
subsets of edges forming a segment such that you can connect them to the tail of any
to form a valid
. Let's call the st of these subsets
.
Let's also define as
with exactly
distincted edges. Similarly we define
and so on. Let's pick any subset of edges in
, call it
, and assume that
has
distincted edges.
The crucial observation here is that we can form a valid from any F^1_{N, a} by adding edges from
to
.
Based on these observations we can implement a dynamic programming solution to the the problem.
Let be the number of spanning trees of
with exactly
distincted edges.
Similarly we define ,
,
and
Then we can compute any of above tables iterating over each segment in the graph, then iterating over each possible subset of edges in this segment and extending the solution to the larger graphs by examining how many distincted edges this subset has and to what kind of graph this subset extends our current graph (if it extends to any). You can precompute the extension table, i.e. precompute if a graph of type, let's say F_1 can be extended to, let's say F_3, using a particular subset of edges.
However, since is up to
we are not allowed to iterate over all segments in the graph. Think for a second, do we really need to do this? Of course we don't. Notice that there are at most
distincted edges in the input, so there are also at most
segments with any distincted edge, which is like nothing comparing it to the
possible segments. What we can do instead, is to assign distincted edges to segments to which they belong, sort this segments in increasing manner and process the graph from left to right. We have two cases to consider then:
- The current segment has distincted edges.
In this case, we can use our dynamic programming method to extend the solution to the graph with one more segment. - The current segment is free of distincted edges.
In this case, we can see how far to the right is the next segment with distincted edges. Then we can use the recursive equation and matrix exponentiation, which are described in the simplifier problem, to extend the current solution to the segment just before the next segment with distincted edges. Since this method is pretty fast, we are able to skip over huge number of segments without dangerous edges very fast.
Notice that we are not allowed to store the whole table anymore, because there are just too many segments. The good news is that we do not have to do this, because we just need to know the entry corresponding to the last examined segment. This reduces the space complexity a lot and is a common trick in these type of problems.
Since in the statement we are asked to answer questions on how many spanning trees with at most dangerous edges are for some values of
, we can now easily answer them based on our
tables, just by computing:
where is the number of spanning trees of the input graph with exactly
distincted edges.
Time complexity
First, you have to precompute the table of extensions, which stores the information if a graph of one type can be extended to a graph of another type using some particular subset of edges. Since there are types of graphs,
subsets of edges, and you can compute the resulting graph for a given graph and subset of edges using
this takes so small amount of time that we do not have to worry about it.
During the computations, sometimes you use skips by matrix exponentiation and since the matrix size if and the longest skip has length
, one skip takes
.
At most times we are forced to compute the extension of a current graph by dynamic programming, and doing this for one segment takes
, where $K$ is maximum number of distincted roads in a query. This is true, because in
table an entry for a graph of one type is based on values of every of
other types of smaller graph and we compute the extension for any possible number of distincted edges. Computing one such entry takes 32 subsets of edges to consider. However this could be reduced by just examining the valid subsets of edges for a particular type of graph i.e. these ones which extends it to some other graph.