SSO - Editorial

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

@psychik The Setter’s solution is blank. I think you forgot to put the solution.

Why use only 51 bits, I mean it should go until 60 in worst case right ??

Passes all except Task #0. Please help
https://www.codechef.com/viewsolution/39254785

30 bits should be enough as constraint is
:smirk:

<2^30

Is it failing for Task #0 ?

1 Like

Check the Official Video Editorial to see why this approach works. :slightly_smiling_face:

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) :slightly_smiling_face: