What is the time complexity of this program

#1

And why he just gives an idea, he should have explained the whole approach in this video, what is happening in this dp course ???

#2

and why is it giving WA instead of TLE , i changed n-1 to n-2 before !!

#3

Can you share me the questions link and your solutions link?

#4

Question : https://www.codechef.com/problems/DAGXOR
Solution : https://ide.codingblocks.com/s/351790?_ga=2.86326616.1550168367.1601926599-443463197.1563121852

#5

The answer to this problem will just be 4^ ( no of non leaf nodes)

#6

You can calculate all the non leaf nodes in 0(n) time and do the power using modular exponential. You’ll get an acceptance. I’m also adding the link to the code for your reference.
https://www.codechef.com/viewsolution/26800731

#7

You are getting a tle because you are using recursion. Stack is begin created at every step and it takes a lot of time in recursion than an iterative solution. So even if your complexity of 10^7. It will be very tight in time to pass.

#8

But sir , what is the logic behind this and what is the logic that is taught in video, i could not understand any, please explain both !!

#9

But sir, my many solutions around of 1e8 are even passed on codechef, so how can a 1e7 solution get TLE and recusion and iterative may have a speed difference but this much :worried:

#10

Recursion has to create a stack and then destroy the elements created in the stack each time you call. So it is definitely possible that your implementation can give you a time limit exceeded.

#11

Okay sir, and sir what was the symmetric part told in video from 13:00 to 19:00 ?

#12

I haven’t seen the video so cannot tell you about the symmetry. I have clarified you most of the things now it’s your turn to implement it.

#13

please,call me on 8368547890.

#14

sir, Can i whatsapp call on this number

#15

yes u can…