MAXDIFF question problem?

https://www.codechef.com/viewsolution/9766474 why is this wrong…

Somebody asked that his solution failed and I’m posting the answer for that as it has very less Karma to ask the questions?

@karbish98 error in your solution is that you are only taking first k items as group to be held by chef’s son so you are missing that if first K group can be large and would be held by son which is not right, so as per correct solution and editorial you need to check both whether first group is more heavy or the second …

also as per in editorial you should check and print as per:

1:Sort all numbers.
2:Find the sum of all numbers. Let it be S.
3:Find the sum of first K numbers. Let it be S1.
4:Find the sum of last K numbers. Let it be S2.
5:Output max(abs(S1 − (S − S1)), abs(S2 − (S − S2))) as an answer.
Also editorail link is:editorial

I have upvoted your question which was posted in answers so that you can now ask question on your own. :slight_smile:

I am confused.
max(abs(S1 − (S − S1)), abs(S2 − (S − S2))= max(abs(S1 − (S1+S2 − S1)), abs(S2 − (S1+S2 − S2))
= max(abs(S1 − S2), abs(S2 − S1))=abs(S1-S2)
Please correct me if I am wrong

Question says that Chef wants his son to carry pile of least items. Thus if k>(n-k).

Then you need to do k=n-k.

Thus just add a line and get green tick.

if(k>(n-k))

k=(n-k);

And then find the sum.

Also you can simply output (total sum)-2*(sum of least k elements).

Link to my AC code for reference

Hope it helps

@jain_mj

If we have sorted the array then obviously the sum of first k elements will be smaller than sum of last k elements. so this solution should be correct.

Based on the explanations by other users. ‘K’ items will have more weight if K>(N-K). It is possible. So, ‘K’ will be heavier. In these cases, we should change the ‘K’ value to ‘N-K’ i.e; K = N-K and this group should be given to Son. This is not obvious from the problem but it says 1 group should have ‘K’ items. In this case, it is. But here, ‘K’ items (which is heavier group) are carrying by Dad instead of Son.

1 Like