You are not logged in. Please login at www.codechef.com to post your questions!

×

MAXDIFF - Editorial

1
2

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.

This question is marked "community wiki".

asked 15 Apr '13, 15:00

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.6k62119138
accept rate: 12%

wikified 15 Apr '13, 15:39


link

answered 29 Mar '16, 22:46

karbish98's gravatar image

2★karbish98
191
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★

for which case my this submission got WA ?

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

link

answered 27 Feb '15, 10:43

rofi93's gravatar image

4★rofi93
21
accept rate: 0%

link

answered 28 Aug '16, 21:57

lucifer007's gravatar image

2★lucifer007
1
accept rate: 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.

link

answered 28 Aug '16, 23:31

srd091's gravatar image

4★srd091
1.5k111
accept rate: 40%

Yes I understood it later , thanks anyway :)

link

answered 30 Aug '16, 09:54

lucifer007's gravatar image

2★lucifer007
1
accept rate: 0%

For which case is the solution giving wa--

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

pls someone explain ?

link

answered 21 Sep '16, 16:43

cvarma21's gravatar image

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; }

link

answered 05 Jan, 18:47

ayushgupta1997's gravatar image

3★ayushgupta1997
1
accept rate: 0%

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

link

answered 30 Mar, 14:41

ayushgoyal1703's gravatar image

3★ayushgoyal1703
111
accept rate: 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<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?

link

answered 17 May, 19:04

akshaypatade_1's gravatar image

2★akshaypatade_1
1
accept rate: 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<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);


    }
link

answered 29 Jun, 16:27

highvibes's gravatar image

2★highvibes
1
accept rate: 0%

link

answered 01 Oct, 18:50

swapnil159's gravatar image

2★swapnil159
1
accept rate: 0%

link

answered 14 Oct, 10:13

lrsowmya's gravatar image

0★lrsowmya
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,590
×1,049
×716
×535
×15
×6

question asked: 15 Apr '13, 15:00

question was seen: 6,341 times

last updated: 14 Oct, 10:13