Alex7's blog

By Alex7, 11 years ago, In English

Hello guys, I need some help with this problem.. spoj.com/problems/MHLAR10 I tried to solve it this way: After checking if a solution exists, I compress all values and then sort them (if a begining and an end are equal, I put the begining first)

dp[i][k]: is the number of ways we can cover the interval [1...i] using an interval that ends in k (k<i) so dp[i][k]=sum (j=i-1 .... j=1) dp[k][j] getting WA my solution fails 8 test cases of 435. Help me please...

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

»
11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I got AC for this problem with DP O(n^3), not sure if there is O(n^2) solution exists. My idea is below :

Consider dp(L,R) is number of ways to construct a minimal subset which last interval is [L,R], inclusive. We will choose one interval [lo,hi] to "connect" to the left (L,R) so that they make a valid minimal subset.

The valid minimal subset now looks like : ... + [lo,hi] + [L,R]

It's easy to find the condition of [lo,hi] is : lo < L && L <= hi && hi < R

After choose [lo,hi], now the last interval would be [ lo, min(L,hi) ].

The base case is when L = 0 which gives answer = 1, since we have only one way to start our set.

Here is my code : http://ideone.com/4f8gLg