### toxic_hack's blog

By toxic_hack, history, 10 days ago, ,

The problem is very simple:

Count the number of permutations of length $N$ where the maximum length of an increasing subarray is exactly $K$.

where: $1 \leq K \leq N \leq 200$.

I am stuck in this problem for days. It would be really great if someone could help me out here.

• +15

 » 10 days ago, # |   +32 I think you might have been confusing (contiguous) subarray with (discontiguous) subsequence. SolutionUse dynamic programming: $dp(i, j, k)$ is the number of solutions (in the $\leq K$ scenario, see below), having chosen $i$ elements, the current increasing subarray has length $j$ and $k$ elements of the remaining $n-i$ are strictly smaller than the last element chosen. Recurrence should be pretty straightforward, although it might need some partial sums to run in cubic time. In order to compute the answer, run this dp with the constraint that $j \leq k$ and with $j \leq k-1$ and subtract the results.
•  » » 10 days ago, # ^ |   0 Thanks a lot! I understood it. I will try to code this up.
•  » » 10 days ago, # ^ |   0 Can the given problem be solved if subarray is replaced with subsequence?
•  » » » 9 days ago, # ^ |   +8 There should be a solution in $O(\pi(n))$, where $\pi$ is the partition function, so it could work good for $n \leq 75$. The solution is from Petrozavodsk Winter 2020 problem Disjoint LIS (link here, but I think it's general enough to be applied to this problem as well:Fix the shape $\lambda$ of some Young tableaux. It can be proven (although I haven't quite understood the proof) that the number of permutations for which the LIS algorithm yields this Young tableaux shape is $f(\lambda)^2$, where $f(\lambda)$ is the number of ways to put values inside this tableaux so that rows and columns are increasing.So a solution would sound like: Fix a partition of $N$ where the biggest element equals $M$ Calculate $f(\lambda)$ the number of ways to put values $1, 2, ..., N$ in a Young tableaux of this shape Add $f(\lambda)^2$ to the answer Sorry for not providing too much more detail, I still haven't come back to the problem to figure its nuts and bolts.
 » 10 days ago, # |   +14 This can be solved in O(N4) using dp. DP state is this : dp[number of elements in permutation][last element][ending longest increasing subarray length][current longest increasing subarray]. I'm using forward dp for this problem. Say we're at a current state dp[i][j][k][l]. We will iterate over the next element which has to be added at the end (say m). If m > j, our current longest ending subarray length will increase by 1, and new maximum longest subarray would be max(k + 1, l). If m <= j, the ending longest increasing subarray will become 1. Doing this naively would yield complexity O(N5), with O(N) transition. To speed it up, we use prefix sums with O(1) transition. Code : Link O(N5) Code : Link O(N4)
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 UPD:Got it !
•  » » 10 days ago, # ^ |   0 Thanks a lot for the solution and the code!