Editorial for SGS Programming Challenge P1 - XOR in Computer Class

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Snowfall

Subtask 1

Because a_i is never greater than 1, each a_i only has one bit. If we XOR a bit by 1, the bit will flip. If we XOR it by 0, it will stay the same. Thus, there are two options for one bit: not changing it or flipping it. Applying this to all bits in one position, all bits either remain unchanged (if x is 0) or are flipped (if x is 1). To calculate the subarray sums, we observe that the sum of all subarrays can be calculated using the formula \sum_{i=1}^N a_i(n-i+1)(i). We calculate the sums for when the bit is flipped and when it is not to check which is larger.

Time complexity: \mathcal{O}(N)

Full solution

We can observe that the bits are independent, thus we can use our subtask 1 solution on each bit position separately, multiplying our answer by 2^{n-1} for the n^\text{th} bit (this is the value of that bit) and adding the product to x.

Time complexity: \mathcal{O}(N \log(\max a_i))


There are no comments at the moment.