Try   HackMD

Editorial - Constructor 2024 - Practice Round

Problem L - Roads

Editorial by : fonmagnus

Abridged Problem Statement

Count how many ways to construct a graph of

N
(2N100)
nodes such that :

  • No multi-edge (no pair of nodes connected with
    >1
    edges) or loops (no edge connecting a node to itself)
  • All nodes need to be connected
  • Let
    di
    is the shortest path from node
    1
    to node
    i
    , then the following condition must be true :
    d2d3dN
  • There should be exactly one shortest path from node
    1
    to all other nodes

Modulo the result by

998244353

(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 Showing Possible 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
Learn More →

The following tree is NOT a valid tree graph :

Image Not Showing Possible 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
Learn More →

Because

d6>d7


Let's assume we have form a valid tree graph rooted at node

1 for
N
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

    1 to the deeper node (contradicts the 4th condition because there must be exactly one shortest path from
    1
    to all other nodes)

    Illustration :

    Image Not Showing Possible 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
    Learn More →

    Take a look at this graph. If we add edge from

    (2,6), then there are two different shortest path from
    1
    to
    6
    :

    • (126)
    • (136)

    So we must not add edge from

    (2,6)

    OR

  • The length of the shortest path from node

    1 to the deeper node will no longer be the same (might contradicts the 3rd condition because
    didi+1
    must holds)

    Illustration :

    Image Not Showing Possible 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
    Learn More →

    Take a look at this graph. If we add edge from

    (1,6) then the length of the shortest path from
    1
    to
    6
    will no longer becomes
    2


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 :

2(K2) or
2C(K,2)
where
K
is the number of nodes in this depth

The formula above can be obtained using the following :

  • There are
    K
    nodes on the same depth, therefore, there are
    (K2)
    pairs (or
    (K2)
    possible edges)
  • Out of those
    (K2)
    edges, we can choose whether or not to add that edges to the new graph, thus
    2(K2)

Based on the observations above, we can count the answer using the following :

  1. Build an array

    d of
    N1
    elements (i.e.
    d2,d3,,dN
    ) such that
    d2d3dN
    where
    d2=1

  2. To calculate the answer, we can use the following : Group some consecutive elements with the same value together in

    d for example :

    d=[1,1,1,2,2,3,3,3,3,4]

    Then we can group them as follows :

    d=[1,1,1k1,2,2k2,3,3,3,3k3,4k4]

    And then to calculate the number of edges, we can just count :

    2(k12)2(k22)2(kM2). In the example for
    d
    above, the number of edges are :

    2(32)2(22)2(42)2(12)
    =23212620

    =1024

So the next question is :

  • How to count the number of ways to construct
    d
    ?
  • For each of valid
    d
    , how many possible tree that can be constructed?

We will answer those questions in the next section


Counting ways to count trees when constructing
d

For a better understanding, take a look at the following tree graph below :

Image Not Showing Possible 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
Learn More →

From the following graph, the array

d can be seen here :

d=[d2,d3,d4,d5,d6,d7]
=[1,1,1,2,2,2]

Now let's assume we want to add node

8, so we want to put some numbers to
d8
, that is :

d=[1,1,1,2,2,2,(?)]

As you can see, the value of

d8(?) can be filled with either
2
or
3

  • If the value of
    d8
    is
    2
    , then this means node
    8
    can be placed under
    2,3,
    or
    4

Image Not Showing Possible 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
Learn More →

Image Not Showing Possible 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
Learn More →

Image Not Showing Possible 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
Learn More →

In any of these scenario, the value

d will become
[1,1,1,2,2,2,2]

As you can see, the number of ways to place node

8 is equal to the number of nodes that has
di=1
(that is node
2,3,4
)

  • If the value of
    d8
    is
    3
    , then this means node
    8
    can be placed under
    5,6,
    or
    7

Image Not Showing Possible 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
Learn More →

Image Not Showing Possible 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
Learn More →

Image Not Showing Possible 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
Learn More →

In any of these scenario, the value

d will become
[1,1,1,2,2,2,3]

As you can see, the number of ways to place node

8 is equal to the number of nodes that has
di=2
(that is node
5,6,7
)


From the observation, we can define this following

dp function :

Define

dp(i,len,len2) as follows :

The number of ways to construct array

d such that :

  • We currently want to fill
    i
    th element
  • The previous consecutive
    d
    has a length of
    len
  • The previous consecutive before the previous consecutive
    d
    has a length of
    len2

For example, in the illustration above when we have filled

d=[1,1,1,2,2,2], then when we want to fill
d8
, the
dp
state would be :

dp(8,3,3) because :

  • i=8
    . We currently want to fill
    8
    th element
  • len=3
    . The previous consecutive elements are
    [2,2,2]
    has the length of
    3
  • len2=3
    . The previous consecutive elements before it are
    [1,1,1]
    has the length of
    3

Then we can calculate the value of

dp(i,len,len2) using this transition

  • Transition 1 : Placing

    di=di1
    We can place
    i
    th node in
    len2
    ways. so :
    len2dp(i+1,len+1,len2)

  • Transition 2 : Placing

    di=di1+1 :
    We can place
    i
    th node in
    len
    ways, and we're closing the consecutive
    len
    elements together, so we can add edges from the same depth (see observation 3) so :
    len2(len2)dp(i+1,1,len)

Therefore

dp(i,len,len2)=(len2dp(i+1,len+1,len2))transition 1+(len2(len2)dp(i+1,1,len))transition 2

And for the base case :

  • if(i>n)
    , then
    dp(i,len,len2)=2(len2)
    (because we have to count the last consecutive
    len
    elements that we have placed after we have placed all elements)

Some Optimization on Implementation

  • Memory Complexity :
    The memory complexity uses

    O(N3) due to the 3 DP states. It can be optimized to
    O(N2)
    if we use a bottom-up DP with flying table

  • Time Complexity :
    The time complexity of this approach is

    O(N3) because we have 4 unique DP states and can be "prune" by limiting the upper bound of
    len
    and
    len2
    into the following pseudocode:

    ​​​​for(int i=1; i<n; i++){
    ​​​​    for(int len=0; len<=n-i; len++){
    ​​​​        for(int len2=0; len2<=n-len; len2++){
    ​​​​            // the DP here
    ​​​​        }
    ​​​​    }
    ​​​​}
    

    My solution uses the bottom-up + flying table DP approach and runs in 15ms with memory usage of 216KB
    Screenshot 2024-02-05 at 19.01.42


Implementation

# include <bits/stdc++.h> using namespace std; typedef long long ll; # define int long long # define For(i, n) for(int i=0; i<n; i++) # define Fori(i, n) for(int i=1; i<=n; i++) # define Each(x, v) for(auto x : v) const int mod = 998244353; int add(int a, int b) { return (a+b) % mod; } int sub(int a, int b) { return (a-b+mod) % mod; } int mul(int a, int b) { return (a*b) % mod; } int pw(int a, int b){ if(b == 0) return 1; int t = pw(a, b/2); if(b%2 == 0) return mul(t, t); return mul(a, mul(t,t)); } int p2[5005]; void precompute(){ p2[0] = 1; for(int i=1; i<=5000; i++){ p2[i] = mul(p2[i-1], 2); } } int n; int dp[2][105][105]; signed main(){ ios_base :: sync_with_stdio(false); precompute(); cin >> n; for(int len=0; len<=n; len++){ for(int len2=0; len2<=n; len2++){ dp[0][len][len2] = p2[len * (len-1)/2]; } } for(int i=1; i<n; i++){ for(int len=0; len<=n-i; len++){ for(int len2=0; len2<=n-len; len2++){ int res = 0; int ways1 = len2; ways1 = mul(ways1, dp[(i-1)%2][len+1][len2]); res = add(res, ways1); int ways2 = p2[len * (len-1)/2]; ways2 = mul(ways2, len); ways2 = mul(ways2, dp[(i-1)%2][1][len]); res = add(res, ways2); dp[i%2][len][len2] = res; } } } cout << dp[n%2][1][1] << endl; }