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 :).
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 depth-wise, 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 pre-processing the dp table
1 Like
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 : CodeChef: Practical coding for everyone
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 
@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 high-speed 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.
@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
@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
1 Like
@pk301
The way to optimize is just shown in the editorial I think. However, I didn’t catch it at that time (since I passed it with unexpected solution, and I would spend time solving next several problems).
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/codechef-sept-2017-challenge-weasel-does-xor-on-tree-getting-nzec-for-this-submi Please help.
Well, after making some random test cases, even I observed a recursive pattern, those who observed but unable to code can check my
[1] 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.
[1]: https://www.codechef.com/viewsolution/15336870
3 Likes
I made these 2 observations:
- Nodes with depth 2^{n} are included in the result iff : (\Delta-1)\ \%\ 2^{n+1} < 2^{n}
- Nodes with depth x = \sum 2^{a_{i}} are included in the result iff nodes with depths 2^{a_{i}} are included for all i
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)
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 CodeChef: Practical coding for everyone
Hey everybody
I’ve made a video in 2 parts for this problem.
Part 1: [Tutorial] Codechef SEPT17 - WEASELTX | Problem Solving Skills - Part 1 - YouTube (Weasel does XOR on Tree - Part 1)
Part 2: [Tutorial] Codechef SEPT17 - WEASELTX | Problem Solving Skills - Part 2 | Why I Love Math - YouTube (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.
1 Like
It may be a brute-force approach but I am really curious where my
[1] is going wrong, apart from it's complexity. I used adjancy matrix to represent the tree and simply XOR'ed the values present in the sub-trees for every node.
[1]: https://www.codechef.com/viewsolution/15370042Sierpinski 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: Sierpinski Triangle
2 Likes
how is f(/,u) the number of sequence (v0,v1,…v/) ?? i cant understand…
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
i also saw same pattern but got TLE in last cases(C++)…
That xoring of nodes at same depth…really mind blowing. That was a pretty neat observation honestly!!!
@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?