@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
@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/15336870I 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)
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.
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
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?
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.
@tarun_1407 - Are you sure you took required values as long in JAVA? I was getting WA in C++ because of int. Changed it to long long, got 40 points.
i used long, got WA, even tried with BigInteger which i knew was much more than required, but still WA.