PROBLEM LINK:Author: Bogdan Ciobanu Tester: Jingbo Shang Editorialist: Hanlin Ren DIFFICULTY:Mediumhard PREREQUISITES:binomial coefficients, Lucas's theorem, multidimensional prefix sum PROBLEM:You are given a rooted tree with root number $0$. Every node $u$ has a weight $X_{0,u}$. When $d>0$, define $X_{d,v}$ is the bitwisexor sum of all $X_{d1,u}$ where $u$ is in $v$'s subtree. You are also given $Q$ queries, each query is a number $\Delta$, and you need to output $X_{\Delta,0}$. QUICK EXPLANATION:Let $Y_d$ be the xorsum of weights of all nodes whose depth is exactly $d$, then the answer to a query $\Delta$ is the xorsum of all $Y_d$'s, where $(\Delta1)\text{ and }d=0$. By using a dp technique similar to multidimensional prefix sum, one can compute $Z_d$, which means the xorsum of all $Y_k$'s where $k\text{ and }d=0$, in $O(N\log N)$ time, and the query takes only constant time. EXPLANATION:subtask 1Since $N,\Delta\le 500$, we can calculate $X_{i,u}$ for all $0\le i\le 500$, $0\le u < N$. Given $X_{i,0},X_{i,1},\dots,X_{i,N1}$, we can compute $X_{i+1,0},X_{i+1,1},\dots,X_{i+1,N1}$ by doing one dfs on tree. This gives an $O(N\cdot\max\Delta)$ algorithm. other subtasksLet's first consider, what if "xor" is changed to addition? i.e., what if $X_{i+1,u}$ is defined as the sum, rather than xor, of all $X_{i,v}$'s where $v$ is in $u$'s subtree? Obviously the answer is a linear combination of all weights, i.e., $X_{\Delta,0}=\sum_{u=0}^{N1}f(\Delta,u)X_{0,u}$, where $f(\Delta,u)$ is something only dependent with $\Delta$ and $u$. What is $f(\Delta,u)$?TL;DR: $f(\Delta,u)=\binom{dep_u+\Delta1}{\Delta1}$ where $dep_u$ is $u$'s depth and $dep_0=0$. Now let's consider how to solve $f(\Delta,u)$. Take the sample input as an example: Then we have: $$\begin{align*} X_{1,0}=&X_{0,0}+X_{0,1}+X_{0,2}+X_{0,3};\\ X_{2,0}=&X_{1,0}+X_{1,1}+X_{1,2}+X_{1,3}\\ =&(X_{0,0}+X_{0,1}+X_{0,2}+X_{0,3})+(X_{0,1}+X_{0,2})+X_{0,2}+X_{0,3}\\ =&X_{0,0}+2X_{0,1}+3X_{0,2}+2X_{0,3};\\ X_{3,0}=&X_{1,0}+2X_{1,1}+3X_{1,2}+2X_{1,3}\\ =&(X_{0,0}+X_{0,1}+X_{0,2}+X_{0,3})+2(X_{0,1}+X_{0,2})+3X_{0,2}+2X_{0,3}\\ =&X_{0,0}+3X_{0,1}+6X_{0,2}+3X_{0,3};\\ &\dots \end{align*}$$ For example, $f(2,3)=3$ and $f(2,2)=6$ here. A recurrence equation of $f$ is: $f(\Delta,u)=\sum_{v\text{ is }u\text{'s ancestor}}f(\Delta1,v)$(note that $v$ could be $u$). Why? Note that when we calculate $X_{\Delta,0}$, we write $$\begin{align*} X_{\Delta,0}=&\sum_vf(\Delta1,v)X_{1_v}\\ =&\sum_vf(\Delta1,v)\sum_{u\text{ is }v\text{'s offspring}}X_{0,u}\\ =&\sum_uX_{0,u}\sum_{v\text{ is }u\text{'s ancestor}}f(\Delta1,v);\\ \text{also, }X_{\Delta,0}=&\sum_uX_{0,u}f(\Delta,u). \end{align*}$$ This explains the above equation. Let's do more on the equation: $$\begin{align*} f(\Delta,u)=&\sum_{v_1\uparrow u}f(\Delta1,v_1)&\text{we use }a\uparrow b\text{ to represent that }a\text{ is }b\text{'s ancestor(possibly }a=b\text{)}\\ =&\sum_{v_1\uparrow u}\sum_{v_2\uparrow v_1}f(\Delta2,v_2)\\ =&\dots\\ =&\sum_{v_1\uparrow u}\sum_{v_2\uparrow v_1}\dots\sum_{v_{\Delta}\uparrow v_{\Delta1}}f(0,v_{\Delta}). \end{align*}$$ Thus, $f(\Delta,u)$ is the number of sequences $(v_0,v_1,v_2,\dots,v_{\Delta})$ such that:
Obviously all $v_i$'s appear on the path from $u$ to $0$. Let $dep_x$ be the depth of node $x$($dep_0=0$) and $d_i=dep_{v_{i1}}dep_{v_i}$, then $(d_1,d_2,\dots,d_{\Delta})$ is an array satisfying the following condition:
We find that every array $d$ satisfying the above condition gives us a unique valid sequence $v$! So $f(\Delta,u)$ is just the number of such array $d$'s. Next is a classical lemma stating this number is just $\binom{dep_u+\Delta1}{\Delta1}$(refer to Wikipedia, the last line of "Definition and interpretations"). We omit the proof here. Lemma 1: given $n,k$, the number of nonnegative solutions of $x_1+x_2+\dots+x_n=k$ is $\binom{n+k1}{n1}$. Coming back to XORNow let's consider the xor case. Note that xoring the same number for even times does nothing, so for a query $\Delta$, we pick all nodes $u$ such that $f(\Delta,u)$ is odd, and xor them up. Next we'll use a lemma called Lucas's Theorem: Lemma 2: given $n,m,p$, and $p$ is a prime. Let's write $n,m$ in base $p$: $$\begin{align*} n=&\overline{n_kn_{k1}\dots n_1n_0};\\ m=&\overline{m_km_{k1}\dots m_1m_0}, \end{align*}$$ Then, $$\binom{n}{m}\equiv\prod_{i=0}^k\binom{n_i}{m_i}\pmod p.$$ Let me demonstrate the lemma by an example. Let $p=5$, $n=116$, $m=55$. Then $n=(\overline{431})_5,m=(\overline{210})_5$, so $\binom{n}{m}\equiv \binom{4}{2}\cdot\binom{3}{1}\cdot\binom{2}{0}\equiv 3\pmod 5$. Actually, you can check that $\binom{n}{m}=5265169722428127562717416598795968\equiv 3\pmod 5$. How does the theorem help us? Note that we only need to know the reminder $\binom{a}{b}\bmod 2$ for some huge $a,b$. When $p=2$, Lucas's theorem becomes Lemma 3: $\binom{n}{m}\equiv 1\pmod 2$ if and only if $n\text{ and }m=m$, where $\text{and}$ is the bitwiseand operation. Thus, $f(\Delta,u)\equiv 1\pmod 2\iff \binom{\Delta1+dep_u}{dep_u}\equiv 1\pmod 2\iff (\Delta1+dep_u)\text{ and }dep_u=dep_u$. subtask 2To solve subtask 2, we preprocess $Y_d$ as the bitwisexor sum of all nodes at depth exactly $d$, and for a query $\Delta$ we enumerate all $d$ from $0$ to $N$, if $(\Delta1+d)\text{ and }d=d$, we xor the answer with $Y_d$. Time complexity: $O(NQ)$. subtask 3If you print the values of $X_{i,0}$ and try to find patterns, you'll find that $X_{i,0}$ has a period of length $L\le 2N$. The solution for this subtask is: first find the length of that period $L$, then prepare all $X_{i,0}$'s for $i\le L$; for any query $\Delta$, we just print $X_{\Delta\bmod L,0}$. In the solution of subtask 4 I'll show that, the answer only depends on the last $\lceil\log_2 N\rceil$ bits of $\Delta1$, and that's why we have an $O(N)$ period. subtask 4Can the condition "$(\Delta1+d)\text{ and }d=d$" be further simplified? Yes! Note that $x\text{ and }y=0$ is a sufficient condition for $(x+y)\text{ and }y=y$, since when adding $x$ and $y$ in binary, no carries would happen. Is it necessary? The answer turns out to be yes! This can be proved by contradiction: Suppose $i$ is the lowest bit that both $x$ and $y$ has $1$ on this bit. Then $(x+y)$'s $i$th bit is $0$ and that violates $(x+y)\text{ and }y=y$. Thus "$(\Delta1+d)\text{ and }d=d$" is equivalent to "$(\Delta1)\text{ and }d=0$". Let $Z_d$ be the bitwisexor sum of $Y_f$'s such that $f\text{ and }d=0$. For a query $\Delta$ we directly output $Z_{(\Delta1)\bmod 2^{18}}$, since $2^{18}>N$ and $((\Delta1)\text{ and }d)$ is only related to $(\Delta1)$'s last $18$ bits. How to compute $Z_d$? We can do it by a dp that's similar to multidimensional prefix sum: Let $dp_{i,j}$ denote the bitwisexor sum of all $Y_d$'s, such that:
Then $dp_{i+1,j}=\begin{cases} dp_{i,j\text{ xor }2^i}&i\text{th bit of }j\text{ is }1\\ dp_{i,j}\text{ xor }dp_{i,j\text{ xor }2^i}&i\text{th bit of }j\text{ is }0\\ \end{cases}$. Note that $dp_{0,j}=Y_j$, and what we want is $Z_j=dp_{18,j}$. The overall complexity is $O(N\log N+M)$. ALTERNATIVE SOLUTION:If your solution is different with ours, feel free to leave a comment. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 17 Aug '17, 18:06

I just used 2 observations to solve this problem.
So we can make up the chain to the nearest power of 2 by padding with zeroes for convenience, and then the pattern can be generated by splitting the chain into two halves, solving recursively, and combining (similar to mergesort). Here is my solution, although I have used an iterative version instead of recursion. The complexity is $\mathcal{O}(N \log N)$. EDIT (The merging and solving procedure in greater detail): function solve(A, L, R): N = R  L + 1 if N equals 1: return solve(A, L, L+N/21) solve(A, L+N/2, R) A_L = slice of A from L to L+N/21 A_R = slice of A from L+N/2 to R for i in [0..N/21]: A[L+i] = A_L[i] xor A_R[i] A[L+N/2+i] = A_L[i] Calling For example, if So And then they will be combined into That took some typing.. hope it's clearer now :D answered 11 Sep '17, 16:04
i also saw same pattern but got TLE in last cases(C++)...
(11 Sep '17, 16:11)
That xoring of nodes at same depth....really mind blowing. That was a pretty neat observation honestly!!!
(11 Sep '17, 16:15)
@adecemberguy I don't think using C++ was the cause of TLE, $\mathcal{O}(N \log N)$ should comfortably clear the limit. Perhaps there is some part of your code taking greater time than you expect?
(11 Sep '17, 17:22)
1
The pattern can have periodicity upto $N$ (roughly) , so if one tries to derive pattern by brute force (i.e. keep on doing recursion, calculating $d_1,d_2,d_3...$ until a repetition/original configuration is obtained) then the last 2 cases give TLE.
(11 Sep '17, 17:28)
@meooow I was trying something very similar. Even though your solution is obviously correct, I'm struggling to understand it completely. I understand the part that it has periodicity on powers of 2 that are >= chain length. I also understand that it's convenient to add 0's to the end to make it power of two, since it seems to be easier to explore what happens on powers of two. I'm not getting the part where you merge 2 halves. Can you please elaborate more?
(12 Sep '17, 05:57)
@llaki I have updated the answer. Hope it's helpful!
(12 Sep '17, 07:39)
@meooow thanks a lot for taking time and effort to provide more clarity, really appreciate it! :)
(12 Sep '17, 11:36)
showing 5 of 7
show all

Well, after making some random test cases, even I observed a recursive pattern, those who observed but unable to code can check my code for a simple implementation of that recursive pattern. Only one test case took 0.48 sec, remaining test cases took less than 0.09 sec. I used 8 for loops and 8 if condition. What else I did was, I divided the depth in a group of 4 because if they are going to contribute in the answer, they will appear in a group of 4. answered 12 Sep '17, 01:18

Sierpinski triangle is T[height][time  1] = T[height  1][time  1] xor T[height][time  2] = ( height & (time  1) == 0), then you can use SOSDP in the mask height for all mask ~(time  1) in Boolean Algebra part: https://www.zeuscat.com/andrew/chaos/sierpinski.html answered 13 Sep '17, 07:42

@liouzhou_101 you said that you were thinking of optimizing it! can you please tell what kind of optimizations are possible here? i am a beginner and for the first time solved 6th question ! it will be helpful if u share your ideas :) answered 11 Sep '17, 20:23

Hey everybody answered 12 Sep '17, 18:48
Yes :D The binomial coefficients modulo 2 is exactly the Sierpinski Triangle. The author used this term when describing his solution, however I didn't.
(12 Sep '17, 20:49)
Math is love <3
(12 Sep '17, 21:14)

This is exactly what I did :) nice problem ! answered 11 Sep '17, 16:00

For 40 points i simulated the process until i reach the same value on the root as the initial value. Then i returned rootValues[delta % rootValues.length ] It's wrong obviously, as i got WA on the third subtask but hey, 40 points is not bad :). answered 11 Sep '17, 18:34

How I approached it it can be simply observed that whenever nodes come in answer all the nodes with same level also comes ,So we can calculate XOR depthwise, Let consider super worst tree ever ,this tree is 1>2>3>4>...>n 1)on day 0 ,ans=1 2)on day 1 ,ans=1^2^3^4^5^6..^n 3)on day 2 ,ans=1^(2^2)^(3^3^3)^(4^4^4^4)^(5^5^5^5^5)^..... 4)on day 3 ,ans=1^(2^2^2)^(3^3^3^3^3^3^3)^.... u can observe:on day 3 , number of 1s,2s,3s,4s,5s,... are 1,3,6,10,15.... again u can see that this looks like binomial coefficients and on further days this pattern also emerges :) so on day k+1 ans=1(kCk time) ^2 ((k+1)Ck times) ^3 ((k+2)Ck times) ^...... You know XOR of a number even times is 0 and otherwise the number itself, so question decreases to find whether nCk is odd or even and now read last para of editorial. Suggestions: Never cancel out XOR values in initial stages, I stuck on this problem for 7 days just coz I cancelled out XORs and was finding pattern in that I couldn't comeup with dp solution given at last in editorial because calculating for each depth XOR must take O(n) time for each query ,I was unable to think of preprocessing the dp table answered 11 Sep '17, 18:55

i have solved it using two observations : first that if any element of any level is present in any node(after some operations) then all the element at that depth is also present in that set...and a tree with depth x will have (2^x) different values of the root. And further after d days the value at root is the Xor of all possible submasks of mask(2^x  d). I calculate all the submasks and store it and then answer the query in constant time :)... solution : https://www.codechef.com/viewsolution/15353659 first i think that it will give TLE as generating submasks of all the masks is (3^x) operation which will in worst case 3.2 seconds... but i dont know how it passed...if anyone can explain me why it will be helpful :) answered 11 Sep '17, 19:12

@pk301 I also have the same approach as you, which is an O(3^k) solution where k = O(log n). It passed because of compiler optimization and highspeed of bitwise operations. My solution runs in 0.20s the worst case of the test data. I was thinking of how to optimize it, however, I didn't try that as it directly passed. Feel better if the constraints were set more strict in order to let O(3^k) solution not pass. answered 11 Sep '17, 19:31

@meooow, Thanks for the insights :) Although, can you please explain the recursive call part ? I understood the pattern that you meant, but I'm not able to relate it to a recursive call. It would be great if anyone could help. Thanks in advance :) answered 11 Sep '17, 20:22
I have updated my answer to explain the recursive part in greater detail, take a look :)
(12 Sep '17, 07:40)

Please help me with my solution i am getting NZEC but it is working fine in my IDE. Even if you could give me a testcase for which my solution would get NZEC. https://stackoverflow.com/questions/46154263/codechefsept2017challengeweaseldoesxorontreegettingnzecforthissubmi Please help. answered 11 Sep '17, 22:12

I made these 2 observations:
So, to get the answer for $\Delta$, first I find all powers of 2 that are included, then I compute the xor sum of all nodes with depths that are combinations of these powers. For example: if $1$, $4$, and $8$ are included, $1$, $5$, $9$, $12$ and $13$ are also included. If we take the binary representations of these numbers, then we can see that $1={(0001)}$, $4={(0100)}$, $5={(0101)}$, $8={(1000)}$, $9={(1001)}$, $12={(1100)}$ are subsets of $1 + 4 + 8 = 13 = (1101) $ To compute the xor sum of all subsets, we can use the approach described here: http://codeforces.com/blog/entry/45223 Complexity: $ (N + Q) \cdot \log(N) $ answered 12 Sep '17, 04:11

I have taken the following approach in solving: Noticed that for any delta, the result is the XOR of the value of the result at "delta = 1" with the XOR of all elements present at depth delta, ie RESULT for delta(D) = Result for delta(1) ^ (Result of XOR of all elements present at depth D). lets say for the example given in question itself, Result of delta(1) = 1^5^8^7 = 11 Now for the queries, Result of delta(2) = 11 ^ (Result of XOR of all elements present at depth 2) = 11 ^ (5^7) = 9 Result of delta(3) = 11 ^ (Result of XOR of all elements present at depth 3) = 11 ^ (8) = 3 After this the pattern just repeats with the fact that delta(0) = value present in array initially ie 1. Can someone please point out what is wrong with this approach and where do I need to correct, the editorials and comment by all the people here are really good but just need to know how can it be solved if I take this approach and if it can be solved using this or not.Link to my solution is https://www.codechef.com/viewsolution/15395688 answered 12 Sep '17, 13:50

how is f(/\,u) the number of sequence (v0,v1,......v/) ?? i cant understand.. answered 15 Sep '17, 22:34

I used a considerably different approach for this problem, similar to some of the comments. First I realised that whether an element(in chain instead of tree) is present in the answer or not depends solely on k and d(depth) of that element. Let n be the maximum depth of the chain. Then i observed that if all set(1) bits in d are 0 in k(or 1 in binary negation of k), the element is present in xor(answer), else absent. Let x denote the next power of 2 >=n. I then used self explanatory approach to calculate answer for negation of all possible k less than x in O(nlogn). Also, please confirm that this works for all corner cases. Heres the link to my solution, Please upvote. AC in 0.15 seconds https://www.codechef.com/viewsolution/15387157 answered 16 Sep '17, 13:40
https://youtu.be/NWDCHktHnuI Tried to make a video editorial I'm really bad at this but please do tell me if it's helpful :)
(24 Sep '17, 22:04)

Hey everybody
I've made a video in 2 parts for this problem.
Part 1: https://youtu.be/FhC6A4mvXUw(Weasel does XOR on Tree  Part 1)
Part 2: https://youtu.be/HIVZ9HVSIb0(Weasel does XOR on Tree  Part 2)
Did you guys notice the amazing look alike of "Sierpinski Triangle" Fractal in this problem? See the part 2 especially as I have discussed about it there.