CSES - Apple Division this is link to problem.
somebody please help me understand this code here,please!
#include <bits/stdc++.h>
#define lli long long int
#define li long int
#define ld long double
using namespace std;
const lli mod = 1e9 + 7;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli n, total=0, ans=INT_MAX;
cin >> n;
li arr[n];
for(lli i = 0; i < n; i++) {
cin >> arr[i];
total += arr[i];
}
for(lli i = 0; i < 1<<n; i++) {
lli s = 0;
for(lli j = 0; j < n; j++) {
if(i & 1<<j) s += arr[j];
}
lli curr = abs((total-s)-s);
ans = min(ans, curr);
}
cout << ans;
return 0;
}
1 Like
It literally just tries all possible subsets and takes the minimum absolute difference (note that the second group is, by default, anything that isn’t in the first group).
3 Likes
thanku so much for taking time, i m just not getting the line(i & 1<<j) why is it checking the jth bit of i.
it was amazing, really amazing thing i learnt today ! thanku so much !
learnt a new thing thank you.
but i have only one query
this solution is possible when n<=32 right? because if n>32 it can’t be represented in the bit representation right? coorect me if i am wrong
i am trying to learn bit manipulation
Mostly correct (although you could use 64-bit long long
too - that’s the real upper limit). And looping all other masks would have other problems too with that many values, 2^{32} or 2^{64} operations would definitely TLE.
2 Likes
Please explain that solution to me.
ohh okay thank you for the help.
you can also use a back tracking approach for this problem
you can use bits to solve this problem by looping over all the possible combinations as described in other replies but here i found a recursive and dynamic programming solution
link
I am solving Apple division CSES,
n < 21
i.e. TC - 2e7
which means the solution should get accepted, but it is not I am getting TLE!
Also, cannot use DP cause, weight of apple is 10^9, idk how to solve this!
Can you help?
Edit - I am using Python.