| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 7 | SecondThread | 150 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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.
I think you might have been confusing (contiguous) subarray with (discontiguous) subsequence.
Use 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.
Thanks a lot! I understood it. I will try to code this up.
Can the given problem be solved if subarray is replaced with subsequence?
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:
Sorry for not providing too much more detail, I still haven't come back to the problem to figure its nuts and bolts.
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)
UPD:Got it !
Thanks a lot for the solution and the code!