×

# MAXDIFF - Editorial

Author: Vamsi Kavala
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

CAKEWALK

# PROBLEM:

You are given an array W[1], W[2], ..., W[N]. Choose K numbers among them such that the absolute difference between the sum of chosen numbers and the sum of remaining numbers is as large as possible.

# QUICK EXPLANATION:

There are two possibilities to try - K largest numbers and K smallest numbers (see below why). So the solution could be like this:

• Sort all numbers.
• Find the sum of all numbers. Let it be S.
• Find the sum of first K numbers. Let it be S1.
• Find the sum of last K numbers. Let it be S2.
• Output max(abs(S1 − (S − S1)), abs(S2 − (S − S2))) as an answer.

# EXPLANATION:

Consider the following sub-problem: choose K numbers with largest possible sum. Then the solution obviously is K largest numbers. So that here greedy algorithm works - at each step we choose the largest possible number until we get all K numbers.

In our problem we should divide the set of N numbers into two groups of K and N − K numbers respectively. Consider two cases:

• The group with largest sum, among these two groups, is group of K numbers. Then we want to maximize the sum in it, since the sum in the second group will only decrease if the sum in the first group will increase. So we are now in sub-problem considered above and should choose K largest numbers.

• The group with largest sum, among these two groups, is group of N − K numbers. Similarly to the previous case we then have to choose N − K largest numbers among all numbers.

This reasoning justify the solution in the QUICK EXPLANATION.

Regarding implementation details. Since N and T are small, then every simple O(N2) sorting algorithm from here will work. Other steps of the solution seems trivial to implement.

# ALTERNATIVE SOLUTION:

Let's go further and ask our self which of two above cases actually gives the answer. After short thinking it became clear that larger difference would be when more numbers are included to the group of largest numbers. Hence we could set M = max(K, N − K), find the sum of M largest numbers (let it be S1) and then the answer is S1 − (S − S1), where S is the sum of all numbers.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be provided soon.
Tester's solution can be found here.

# RELATED PROBLEMS:

Will be provided soon. All readers are welcomed to provide related problems in comments.

This question is marked "community wiki".

6.7k62119138
accept rate: 12%

 2 https://www.codechef.com/viewsolution/9766474 why is this wrong answered 29 Mar '16, 22:46 19●1 accept rate: 0% Hey karbish98 here is the solution to your question https://discuss.codechef.com/questions/80572/maxdiff-question-problem More over I have upvoted your question so that you can now ask question on your own and upvote and participate in codechef discuss and community rather that posting questions in answer column of editorials. (31 Mar '16, 11:30) jain_mj3★
 0 for which case my this submission got WA ? submission: http://www.codechef.com/viewsolution/6355868 answered 27 Feb '15, 10:43 4★rofi93 21 accept rate: 0%
 0 why does it give WA? https://www.codechef.com/viewsolution/11273738 answered 28 Aug '16, 21:57 1 accept rate: 0%
 0 @lucifer007 you just forget that if k>(n-k) then k will be replaced with (n-k). link of AC solution: https://www.codechef.com/viewsolution/11274212. answered 28 Aug '16, 23:31 5★srd091 1.6k●1●11 accept rate: 42%
 0 Yes I understood it later , thanks anyway :) answered 30 Aug '16, 09:54 1 accept rate: 0%
 0 For which case is the solution giving wa-- https://www.codechef.com/viewsolution/11583814 pls someone explain ? answered 21 Sep '16, 16:43 0★cvarma21 1 accept rate: 0%

# include <cstdio>

using namespace std;

# include <algorithm>

int main() { int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d",&n,&k); int arr[n]; for(int i=0 ; i<n ;="" i++)="" scanf("%d",&arr[i]);="" sort(arr,arr+n);="" int="" s1,s2;="" s1="s2=0;" for(int="" i="0;i&lt;n;i++)" {="" if((i+1)<="k)" s1+="arr[i];" else="" s2+="arr[i];" }="" int="" ans;="" if(s1="">s2) ans=s1-s2; else ans=s2-s1; printf("%d\n",ans); } return 0; }

16217
accept rate: 0%

 0 https://www.codechef.com/viewsolution/13185103 please tell me what is wrong? answered 30 Mar '17, 14:41 12●2 accept rate: 0%
 0 testcase=int(input()) while(testcase>0): child=0 chef=0 lst=[int(i) for i in input().split()] weights=[int(i) for i in input().split()] weights.sort() for i in range(0,len(weights)): if(i
 0 Can someone tell me why am I getting the wrong answer for this code while(t-->0) { int n=sc.nextInt(); int k=sc.nextInt(); int a[]=new int[n]; for(int i=0;i=k) { for(int i=0;i
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,473
×1,434
×876
×681
×15
×6

question asked: 15 Apr '13, 15:00

question was seen: 7,952 times

last updated: 29 May, 03:10