Why the below code gave tle , although it was t*n*4 which is 1e7

#1
#2

I find the time complexity is fine. Where have you tried submitting the code.

#3

Problem : https://www.codechef.com/problems/DAGXOR
In mine its giving WA, but when sir wrote in video , it gave TLE in them, why WA in mine and why TLE in them, and i also could not understand the logic of symmetric he told from 13:00 to 19:00 of the video, can you please explain that with drawing figure as well !!

#4

I’ve replied to your queries in the previous thread.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

Sir, Could not understand why, please explain how to come up with that solution :frowning:

#7

See there are some simple observations.

  1. You are given a rooted tree. (No cycles)
  2. You can make the xor of the path 0 with three elements:- 1,2,3.
    So you need three nodes to be fixed.
    So let’s say you fix node1,N and all leaf nodes connected to the Nth node. Then you can make the xor of path zero. Wo in all the other positions you can put any possible value so there are 4 possible ways to fill each cell.
    There fore logic comes to be very straightforward to implement this.
    https://www.codechef.com/viewsolution/26628574
#8

why i need 3 nodes to be fixed and is this saying for every path ?? and is the leaf word for the nodes connected to nth node ??

#9

and what does all other position mean here, and if leafs are already filled then why 4^(no. of leaf nodes ) , can you please explain with small diagram and example

#10

It’s 4^( non leaf nodes). I think you should give a try to this question yourself first. It’s pretty easy to think . You’re trying to understand my logic which sometimes become difficult. So give it a try and tell me if you could solve or not.

#11

You need three nodes atleast because you need three elements 1,2,3 to make a path with xor 0.

#12

1
4
1 2
1 3

Sir, can you please explain this case ?? ( And why only leaf nodes needs to put with 1,2,3 , can’t i put every it anywhere, and untill and unless the tree is a straight line, their will be no leaf node :frowning:

#13

Yes you can consider any nodes not necessarily leaf nodes. But it is easier to think in terms of that. If you do not take that it will be difficult to think which nodes are picked. I hope you understand.

#14

Sir, like in the above example if i take 1 path i.e 1->2->4 then how can i assign the values 0,1,2 in this path bcz then the xor would not be 0. So, how that condition satisfies here, baas ye baat samaj nhi aa rahi :frowning: