PPXOR - October Cook Off Cook39

This is the problem that i hav been trying to solve…here’s my code

int main()
{

      int t,n,a[100010],i,j;
      int dp[2][100010],sum=0;
      
      scanf("%d",&t);
      
      while(t--)
      {
                scanf("%d",&n);
                
                a[0] = 0;
                
                for(i=1;i<=n;i++)
                scanf("%d",&a[i]);
                
                memset(dp,0,sizeof(dp));
                
                i=1;
                sum=0;
                
                dp[1][1] = a[1];
                
                for(j=2;j<=n;j++)
                {
                                 dp[i][j] = dp[i][j-1] ^ a[j];
                                 sum+=dp[i][j];
                }
             
                for(i=2;i<=n;i++)
                {
                                 for(j=i+1;j<=n;j++)
                                 {
                                                    dp[1][j] = dp[1][j] ^ a[i-1];
                                                    sum+=dp[1][j];
                                 }
                }
                
                for(i=1;i<=n;i++)
                sum+=a[i];
                
                printf("%d\n",sum);
                                 
      }                          

return 0;
}

Getting WA repeatedly…Is there any corner case am missing…??..Any help will be much appreciated…

I couldn’t really understand the dp involved, but one thing is for sure, even if you do not get WAs somehow, the time complexity of your algorithm is O(n^2) [due to the nested loop], and since n could be upto 10^5, your code will give TLE.

@shobhit6993 :

my logic is say for instance n = 4…so the sets we need to compute are (1,2),(1,3),(1,4)…after that (2,3),(2,4)…then (3,4)…

First i ll be computing Value of (1,2),(1,3),(1,4)…value of (1,3) can be obtained from dp(1,2) ^ a[3]…so
dp(i,j) = dp(i,j-1) ^ a[j]…

Then i ll compute dp(2,3) from dp(1,3) as dp(2,3) = dp(1,3) ^ a[1]…and store the result back in the location (1,3)…
Similarly i ll compute dp(2,4) from dp(1,4) and store it back in the location (1,4)…

Now to compute dp(3,4) i ll go to the location (1,4) (Now 1,4 has the answer for (2,4))…So dp(3,4) = dp(1,4) ^ a[2]…and store it back in the location (1,4)…This way i ll be dng for all pairs…So instead of 2D array of dp[10^5][10^5] an array size [2][10^5] is sufficient…

And at last i ll be adding dp(1,1),dp(2,2) which are a[1],a[2] and so on…This is my logic…

But i think the prob is with integers…But i guess using long long will give TLE coz of the loop running 10^10 times…

//