### steelarm's blog

By steelarm, history, 15 months ago,

The problem

I am trying out the following approach:

1.I sort the array of weights in decreasing order and "put" the largest weight in one group.

2.Then I keep adding weights to the other group until it becomes larger.

3.Then I start adding apples to the first group until this is one is larger and again start putting apples in the other group and keep on going like this until i reach the end of the array.

4.And then I print the difference between the total weights of the two groups.

My solution gives the correct answer with the sample test cases and a few others too but I am getting a WA, so can anyone suggest something I can do to correct my code. Code:

#include <bits/stdc++.h>
using namespace std;

#define B begin()
#define E end()
#define I iterator
using pii = pair < int , int >;
using vi = vector < int >;
using llu = unsigned long long int;
using ll = long long int;

//ofstream cout ("op.txt");
//ifstream fin("inp.in");
int main ()
{
ll n;
cin >> n;
vector <ll> vec(n);
ll val;
for ( int i = 0 ; i < n ; i ++ ){
cin >> val;
vec[i] = val;
}
sort ( vec.B , vec.E , greater<ll>() );
ll ansa = 0 , ansb = 0 ;
ansa = vec[0];
for ( int i = 1; i < n ; i++ ){
if ( ansb < ansa )
ansb += vec[i];
else
ansa += vec[i];
}
cout << max( ansa , ansb ) - min( ansa , ansb );
return 0;
}



Any and all help is appreciated

• +4

 » 15 months ago, # | ← Rev. 2 →   0 Try with 5 5 5 7 8
•  » » 15 months ago, # ^ |   0 With this testcase my program gives 4 but it is clear that the answer is 0. So it is obvious that my approach is wrong. So can you suggest an improvement.
•  » » » 15 months ago, # ^ |   +10 It's not that your code is wrong, your whole idea doesn't work. This problem is hard to solve in general, you'll have to use the fact that $n \leq 20$ and make an exponential time algorithm.
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 So I will need to try out all the possibilities of the two sums so that their difference is minimum ? Anyway, thanks for the tip and I will surely implement this now. Now I realize that I should have taken the n <= 20 limit to mean that an exponential time algorithm was required.
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Finally!! I was able to solve the problem by designing an exponential-time algorithm , so thanks for all the help mango_lassi. Now, I just wanted to ask that should I update the post to reflect the fact that I have solved the question.
•  » » » » 6 months ago, # ^ |   0 Exponential time works, but is there a more optimal solution to this problem? I have been trying to think but I cannot think of anything more efficient!
•  » » » » » 6 months ago, # ^ |   0 This looks like a Knapsack but the fact that the range of numbers is big (aprox $2^{33}$) makes the algo slower than simply try all $2^n$ possible solutions.
•  » » » » 6 days ago, # ^ |   0 what is an exponential time algorithm?
•  » » 2 weeks ago, # ^ |   0 Hmm. I can't help but see that this problem is similar to Two Sets — https://cses.fi/problemset/task/1092/ However, this approach works there and passes all test cases. Can someone prove why this works there? And why does it not work here?
•  » » » 2 weeks ago, # ^ |   0 they are completely different problems that have different approaches? the solution for this problem should not work for Two Sets since the solution to this problem requires an exponential time solution while Two Sets requires a linear solution, and vice versa
•  » » » » 2 weeks ago, # ^ |   0 I'm sorry for not being clear. The approach that steerlam discussed in his blog, actually works for Two Sets. The problem of Two Sets itself is similar to this one in my opinion (disregarding the constraints and input size). The key difference is that the difference between the two groups should be zero instead of minimum.
•  » » » » » 2 weeks ago, # ^ |   0 the greedy approach taken in the blog works because in Two Sets, the numbers are 1, 2, ... n. you can prove that they work by looking at the two cases that work (n = 4k or n = 4k+3 for integers k) and proving this greedy approach through induction
•  » » » » » » 2 weeks ago, # ^ |   0 Thank you so much. I'm now working on a recursive solution to Apple Division.
 » 4 months ago, # | ← Rev. 2 →   0 As N is maximum 20 you can take all possible combinations of elements and put them in one group and put others in another group and check their difference. Maximum complexity will be 2^20 which is acceptable. Something like this:-for (ll i = 0; i < pow(2, n); i++) { ll sum1 = 0, sum2 = 0; for (ll j = 0; j < n ; j++) { if (i & 1 << j) sum1 += a[j]; else sum2 += a[j]; } min1 = min(min1, abs(sum1 - sum2)); }Hope it helps!
•  » » 6 days ago, # ^ |   0 you have written the code snippet but its difficult to understand what this code is doing like why u have used two loops? why you have wriiten pow(2,n)? why you have used the bit manipulation i&1<
•  » » » 6 days ago, # ^ |   0 I'm just using all possible combinations of size N from 0000...N times to 111...N times in binary form and for each number I check if which bit(i) is set and put Ai in one group and all indexes where there is 0 in another group. And take there difference.
•  » » » » 6 days ago, # ^ |   0 yes thank you got it.
 » 6 days ago, # | ← Rev. 2 →   0 hi,can i use dp here because this sum is similar to subset sum with minimum difference? subset sum with minimum diffi am using this concept but i am getting runtime error in 9 diff tc.EDIT: got it. its done
 » 5 days ago, # |   0 Here is my codehttps://cses.fi/problemset/result/819111/