### toxic_hack's blog

By toxic_hack, history, 3 years 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.  Comments (7)
 » 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.
•  » » » 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.