MAXDIFF - Editorial

editorial
, , , , ,
#1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Greedy algorithm, Sorting algorithms

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.

5 Likes
#2

for which case my this submission got WA ?

submission: http://www.codechef.com/viewsolution/6355868

#3

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

3 Likes
#4

why does it give WA? https://www.codechef.com/viewsolution/11273738

#5

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

#6

Yes I understood it later , thanks anyway :slight_smile:

#7

For which case is the solution giving wa–

https://www.codechef.com/viewsolution/11583814

pls someone explain ?

#8

#include
using namespace std;
#include
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<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;
}

#9

https://www.codechef.com/viewsolution/13185103
please tell me what is wrong?

#10

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<lst[1]):
child+=weights[i]
else:
chef+=weights[i]
print(chef-child)
testcase-=1

Can anybody will tell me why am i getting wrong answer?

#11

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<n;i++)
a[i]=sc.nextInt();
Arrays.sort(a);

		int chef=0;
		int child=0;
		if(n-k>=k)
		{
			for(int i=0;i<k;i++)
				child=child+a[i];
			for(int i=k;i<n;i++)
				chef=chef+a[i];
		}
			else
			{
				for(int i=0;i<n-k;i++)
					child=child+a[i];
				for(int i=n-k;i<k;i++)
					chef=chef+a[i];
			}
			System.out.println(chef-child);
			
		
	}
#12

https://www.codechef.com/viewsolution/15576532

why is this getting WA

#13

https://www.codechef.com/viewsolution/15820847

Why am I getting WA?

#14

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int i,n,k;
long long int c=0,d=0;
cin>>n>>k;
long int a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
int m=sizeof(a)/sizeof(a[0]);
sort(a,a+m);
for(i=0;i<k;i++)
{
c+=a[i];
}
for(i=k;i<n;i++)
{
d+=a[i];
}
int r=((c>d)?(c-d):(d-c));
cout<<r<<endl;
}
}

why i am getting WA

1 Like
#15

Guys, help me please. Why my solution gets WA? I am sure that it my solution is correct! https://www.codechef.com/viewsolution/21715217

#16

my approach:-

  1. sort the entire array of weights and find the total sum of all elements (let’s denote by S)
  2. find total sum of first k elements in the sorted array (let’s denote it by S0)
  3. max difference will be (S-S0)//fathers weight - (S0) //child weigth

can’t quite find the error in this
what am I missing ?

#17

why is this showing wrong answer?

https://www.codechef.com/viewsolution/23613827

#18

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.

#19

Consider test case:

1 2 3 4 5 6 7 8 9 10 , k = 8 , n = 10

There are two possibilities:

case 1 index(0:k and k:):

group 1: [1,2…8] sum = 36

group 2: [9,10] sum = 19

diff_case1 : 17

case 2 index (0:n-k and n-k:):

group1: [1,2] sum = 3

group2: [3,4…10] sum = 52

diff_case2: 49

output: max(diff_case1,diff_case2) = 49

Here is the Python code:

for _ in range(int(input())):
n,k = map(int,input().split())
l = sorted(list(map(int,input().split())))
print(max(abs(sum(l[:k])-sum(l[k:])),abs(sum(l[:n-k])-sum(l[n-k:]))))
3 Likes
#20

/*

  • cc_practise_maxdiff.cpp
  • Created on: Aug 19, 2019
  •  Author: ankit

*/

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
int t, n, k;
ull sum, sum_k, sum_nminusk;
cin >> t;

vector<int> wt(101,0);
while(t--){
	sum =0;
	sum_k = 0;
	cin >> n >> k;
	for(int i=1 ; i<= n ;i++){
		cin >> wt[i];
		sum += wt[i];
	}
	sort(wt.begin()+1, wt.begin()+1+n);
	for(int i = 1; i <= k ;i++){
		sum_k += wt[i];
	}
	sum_nminusk = sum - sum_k;
	if(k > n-k){
		// implies sum of k elements might be
		// greater than sum of n-k elements
		// so in such case assign child n-k elements
		if(sum_k > sum_nminusk){
			cout << sum_k - sum_nminusk << "\n";
			continue;
		}
	}
	cout << sum_nminusk  - sum_k << "\n";
}
return 0;

}

Can anyone please tell me the test case where my code fails to give correct output ??