I am trying to solve this problem for almost a month now but have had no success. Can someone give me a hint (not entire solution) to solve this problem?

Thanks in advance,

Animesh.

I am trying to solve this problem for almost a month now but have had no success. Can someone give me a hint (not entire solution) to solve this problem?

Thanks in advance,

Animesh.

2 Likes

The obvious first step is to sort all the elements because their order doesn’t matter.

Suppose we’ve fixed L and H, let x be the number of elements <= L which are changed to L and x1 be the number of elements > L which are changed to L. Similarly let y be the number of elements >= H which are changed to H and y1 the number of elements < H which are changed to H.

Let dL be the increase in cost if we increase L by 1 and dH be the increase in cost if we decrease H by 1.

dL = x-x1 and dH = y-y1

Try to prove that there has to be an optimial solution where dL == dH.

4 Likes

Thank you for the prompt reply.

1 Like