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.
how to be good at cp
Additionally, the i-th number in row n has a contribution iff
x & (n - 1) = n - 1, which solves this problem in O(1) memory.This is another neat observation! Thanks for the comment
For a proof of this fact, one can use Lucas' Theorem which states that
where $$$n=n_lp^l+n_{l-1}p^{l-1}+\ldots +n_0$$$ and $$$k=k_lp^l+k_{l-1}p^{l-1}+\ldots +k_0$$$ are the base $$$p$$$ expansions of $$$n$$$ and $$$k$$$. The theorem uses the convention that $$$\binom{n}{k}$$$ is $$$0$$$ whenever $$$k>n$$$. Using $$$p=2$$$, we get that the parity is $$$0$$$ iff there is some $$$n_i=0$$$ and $$$k_i=1$$$, which implies that it is $$$1$$$ iff all bits set in $$$k$$$ are set in $$$n$$$.
Note that a pyramid of height $$$n$$$ has contributions as the $$$(n-1)$$$-th row of Pascal's triangle which is why you take and with $$$n-1$$$.
I have another solution(Constructive way), don't know whether it is the intended solution or not
Observe for odd $$$n$$$ on what indices the final answer depends on! (if $$$n$$$ is even do one Operation to get into odd $$$n$$$)
The observation concludes that these sequences depends on nearest integer which is in the form of $$$2^{x}$$$ for some positive integer $$$x$$$.
For the final answer just XOR all these indices. Time Complexity : $$$O(nlogn)$$$.
yeah