Hello all,

Recently, while looking at interesting problems I can assign my students to solve, I found this CSES problem — Xor Pyramid which to my surprise I didn't see it covered anywhere lately even though it's in my opinion quite a beautiful problem with a short implementation, so I decided to make a video solution for it, which can be found here.

At first, it seems very hard to approach it faster than building the entire pyramid in $$$O(n^2)$$$ but after thinking at various observations related to how XOR operation works, as well as recalling a similar approach used for the same problem's SUM version, we can come up with a very short and in my opinion, beautiful idea.

The main idea is to observe that each of the numbers from the bottom row of the pyramid has a certain contribution to the final XOR sum, and similar to how you would compute the actual sum of the values, we can see that the contribution of the values on the final row is equal to the $$$n_{th}$$$ row of Pascal's triangle, and thus we can reduce the problem to finding the parity for each value from this row (even contributions cancel out when it comes to XOR operation).

In order to compute this fast, we will have to precompute for all factorials up to $$$n-1$$$ the exponent at which $$$2$$$ shows up in all factorials and now we will rely on the well known formula for combinations in order to find the final exponent at which $$$2$$$ shows up in the contribution for each of the numbers in the array.

Thus, we managed to solve a seemingly complicated CSES problem using a beautiful solution with only around $$$10$$$ lines of code. Please let me know what you think and I am curious to find out what other problems or techniques should I cover next.