SHUFFLEEZ - 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:

Elementary Combinatorics

PROBLEM:

For a permutation P and a fixed K, define f(P) as the array obtained by doing the following:

  • For i = 1, 2, 3, \ldots N-K+1, sort the subarray P[i, i+K-1] in ascending order, in-place.

Given N and K, count the number of permutations P for which f(P) = [1, 2, \ldots, N].

EXPLANATION:

Let’s look at the value 1, which must end up at position 1 of f(P).
The only subarray that affects the first position is P[1, K].
We want 1 to appear in position 1 in the end; which means surely 1 must appear in one of positions 1, 2, \ldots, K of P.

It doesn’t matter which of these positions it appears in - since we sort P[1, K] and 1 is the smallest value for sure, as long as it appears among the first K positions it will end up at position 1 of f(P).
So, there are K positions where 1 can appear.

Next, we look at value 2.
By similar reasoning, 2 should be among positions 2, 3, \ldots, K+1 after P[1, K] has been sorted.
Obviously, it can’t be at position 1 after the sorting (that’s occupied by value 1); and if it’s at a position \gt K+1 then it can’t be brought to position 2.

This is possible only if:

  • 2 was initially at one of positions 2, 3, \ldots, K+1, or
  • 2 was initially at position 1, and then gets pushed to position 2 after the first operation.

Put together, 2 must have been in some position among 1, 2, \ldots, K+1 initially.
Again, this is sufficient for it to end up at position 2.

How many choices do we truly have?
Well, there are K+1 available positions; but one position in [1, K] is already occupied by value 1 so really there are only K available positions.
We can choose any one of them.

It’s not hard to see that the same logic extends to any value x.
For value x to end up at position x, it must be initially present at some index in the range [1, x+K-1] (more precisely, the right bound is \min(N, x+K-1).)
If it’s beyond this range, it cannot be brought leftwards to reach position x; while if it’s in this range it will surely end up at position x (as long as the condition is satisfied for all smaller values as well.)

How many choices do we have for x?
Well, there are \min(N, x+K-1) positions available; but the values 1, 2, \ldots, x-1 have already been placed among them.
So, there are

\min(N, x+K-1) - (x-1)

available positions; all of which are valid choices independent of previous choices.

The answer is hence simply the product of this across all 1 \le x \le N.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
for _ in range(int(input())):
    n, k = map(int, input().split())
    q = list(map(int, input().split()))
    
    ans, rem = 1, k-1
    for i in range(1, n+1):
        if i+k-1 <= n: rem += 1
        
        ans = (ans * rem) % mod
        rem -= 1
    print(ans)