stefdasca's blog

A beautiful CSES problem with a way easier solution than one might think it has
By stefdasca, history, 6 months ago, In English

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.

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

how to be good at cp

→ Reply
»
6 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    This is another neat observation! Thanks for the comment

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For a proof of this fact, one can use Lucas' Theorem which states that

    $$$\binom{n}{k}\equiv \prod_{i=0}^l \binom{n_i}{k_i}\bmod{p}$$$

    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$$$.

    → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have another solution(Constructive way), don't know whether it is the intended solution or not

  1. Observe for odd $$$n$$$ on what indices the final answer depends on! (if $$$n$$$ is even do one Operation to get into odd $$$n$$$)

  2. The observation concludes that these sequences depends on nearest integer which is in the form of $$$2^{x}$$$ for some positive integer $$$x$$$.

  3. For the final answer just XOR all these indices. Time Complexity : $$$O(nlogn)$$$.

code
→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yeah

→ Reply