rain_0's blog

LIS with atmost k exceptions allowed
By rain_0, history, 4 years ago, In English

Given sequence of N integers, find the longest subsequence whose elements are ordered in an increasing order. Up to k exceptions that means at most k times, the next number in the sequence is smaller than previous one. Output should be the length of the longest such subsequence. In particular the question is a variant of LIS problem where at most k exceptions (restarts) are allowed.

Constraints:

3 <= N <= 10^6

1 <= K <= max{N-1,2000}

1 <= s[i] <=10^7

Time: 3 sec

Memory: 64 MB

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it +66 Vote: I do not like it

This can be solved in $$$\mathcal{O}(n \log^{2} n)$$$ with the aliens trick. You can see my answer to the same question at Computer Science Stackexchange: link

The answer isn't complete though, as I am not able to prove the concavity of the problem. Maybe someone else here can.

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

    Proof by AC

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

    We can have another DP: Let $$$Cost[i][j]$$$ be the length of LIS in the interval $$$[i, j]$$$. This problem is equivalent to partitioning an array with at most $$$k+1$$$ intervals to maximize the sum of the cost for each subarray. It is well known, that if $$$Cost[i][j]$$$ is Monge, then the DP value (hence the answer) is convex.

    Let's prove that $$$Cost[a][d] + Cost[b][c] \le Cost[a][c] + Cost[b][d]$$$.

    Consider a LIS from interval $$$[a, d]$$$ and $$$[b, c]$$$. We will rearrange them to form an increasing sequence in the interval $$$[a, c]$$$ and $$$[b, d]$$$. Consider a polygonal chain formed by two LIS. If there is no intersection, then we just split the LIS from $$$[a, d]$$$ to $$$[a, c], [c + 1, d]$$$ and append the latter to the LIS of $$$[b, c]$$$. Otherwise, we exchange two line segments at the intersection point.

    Thus, all solutions in the interval $$$[a, d]$$$ and $$$[b, c]$$$ is contained in a solution set of $$$[a, c]$$$, $$$[b, d]$$$, and the convexity is proved.

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

      Thanks, I added a proof to the answer. I was able to prove the concavity of Monge array partition by myself:

      concavity of Monge array partition
      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      What is monge?

      → Reply