PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given an array A of length N containing each integer from 1 to N exactly once each, count the number of graphs for which A will be the DFS order.
The DFS must start at 1, and visits adjacent vertices in ascending order of label.
EXPLANATION:
Let’s understand how the given DFS works.
We start at vertex 1.
Now, suppose we delete vertex 1 from the graph (also delete all edges incident to it).
This will break the graph into several connected components.
What the DFS procedure given to us does is: choose the smallest unvisited neighbor of 1, and continue the DFS in the component containing it.
Once this component has been fully visited, once again choose the smallest unvisited neighbor of 1 and DFS into its component, and so on.
Note that in particular, each connected component obtained after the deletion of 1, will appear as a contiguous sequence in A - because all vertices in the component must be visited before moving to the next one.
The problem is, we don’t actually know what these components are - and the choice isn’t really unique, there can be many different partitions.
However, let’s try to understand what we can say about a certain partition into components.
Specifically, suppose we fix the components to be given by the subarrays [l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k].
Note that these must satisfy l_1 = 2, r_k = N, and l_i = r_{i-1} + 1, since every vertex (other than 1) must belong to a component.
One thing that we can say immediately, is that A_{l_1} \lt A_{l_2} \lt\ldots\lt A_{l_k} must hold.
This is because A_{l_i} is the first vertex visited in the i-th component; and neighbors of 1 are processed in ascending order.
Second, since these are separate components, there cannot exist any edges between vertices in different components.
That is, if u \in [l_i, r_i] and v\in [l_j, r_j] where i \lt j, the edge (u, v) cannot exist (otherwise they wouldn’t be separate components).
So, the components are quite disjoint, and don’t really interact with each other at all.
Finally, we need to look at which vertices can be adjacent to 1.
Clearly, all the A_{l_i} must be adjacent to 1.
However, some other vertices can be adjacent to it too - specifically, note that for the range [l_i, r_i], 1 can be adjacent to any vertex that’s larger than A_{l_i}.
This is because 1 can’t be adjacent to anything smaller because A_{l_i} is supposed to be the smallest neighbor of 1 in the component; and 1 can freely be adjacent to anything in the component larger than A_{l_i} because edges to 1 in the DFS are just going to be ignored anyway.
Other than that, there are no real other constraints: so we then just need to count the number of ways to solve for each component and multiply them.
For the component [l_i, r_i], this simply equals the number of connected graphs such that starting our DFS at A_{l_i} will result in the order [A_{l_i}, \ldots, A_{r_i}].
Observe that we’ve really just broken the original problem down into smaller problems of the same nature - which naturally suggests dynamic programming.
So, let’s define dp(L, R) to be the number of connected graphs such that running the DFS starting at A_L gives the order [A_L, \ldots, A_R].
Our goal is to compute dp(1, N).
Let’s now look at computing dp(L, R).
Since the “root” is A_L, what we want to do is partition the range [L+1, R] into subarrays representing the components (with the left endpoints of the subarrays being strictly increasing); though we don’t know how exactly yet.
Define f(L+1, R) to be the number of ways to partition [L+1, R] into separate components and solve for each one individually, while ensuring that the left endpoints of the partition are increasing.
We now move to computing f(L+1, R) instead.
One way to do this, is to fix the first subarray - suppose it’s [L+1, x].
Then,
- There are, by definition, dp(L+1, x) ways to make a connected component out of [L+1, x], starting at L+1.
- There are f(x+1, R) ways to partition the remaining part into subarrays.
However, this is only valid if A_{L+1} \lt A_{x+1}. If not, there are 0 ways instead.
So, simply iterating over x gives us a way to compute f(L+1, R) in linear time; recursively of course since it depends on dp and f calls to smaller ranges.
Thus, we have:
Now, we could just set dp(L, R) to f(L+1, R), but that misses one detail: recall that there can be edges from L to some vertices in [L+1, R] that are not subarray left endpoints; and it’s impossible to characterize those just from knowing f(L+1, R) since that depends heavily on the actual partition into components.
To account for this, let’s just store that information in f(L+1, R) as well.
To do this, recall that we computed f(L+1, R) by iterating L+1 \le x \le R as the right endpoint of the first component.
When doing this, for a fixed x, note that we simply get an additional 2^c options, where c is the number of elements in the range [L+1, x] that are \gt A_{L+1}.
Simply throw in this additional 2^c multiplier in the expression, so we obtain
Once this is done, we just have dp(L, R) = f(L+1, R).
Depending on how you implement this and which parts you choose to optimize, the complexity ranges from \mathcal{O}(N^3) to \mathcal{O}(N^5), all of which will be accepted.
Also, it can be seen from what we did above that having both the dp and f functions is redundant, since we just had dp(L, R) = f(L+1, R) anyway.
It’s thus possible to rewrite the transitions to just work with a single function, if you wish to.
TIME COMPLEXITY:
\mathcal{O}(N^3) \sim \mathcal{O}(N^5) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
const int mod = 998244353;
vector p2(1005, 1);
for (int i = 1; i < 1005; ++i)
p2[i] = 2ll * p2[i-1] % mod;
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector a(n, 0);
for (int &x : a) cin >> x;
vector split(n, vector(n, 0));
vector dp(n, vector(n, 0));
// split[l][r] = ways to split [l, r] into subarrays with increasing first element, along with edges to root
// dp[l][r] = ways to form a valid graph out of [l, r] with l as root
for (int i = 0; i < n; ++i) {
split[i][i] = dp[i][i] = 1;
}
for (int len = 2; len <= n; ++len) {
for (int l = 0; l+len <= n; ++l) {
int r = l+len-1;
dp[l][r] = split[l+1][r];
int ch = 0;
for (int i = l; i <= r; ++i) {
ch += a[i] > a[l];
int nxt = n+1;
if (i+1 <= r) nxt = a[i+1];
if (a[l] > nxt) continue;
if (i+1 <= r) split[l][r] = (split[l][r] + 1ll * split[i+1][r] * dp[l][i] % mod * p2[ch] % mod) % mod;
else split[l][r] = (split[l][r] + 1ll * dp[l][i] * p2[ch]) % mod;
}
}
}
cout << dp[0][n-1] << '\n';
}
}