Блог пользователя gur_chella

Автор gur_chella, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem source?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

      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