gur_chella's blog

Dynamic Programming question
By gur_chella, history, 6 years ago, In English

Recently I came across such a question: You have to divide an array into k segments, and the resultant score of each segment is the number of pairs (i,j) such that i<j and a[i]>a[j]. For example, the score of [9,1,7,3,2] will be 7 since the following pairs can be formed: {9,1},{9,7},{9,3},{9,2},{7,3},{7,2},{3,2}. Now our task is to maximize the sum of scores of the resultant segments. The k segments can be formed only using continuous elements of the array. The constraints are:
1<=a[i]<=10**6 1<=n<=500 1<=k<=n
I was thinking of a dp solution to this, where dp[i][j][len] stores the answer we can get after we reach the ith index, which belongs to the jth group of length len. Hence I declared an array dp[505][505][505]. The base case would be simply the following: And at each element we make the choice of ending a group or not 

if(idx==n)
{
     if(grp==k-1)//since we need k groups so this is the first and last element of the kth group
        return 0;
     if(grp==k)
          return answer_for_this element_using_array_length_len
    return -infinity
}

How do I make this approach better? I used a sorted segment tree to find number of elements that are greater than A[i] and in the range of i-len to i. Can it be made more memory efficient(since it was partially accepted and I got memory limit exceeded via this method) or is there a non dp solution to this? Or is a 3d dp state not required?Thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem source?

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

I think dp state should be dp[i][j] where this state stores the best answer if the last element of ith segment is at jth position.

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

Approach looks solid. you might need to precompute the number of inversions for each subarray to speed it up. In addition, you only need to store two variables for your state (I'm not sure why len matters).

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

    If we dont store len how are we going to know the answer for the ith element? For example, right now my function goes as: ll rdx=answer_for_this_group + max(f(idx+1,grp+1,1),f(idx+1,grp,len+1)). If I dont know the length, how will I compute answer_for_this_group?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +14 Vote: I do not like it

      He means following:
      Let dp[i][j] be max score which we can achieve by distributing first i elements into j groups
      Then recurrence is: dp[i][j] = max(dp[t][j - 1] + f(t + 1, i)) where: j - 1 ≤ t < i and f(l, r) is number of inversions in segment [l, r]
      In order to optimize this solution you should previously compute f[l][r] over all l ≤ r, overall with trivial implementation, you can achieve O(n3) which seems to be enough, since n ≤ 500

      → Reply