legar's blog

Help in this interesting dp Problem
By legar, history, 9 years ago, In English

You are given a list L of N integers. < 1000 Let's define an operation of cutting the list as follows: Suppose L = {l1, l2, ..., li, li+1, ..., lN}, then, cutting the list L at index i will split L into two nonempty sub-lists L1= {l1, l2, ...; li} and L2= {li+1, li+2, ..., lN}. Now, for each of sub-list Li, we can find the difference between the maximum value (Mi) and minimum value (mi) of Li and call it di. The task is to cut the list into K sub-list (1 ≤ K ≤ N) so that ans = d1+d2+....+dk, is minimized. Print ans. (1 ≤ K ≤ N ≤ 1000). The O(N*N*K) solution is very slow. Thanks.

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

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

Link to the question ?

→ Reply
»
9 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

In your problem it is clear that the brute force solution is dp[i][j] = the total minimal cost for the first i elements to split them in j sub-lists, and for that you fix the left side of your last list. O(n*n*k) There is an optimization that can transform you solution in O(n*k* logn ) , noticing than for your dimension j , once we iterate through all i s , the optimal left side for dp(i,j) is >= or <= then the left side for dp(i-1,j) . You can do a divide and conquer algorithm for all possible values of j. Last Edit : This solution doesn't work, you can brute force the left sides and the propery isn't satisfied :(

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

I know a solution in O(n*k) where the cost of list is maximum or minimum and it implies deque and dynamic, but combining those two does not sound good.Did you come up with this problem or it is from some archive/contest?(If you thought of it,there may be no faster solution than O(n*n*k)).

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

    This problem is from ACM-ICPC Thailand Southern Programming Contest 2012, I can't give you link to the problem because de OJ is no free for all people, but the O(n*n*k) solution is TLE.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This is the problemset for the contest that contains this problem (2012):D

Problem Link

I think you misunderstand the problem, the correct constraints are: 1 ≤ K ≤ N ≤ 400

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

    Yes, but number of cases is 120.

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

I think I have the solution. Multiply the array by -1 to transform the problem to calculate the maximum sum that can be obtained by adding or subtracting 2*k elements from the array, with the rule that in the pair of selected elements 2*i + 1 and 2*i + 2 (0 <= i < k), there is exactly one summed and one subtracted from the sum total. This new problem can be solved with a DP in O (N * K).

→ Reply