XORSUB conceptual doubt

1

can someone intelligent explain me why the code fails in testcase 8 to 14 if i place a “+” in the 12th line of my code if i place “|” or operator it works fine.
https://www.codechef.com/viewsolution/26237730

2

“+” and | aren’t interchangeable.
They are different. + will add 2 numbers, in binary representation if 2 corresponding bits are 1, then 1+1 will give 0 and carry=1, which will be added on the next significant bit. | is just bitwise OR, it’ll take “OR” of corresponding bits into the result.

SO, in short, | is simply “+”, without the carries.

3

It would have been better if you had understood the context of his question before commenting. His dp states store boolean values. Now dp[something] = dp[something-else] + dp[something-something-else]is what he replaced dp[something] = dp[something-else] | dp[something-something-else] by. Now addition of dp[something-else] and dp[something-something-else], ie dp[something-else] + dp[something-something-else] will always be either 0, 1 or 2, because both of them can either be False(0) or True(1), and since the variable their sum is assigned to is also boolean, the result stored in it is also either 1(True), 2(True) or 0(False). So, at-least in this case, + and | seems equivalent as
True | True → True
and True → converts to 1, 1 + 1 = 2 → converts to True in boolean
You can extend this to False and it’s equivalent 0 and see it still holds.

The problem, in my opinion, is somewhat different. Perhaps @ssjgz or @l_returns can clarify.

Edit- @adi521, the only thing you missed here is that you declared your dp array of type integer, that’s what causing the problem. + and | will only be equivalent when dp array is of type boolean. I replaced int with bool in your code and kept + as it is(not changing it to |), and all the test cases passed- CodeChef: Practical coding for everyone

2 Likes
4

It’s fairly easy to trigger an overflow in your dp[i][j] value (see e.g. this testcase), which probably doesn’t help matters :slight_smile:

Edit:

Since this thread is about “why” the results differ: as far as I can tell, the only functional problem changing | to + in your original solution causes is overflow. It’s quite possible (though inadvisable) to get correct results by simply avoiding overflow by e.g. clamping d[i][j] to be at most std::numeric_limits<int>::max() / 2 after computing it - if we do this, then the solution with + should give the same results as the solution with |.

But as @anon62928982 says, the best approach is simply to use bool instead of int and avoid all these headaches entirely :slight_smile:

2 Likes
5

yaa might be a problem of over flow but still n is small …i will check by declaring it long…n thanks bro for help

6

that means if the dp array is of long type then it will give correct result

7

Not necessarily - if you’re dealing with exponentially larger numbers, you can easily overflow a long, too.

Edit:

Which is the case, here - here is some of the final output with some diagnostics added before an overflow occurs:

<snip>
i: 71 j: 511 dp[i][j]: 4611686018427387904
<snip>

The next line is

i: 72 j: 0 dp[i][j]: -9223372036854775808

The maximum value a long can hold on my computer is just 9223372036854775807.

2 Likes
8

but i dont think thats the issue as n is not that large and even ai is not that large

9

It is an issue - those printouts showing the overflow came from your code plus my testcase - I just added some print statements to it! :slight_smile:

Edit:

Here’s a copy of your code with the following modification:

a) Changed the types from int to long
b) Keep track of the largest value of dp[i][j], and print it out when it increases
c) Print out negative values of dp[i][j], indicating overflow.

Run it with the testcase I linked and observe the output.

#include <bits/stdc++.h>
using namespace std;
int fun(int a[],int n,int k)
{
    long dp[n+1][1024],i,j,val=0,w=-1;
    long largestDPSeen = 0;
    for (i=0; i<=n; i++) 
    {for (j=0; j<=1023; j++) 
        dp[i][j] = 0;}
    dp[0][0]=1;
    for (i=1; i<=n; i++) 
    {for (j=0; j<=1023; j++) 
        {
            dp[i][j] = dp[i-1][j] + dp[i-1][j^a[i-1]];
            if (dp[i][j] > largestDPSeen)
            {
                largestDPSeen = dp[i][j];
                cout << "New largestDPSeen: " << largestDPSeen << endl;
            }
            if (dp[i][j] < 0)
            {
                cout << "Whoops - overflow: " << dp[i][j] << endl;
            }
        }

    }
    for(i=1023;i>=0;i--)
    {
        if(dp[n][i]>0)
            w=max(w,i^k);
    }
    return w;           
}
int main() {
    // your code goes here
    int t,i;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int a[n];
        for(i=0;i<n;i++)
            cin>>a[i];
        cout<<fun(a,n,k)<<"\n";
    }
    return 0;
}
2 Likes
10

thanks bro you are great at helping everyone keep going… @ssjgz

2 Likes