# Editorial - Constructor 2024 - Practice Round
## Problem L - Roads
### Editorial by : fonmagnus

### Abridged Problem Statement

Count how many ways to construct a graph of $N$ $(2 ≤ N ≤ 100)$ 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 $d_i$ is the shortest path from node $1$ to node $i$, then the following condition **must** be true : $d_2 ≤ d_3 ≤ \ldots ≤ d_N$
- 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 :


The following tree is **NOT** a valid tree graph :


Because $d_6 > d_7$

---

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 4^th condition because there must be **exactly** one shortest path from $1$ to all other nodes)

Illustration :


Take a look at this graph. If we add edge from $(2, 6)$, then there are two different shortest path from $1$ to $6$ :
- $(1 \rightarrow 2 \rightarrow 6)$
- $(1 \rightarrow 3 \rightarrow 6)$

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 3^rd condition because $d_i ≤ d_{i+1}$ must holds)

Illustration :


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 3^rd or 4^th 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^{\binom{K}{2}}$ or $2^{C(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 $\binom{K}{2}$ pairs (or $\binom{K}{2}$ possible edges)
- Out of those $\binom{K}{2}$ edges, we can choose whether or not to add that edges to the new graph, thus $2^{\binom{K}{2}}$

---

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

1. Build an array $d$ of $N-1$ elements (i.e. $d_2, d_3, \ldots, d_N$) such that $d_2 ≤ d_3 ≤ \ldots ≤ d_N$ where $d_2 = 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 = [\underbrace{1, 1, 1}_{k_1}, \underbrace{2, 2}_{k_2}, \underbrace{3, 3, 3, 3}_{k_3}, \underbrace{4}_{k_4}]$

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

$2^{\binom{k_1}{2}} \cdot 2^{\binom{k_2}{2}} \cdot \ldots \cdot 2^{\binom{k_M}{2}}$. In the example for $d$ above, the number of edges are :

$2^{\binom{3}{2}} \cdot 2^{\binom{2}{2}} \cdot 2^{\binom{4}{2}} \cdot 2^{\binom{1}{2}}$
$= 2^3 \cdot 2^1 \cdot 2^6 \cdot 2^0$
$=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 :


From the following graph, the array $d$ can be seen here :

$d = [d_2, d_3, d_4, d_5, d_6, d_7]$
$= [1, 1, 1, 2, 2, 2]$

Now let's assume we want to add node $8$, so we want to put some numbers to $d_8$, that is :

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

As you can see, the value of $d_8 (?)$ can be filled with either $2$ or $3$

- If the value of $d_8$ is $2$, then this means node $8$ can be placed under $2, 3,$ or $4$


In any of these scenario, the value $d$ will become $[1, 1, 1, 2, 2, 2, \underline{2}]$

As you can see, the number of ways to place node $8$ is equal to **the number of nodes that has $d_i = 1$ (that is node $2, 3, 4$)**

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


In any of these scenario, the value $d$ will become $[1, 1, 1, 2, 2, 2, \underline{3}]$

As you can see, the number of ways to place node $8$ is equal to **the number of nodes that has $d_i = 2$ (that is node $5, 6, 7$)**

---

From the observation, we can define this following $dp$ function :

Define $dp(i, len, len_2)$ 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 $len_2$

For example, in the illustration above when we have filled $d = [1,1,1,2,2,2]$, then when we want to fill $d_8$, 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$
- $len_2 = 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, len_2)$ using this transition

- Transition 1 : Placing $d_i = d_{i-1}$
We can place $i$^th node in $len_2$ ways. so :
$len_2 \cdot dp(i+1, len+1, len_2)$

- Transition 2 : Placing $d_i = d_{i-1}+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 :
$len \cdot 2^{\binom{len}{2}} \cdot dp(i+1, 1, len)$

Therefore $dp(i, len, len_2) = \underbrace{(len_2 \cdot dp(i+1, len+1, len_2))}_{\text{transition 1}} + \underbrace{(len \cdot 2^{\binom{len}{2}} \cdot dp(i+1, 1, len))}_{\text{transition 2}}$

And for the base case :

- $\text{if}(i>n)$, then $dp(i, len, len_2) = 2^{\binom{len}{2}}$ (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(N^3)$ due to the 3 DP states. It can be optimized to $O(N^2)$ if we use a bottom-up DP with flying table

- Time Complexity :
The time complexity of this approach is $O(N^3)$ because we have 4 unique DP states and can be "prune" by limiting the upper bound of $len$ and $len_2$ 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

---

### 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;
}