why is that exactly same as tester’s submission ?
1 Like
LoL
Please give me some tips so that I can also play with numbers like you.
2 Likes
dp[i] surely doesn’t represent the freq of sums having i^{th} bit set. Regarding dp[i]/2 think about addition in binary.
maybe because it’s trivial… or it might be my alt…
I wrote an exponential algorithm and a random testcase generator and tried 2-3 ideas… This was my third one… It ran for about a minute without giving errors at which point I killed it and submitted.
1 Like
answer will be the sum of some powers of 2
; those powers of 2 should be attained by the subset sum
bitwise OR turns the bit on
like 1,9,8 max sum here is 17 turns on the bits at 5th(16) and 1st(1) place
for 9 bit set -> at 4th place (8)
for 10 bit set -> at 2nd place (2)
using OR only we can set the bits
1 Like
can someone please tell what is the error in this, i am not getting done somewhat similar as mentioned in the editorial.
ll bit[51];
int main()
{
int t = 1;
cin >> t;
while (t--)
{
ll n;
cin >> n;
ll a[n];
memset(bit, 0, sizeof(bit));
for (int i = 0; i < n; i++)
{
cin >> a[i];
for (ll j = 0; j <= 50; j++)
{
ll d = ((a[i]) >> j) & 1;
bit[j] += d;
}
}
ll p = 1, prev = 0, ans = 0;
for (ll j = 0; j <= 50; j++)
{
ll dis = bit[j] * p;
prev += dis;
if (prev >= p)
{
ans += p;
}
p = p * 2;
}
cout << ans << endl;
}
}
check this
1 Like
why use dp[i-1]/2? I mean if there are 4 numbers with (i-1)th bit set then there can 4c2+4c3+4c4 ways to choose the numbers; hence there will be 11 different numbers with ith bit set.
Very nice problem. Definitely adding it to my list of best bitwise problems
1 Like
Here, dp[i] doesn’t storing no. of ways to get 1 at ith bit, it is storing maximum count of 1’s at ith bit (including carry contribution covered by dp[i-1]/2).
1 Like
I also initially thought along the same lines but dp[i] is not freq of numbers having i^{th} bit set.
Say you somehow got the freq[i] where freq[i] is freq of numbers having i^{th} bit set. You can’t really write freq[i+1] in terms of freq[i] because there will be some numbers included in freq[i] with their (i+1)^{th} bit already set.
But let’s just assume there is no number included in freq[i] with their (i+1)^{th} bit already set…still you can’t write a definite formula. Say (x and y) contributed in the i^{th} bit and (y and z) also contributed in the i^{th} bit. Say a=x+y and b=y+z. For (i+1)^{th} bit, you’d take contribution of a and b because for both i^{th} bit is set but you can’t really take it as you’d be repeating y in it.
1 Like
oh! yea, now it makes sense. but i strongly feel that the editorialist should have once explicitly mentioned what dp[i] stores (although he has told implicitly what dp[0] stores).
I mean that’s the first thing you should do if you are writing editorial for a dp problem
2 Likes
Why use only 51 bits, I mean it should go until 60 in worst case right ??
30 bits should be enough as constraint is
<2^30
Is it failing for Task #0 ?
1 Like
I think it would be more intuitive if one knows how multiple binary numbers are added column wise, also dp[i] = the number of bits available at the i^{th} column (after all carries have been propagated till the i^{th} column from LSB) 