### gur_chella's blog

By gur_chella, history, 10 months ago, ,

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

 » 10 months ago, # |   0 Problem source?
•  » » 10 months ago, # ^ |   0 https://www.hackerearth.com/challenge/hiring/Pocket-Aces-software-hiring-challenge/ The 3rd question on this one. Unfortunately I am not able to access the questions now.
 » 10 months ago, # |   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.
 » 10 months ago, # |   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).
•  » » 10 months ago, # ^ |   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?
•  » » » 10 months ago, # ^ | ← Rev. 3 →   +14 He means following:Let dp[i][j] be max score which we can achieve by distributing first i elements into j groupsThen 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
•  » » » » 10 months ago, # ^ |   0 Oh I get it now. Thanks!