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?
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.
1 Like
@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.
@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?
I have updated my answer to explain the recursive part in greater detail, take a look 
Wow… that is some solution