SEQ1 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given K, a sequence of integers is called good if it contains some K consecutive integers.
For a permutation P, define f(P) to be the length of the shortest good prefix of P.
Given N and K, compute the sum of f(P) across all permutations of [1, N].

Here, \sum N^2 \le 2000^2.

EXPLANATION:

Suppose f(P) = M.
This means that the prefixes of P of lengths 1, 2, 3, \ldots, M-1 are all not good, while the prefix of length M is good.
Once the length M prefix is good, all longer prefixes will also certainly be good.

So, f(P) can be said to equal the number of prefixes of P that are not good, plus 1.
If we allow for the empty prefix as well, which is never good, f(P) simply equals the number of prefixes of P that are not good.

This perspective allows us to rewrite “sum of f(P) across all P” as follows:

  • For each subset of \{1, 2, \ldots, N\} that’s not good, count the number of permutations that contain exactly this subset as a prefix.
  • The answer is then the sum of all these counts.

The first part is easy: for a subset of size x, there are x! \cdot (N-x)! permutations that contain the elements of this subset as a prefix.
This is because the elements of the subset can themselves be rearranged among the first x positions in any order, while the remaining (N-x) elements can be arranged among the remaining (N-x) positions in any order too.

So, if we are able to count the number of subsets of \{1, 2, \ldots, N\} that are not good, for each size x = 0, 1, \ldots, N (say, denoted c_x), then the answer would just be

\sum_{x=0}^N c_x \cdot x! \cdot (N-x)!

To compute the values of c_x, we’ll use dynamic programming.

For simplicity, a subset that’s not good will be called bad.
Let dp(i, j) denote the number of bad subsets of \{1, 2, \ldots, i\} with size j.
Note that c_x = dp(N, x) under this definition.

To compute dp(i, j), we look at the element i itself.
There are two possibilities: either i is present in the subset, or it is not.

If i is not present in the subset, then all j elements of the subset must come from the first i-1 elements instead.
There are thus dp(i-1, j) such subsets.

If i is present in the subset, then we must instead have j-1 elements from the first i-1 elements.
There are dp(i-1, j-1) such subsets.

However, we also need to ensure that there are no K consecutive elements in the subset.
Observe that this can’t happen in the first case (where i is not chosen) because dp(i-1, j) by definition counts only bad subsets.
In the second case however, it’s possible that we do run into issues - but the only case where we have K consecutive elements is if these K consecutive elements end at i itself, again because by definition of the DP, there can’t have been any violations till i-1.

So, the only violating case is when all the elements i, i-1, \ldots, i-K+1 are included, while i-K is not (otherwise there would already be K consecutive integers till i-1, which we know is not the case.)

That is, the subsets we want to remove look like: some bad subset of \{1, 2, \ldots, i-K-1\} followed by all of \{i-K+1, \ldots, i\}.
In particular, note that the bad part of \{1, 2, \ldots, i-K-1\} must have size exactly j-K; but beyond that doesn’t matter.

Thus, the number of subsets to subtract is exactly dp(i-K-1, j-K), i.e. all bad subsets of the first i-K-1 elements with size j-K.
Note that this is with the understanding of the dp being 0 if either input parameter is negative.

So, we obtain the simple recurrence

dp(i, j) = dp(i-1, j) + dp(i-1, j-1) - dp(i-K-1, j-K)

Depending on implementation, there is one final edge case: if i=j=K then make sure to subtract 1 to account for the subset \{1, 2, \ldots, i\}.

In any case, this gives us a DP with \mathcal{O}(N^2) states and constant time transitions from each, for quadratic time overall.
Since \sum N^2 is bounded by 2000^2 in this version, this is fast enough.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (C++) 
// #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<int> fac(2005, 1);
    for (int i = 1; i < 2005; ++i) fac[i] = (fac[i-1] * 1ll * i) % mod;

    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        vector dp(n+2, vector(n+1, 0));
        dp[0][0] = dp[1][0] = 1;
        for (int i = 2; i <= n+1; ++i) {
            for (int j = 0; j <= i-1; ++j) {
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % mod;
                if (j >= k) dp[i][j] = (dp[i][j] + mod - dp[i-k-1][j-k]) % mod;
            }
        }

        int ans = 0;
        for (int i = 0; i <= n; ++i) {
            int mul = (1ll * fac[i] * fac[n-i]) % mod;
            ans = (ans + 1ll * dp[n+1][i] * mul) % mod;
        }
        cout << ans << '\n';
    }
}
1 Like
SEQ2 - Editorial