There is no commentSelect some text and then click Comment, or simply add a comment to this page from below to start a discussion.
Editorial - Constructor 2024 - Practice Round
Problem L - Roads
Editorial by : fonmagnus
Abridged Problem Statement
Count how many ways to construct a graph of nodes such that :
No multi-edge (no pair of nodes connected with edges) or loops (no edge connecting a node to itself)
All nodes need to be connected
Let is the shortest path from node to node , then the following condition must be true :
There should be exactly one shortest path from node to all other nodes
Modulo the result by
(Time Limit : 1 sec., Memory Limit : 256 MB)
Solution
Observation 1
We can make a tree graph rooted at 1. If we do so, the depth of the node with the higher number must be greater than or equal to the depth of the node with the lower number
Illustration : The following tree is a valid tree graph :
Image Not ShowingPossible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Let's assume we have form a valid tree graph rooted at node for nodes that fulfills the condition, then :
Observation 2
We can add some edges in the tree. But we can only connect a pair of nodes that belongs to the same depth
Proof by contradiction:
If we add an edge from a pair of nodes that belongs to different depth then either one of the following would happen :
there will be multiple shortest path from node to the deeper node (contradicts the 4th condition because there must be exactly one shortest path from to all other nodes)
Illustration :
Image Not ShowingPossible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Take a look at this graph. If we add edge from then the length of the shortest path from to will no longer becomes
Observation 3
Adding a new edge from any pair of nodes in the same depth won't contradict the 3rd or 4th conditions
Reason :
Because by adding an edge between 2 nodes in the same depth, won't change the value of the shortest path
Based on observation 3, we can add an edge with any pair of nodes in the same depth. The number of ways to do this is : or where is the number of nodes in this depth
The formula above can be obtained using the following :
There are nodes on the same depth, therefore, there are pairs (or possible edges)
Out of those edges, we can choose whether or not to add that edges to the new graph, thus
Based on the observations above, we can count the answer using the following :
Build an array of elements (i.e. ) such that where
To calculate the answer, we can use the following : Group some consecutive elements with the same value together in for example :
Then we can group them as follows :
And then to calculate the number of edges, we can just count :
. In the example for above, the number of edges are :
So the next question is :
How to count the number of ways to construct ?
For each of valid , how many possible tree that can be constructed?
We will answer those questions in the next section
Counting ways to count trees when constructing
For a better understanding, take a look at the following tree graph below :
Image Not ShowingPossible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
As you can see, the number of ways to place node is equal to the number of nodes that has (that is node )
From the observation, we can define this following function :
Define as follows :
The number of ways to construct array such that :
We currently want to fill th element
The previous consecutive has a length of
The previous consecutive before the previous consecutive has a length of
For example, in the illustration above when we have filled , then when we want to fill , the state would be :
because :
. We currently want to fill th element
. The previous consecutive elements are has the length of
. The previous consecutive elements before it are has the length of
Then we can calculate the value of using this transition
Transition 1 : Placing We can place th node in ways. so :
Transition 2 : Placing : We can place th node in ways, and we're closing the consecutive elements together, so we can add edges from the same depth (see observation 3) so :
Therefore
And for the base case :
, then (because we have to count the last consecutive elements that we have placed after we have placed all elements)
Some Optimization on Implementation
Memory Complexity : The memory complexity uses due to the 3 DP states. It can be optimized to if we use a bottom-up DP with flying table
Time Complexity : The time complexity of this approach is because we have 4 unique DP states and can be "prune" by limiting the upper bound of and into the following pseudocode: