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...
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