PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: TheScrasse
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
3045
PREREQUISITES:
Dynamic Programming
PROBLEM:
You are given two positive integers N and K.
- Consider a set S of segments, initially empty. For each i (1 \leq i \leq N-1) such that P_i \lt P_{i+1}, insert the segment [P_i, P_{i+1}] into S. Then, if you pick any subset of K segments of S, their intersection is empty.
Count the number of good permutations P_1, P_2,\dots, P_N. As the result can be very large, you should print it modulo 998\,244\,353.
EXPLANATION:
We classify each element P_i in the permutation in one of four categories: start point of some segment (i.e. P_i < P_{i + 1} and P_i < P_{i - 1}), end point of some segment (P_i > P_{i - 1} and P_i > P_{i + 1}), both start point and end point (P_{i - 1} < P_i < P_{i + 1}), and none (P_{i - 1} > P_i > P_{i + 1}). To help with the analysis, let P_0 = N + 1 and P_{N + 1} = 0. Notice that the structure of the permutation is as follow:
- Some none elements
- One start element
- Some both elements
- One end element
- Some none elements
and repeat.
Let’s construct the permutation as follow: we iterate values from 1 to N. For each value, we first choose its type (either start, end, both, or none), then insert it into the appropriate position in the current construction. Note that the construction doesn’t necessarily follow the previously mentioned structure of a final permutation (in particular, some start element might be “unclosed”, meaning that while it may be followed by some both elements, it is yet to be followed by the matching end element), but at the end the final construction should obey the structure. Because of this, we store an additional information on the current construction: the amount of unclosed start element. This has an added benefit: when we iterate by increasing values v, this amount of unclosed start element is the amount of segments in S that covers v - 1, so we can impose a restriction on this value being no more than K.
All of these ideas point to a dynamic programming solution: let f_{i, j} be the number of ways to construct the first i values (from 1 to i) such that there are j unclosed start elements. Our final answer should be f_{N, 0}. Iterating on the previous state f_{i - 1, j}, there are four ways to choose the role of the value i to be inserted:
- i is a none element. We can only insert i in j + 1 positions: either the very beginning of the permutation, or right after some unclosed start elements. The transition is f_{i, j} \mathrel{+}= f_{i - 1, j} \cdot (j + 1).
- i is a start element. Similarly, we can only insert i in j + 1 positions like the previous case, but j has to be less than k. The transition is f_{i, j + 1} \mathrel{+}= f_{i - 1, j} \cdot (j + 1) if j < k.
- i is a end element. We can only insert i in j positions (since i close off unclosed start elements). The transition is f_{i, j - 1} \mathrel{+}= f_{i - 1, j} \cdot j if j > 0.
- i is a both element. We can only insert i in j positions (after some unclosed start elements), but j needs to be less than k. The transition is f_{i, j} \mathrel{+}= f_{i - 1, j} \cdot j if j < k.
TIME COMPLEXITY:
Time complexity is O(N^2) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 2010
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll dp[maxn][maxn][2], f;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
if (m >= 2) dp[1][1][0] = 1;
dp[1][1][1] = 1;
for (i = 2; i <= n; i++) {
for (j = 1; j <= m; j++) {
for (k = 0; k <= 1; k++) {
dp[i][j][k] = 0;
if (j - k >= m) continue;
f = (j - k != m - 1);
if (j - 1 >= 0) dp[i][j][k] += ((j - k) * dp[i - 1][j - 1][k]);
dp[i][j][k] += ((j + f * (j - k)) * dp[i - 1][j][k]);
dp[i][j][k] += (f * j * dp[i - 1][j + 1][k]);
if (k - 1 >= 0 && j - 1 >= 0) dp[i][j][k] += dp[i - 1][j - 1][k - 1];
if (k - 1 >= 0) dp[i][j][k] += (f * dp[i - 1][j][k - 1]);
dp[i][j][k] %= mod;
// cout << i _ j _ k _ dp[i][j][k] << nl;
}
}
}
cout << dp[n][1][1] << nl;
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
ll dp[2001][2001];
int main(){
ios::sync_with_stdio(false);
int n,k;cin >> n >> k;k--;
dp[0][0]=1;
for(int i=1; i<=n ;i++){
for(int j=0; j<=min(i-1,k) ;j++){
if(j>0){//join
ll ways=j*j;
dp[i][j-1]=(dp[i][j-1]+dp[i-1][j]*ways)%mod;
}
if(j<k){//to right
ll ways=j;
dp[i][j]=(dp[i][j]+dp[i-1][j]*ways)%mod;
}
{//to left
ll ways=j+1;
dp[i][j]=(dp[i][j]+dp[i-1][j]*ways)%mod;
}
if(j<k){//new
ll ways=1;
dp[i][j+1]=(dp[i][j+1]+dp[i-1][j]*ways)%mod;
}
}/*
for(int j=0; j<=n ;j++){
cout << dp[i][j] << ' ';
}
cout << endl;*/
}
cout << dp[n][0] << '\n';
}
Editorialist's Solution
#include <bits/stdc++.h>
#include <atcoder/modint> //https://atcoder.github.io/ac-library/production/document_en/
using namespace std;
using namespace atcoder;
using mint = modint998244353;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k; k--;
vector<vector<mint>> dp(n + 1, vector<mint>(k + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= min(i - 1, k); j++) {
// not points of any segment
dp[i][j] += dp[i - 1][j] * (j + 1);
// start point of a segment
if (j + 1 <= k) {
dp[i][j + 1] += dp[i - 1][j] * (j + 1);
}
// end point of a segment
if (j > 0) {
dp[i][j - 1] += dp[i - 1][j] * j;
}
// end of one and start of another
if (j + 1 <= k) {
dp[i][j] += dp[i - 1][j] * j;
}
}
}
cout << dp[n][0].val();
}