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.

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…