Similar to other contestents in the problem XDCOMP problem link I also constructed a tree containing xor equal to X or 0 using Bottom Up approach. But after this my approach was quite different. We know that Fibonacci(N)= Number of ways to represent N as sum of odd numbers.
Now we let the number of subtrees having Xor value=X be M ,which we already know. So all the possible combinations to distribute them in groups with XOR value X will be Fibonacci(M). For Xor value 0 we will make corner case. IDK whether this approach is correct or not. I just applied a many times it and got WA’d all the time. My submission can be found here .
Your solution underestimates the number of the possible subtree combinations; you are missing some of the possible cases. Please consider the following test:
8 1
1 0 0 1 0 1 1 1
1 2
1 6
2 3
2 4
5 6
6 7
5 8
Your solution solves it with the answer 7 while the number of possible subtree combinations is definitely greater:
1. {1,2,3},{4},{5,6},{7},{8}
2. {1,2,3},{4},{5,8},{6},{7}
3. {1,2,3},{4},{5,6,7,8}
4. {1,2,3,5,6,8},{4},{7}
5. {1,2,3,5,6,7},{4},{8}
6. {1,2,3,6,7},{4},{5,8}
7. {1},{2,3,4},{5,6},{7},{8}
8. {1},{2,3,4},{5,8},{6},{7}
9. {1},{2,3,4},{5,6,7,8}
10. {1,5,6,8},{2,3,4},{7}
11. {1,5,6,7},{2,3,4},{8}
12. {1,6,7},{2,3,4},{5,8}
13. {1,2,3,4,6},{5,8},{7}
14. {1,2,3,4,5,6},{7},{8}
15. {1,2,3,4,5,6,7,8}
2 Likes
Thanks for the response. I think the approach will work only when none of the elements is zero in problem tree.
Anyways if anyone could manage cases having zero using the above approach, do reply.