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.
Hey karbish98 here is the solution to your question
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.
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?
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);
#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;
}
}
