toxic_hack's blog

Help needed in this DP problem
By toxic_hack, history, 4 years ago, In English

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.

LINK

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

I think you might have been confusing (contiguous) subarray with (discontiguous) subsequence.

Solution
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! I understood it. I will try to code this up.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can the given problem be solved if subarray is replaced with subsequence?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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)

→ Reply