CHEFFILT - Editorial

Your approach is O(N∗1024∗T). You need to be lucky to pass with that solution. Try the approach mentioned in the editorial O(T***1024***1024).

@xariniov Few of them passed all test cases with the same complexity.So I was wondering whats wrong with my code.

Mine also did pass all the test cases during the contest. I’m not sure, if they add stronger test cases for practice problem or it might be a case that your solution has a bigger hidden constant factor.

The line that follows that tries to perform two operations at once:

“new_v[j] = (v[j] + v[j^i]) * p2[c*-1] % mod” and
“new_v[j^i] = (v[j] + v[j^i]) * p2[c*-1] % mod”

This assigns the same value to two indices: j and j^i. However, without “j <= (j^i)”, this will be done twice (once for j and another for j^i), so the answer will be incorrect. We need “j <= (j^i)” for this to be only done once.

i think its because of using maps…

saved some time for me .