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
Try with
5 5 5 7 8
With this testcase my program gives
4
but it is clear that the answer is0
. So it is obvious that my approach is wrong. So can you suggest an improvement.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.
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!
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.
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?
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
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.
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
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!
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<<j? this will help those who are trying to understand the solution
first try this
then try this
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.
Hi, I had initially thought of this solution, but wasn't able to convince myself that it would not TLE. If I'm right, 2^20 operations max on the loop comes out around 1e7. So, won't that lead to a TLE? (since only upto 1e6 time is the threshold?)
No. Max operations allowed is more than 1e7 and less than 1e8 so around 1e7. That's why 1e7 is allowed in most of the circumstances.
Thank you so much for clarifying that!