First sort the array. Then can be solved in O(n*k) using dp state as (i,k) which calculates the contribution of elements from i to n , given k out of K are chosen already before i. Contribution of element i is : (i) k*a[i] - (K - k)*a[i] if ith element isnt included in set I coz to the left of it we have k elements lesser and to the right we have (K - k) elements greater (ii) (i - 1 - k)*a[i] - (n - i - (K - k - 1))*a[i] if ith element is included in set I, coz to the left we have (i - 1 - k) elements that belongs to J, lesser than it and (n - i - (K - k -1)) elements to the right that belong to J

can you explain how this problem is satisfying optimal substructure property

Refer the link - http://qr.ae/T2VCbj

Credits - Anubrata Das Sarma

There seems to be a simple solution.

First sort the into ascending order.

Since the roles of Li and Lu are symmetric, we may assume . If not, replace by .

Now let , and . This is a minimally unfair solution, and we can compute in time with a single pass through the to compute the contribution of each to .

To prove this, we begin with three assumptions:

• The are sorted into ascending order.
• The are distinct; when .

The first two assumptions are safe. We will remove the third assumption later.

Given a candidate set of indices , let and . When is obvious, we write simply and .

Given and an integer with such that but , let . Then

If is a minimally unfair candidate set with and , then we must have . Since , this implies . But actually we can remove the condition that :

Whenever is a minimally unfair candidate set of indices and , , then .

To prove this, we consider two cases. First, if whenever , then . Otherwise, choose the smallest such that and . Then .

By similar reasoning, we can show that if is a minimally unfair candidate set of indices and , , then either or . Note that the form of the conclusion is a bit weaker in this case.

Now define as follows: for each , if and only if and .

This is a recursive definition, but since and depend only on the presence or absence of in , it is well-defined. In fact, it is the same as the defined at the beginning of this comment.

Suppose is not minimally unfair; there is some with . Then there is some such that for every such , . Choose the smallest such , and some such that .

It then follows that and . We will now derive a contradiction.

• If , then and .
• If and , then and .
• If and , then and .
• If and , then because and by the construction of . Hence , by the choice of and . Then , so , so . Let . Then , so from the equations above and , it follows that . This contradicts the choice of .

This completes the proof for the case when the are distinct. What if for some ?

For each , choose a real number very close to , say , such that the are all distinct. Given a set of indices , define analagously to , but using the instead of the . Then will be a real number very close to , certainly .

The above argument for the case of distinct does not depend on the being integers; it also applies to real numbers. So the constructed above will provide the minimal value for . But since and are always so close, and is always an integer, this means the constructed above also provides the minimal value for .

did anybody understood the editorial for this question ?