exactly
1 Like
Is it a typo ?
req[X] = 0;
if(type(X) == Type2) {
excess[X] ++; // I think this should be “req[x]++;”
}
1 Like
if we mark all nodes at odd depth with 0 and even depth with 1 or vice - versa
and then optimise/calculate the cost of converting the given string into the form
011…11100…0011…1111 or 1000…011…10…0
will this work ???
1 Like
fixed, thanks for mentioning it.
1 Like
I did the exact same thing but I was getting TLE. Can anyone tell me whats wrong?
TLE Solution link: CodeChef: Practical coding for everyone
I used donor and taker in place of excess and req variables. And ignore the commented lines ( 
) And my dfs function name is solve
1 Like
But since there is a restriction about which nodes can be swapped with which ones (adjacent nodes in the tree will not always be adjacent in the string), how would you approach for that?
2 Likes
It doesn’t seem intentional to me. The problem statement is fairly simple, so it’s easy to think of the same problem. But yeah, they should’ve researched a bit more and checked if the problem already existed somewhere else.
6 Likes
We did not know that problem existed. We did decent amount of check but could not find. As someone suggested, I should have checked more given the problem statement is so simple and natural.
7 Likes
i did the same thing followed by finding distance between the positions where we need 1(pos1) which is somewhere else(pos2) in the original string but got WA.
is this wrong??
exactly.How can this work is only adjacent swap allowed.
What would be the difficulty level for this question for somebody who knows basics techniques in tress and graphs, will he be able to solve it? i haven’t worked on trees yet.
1 Like
Sir can u please help
why am i getting TLE in my code despite using the same logic as yours?
Submission: CodeChef: Practical coding for everyone
2 Likes
If you know how to do a dfs, then you can do it.
You can refer to this solution :
4 Likes
Does not matter only 57 participants were able to solve it. 
2 Likes
Someone please give it a look.
1 Like
can someone please explain me how the ans is going to be calculated? We have to add distances between the nodes but we in tutorial where are we adding those distances?
1 Like
In the editorialist solution the part where ans+=excess[u]+req[u], that is where we count the number of nodes for which we travel the edge from u to its parent.
1 Like
I guess in your recursive function you are passing string s as pass by value and as its size can reach O(N) and your recursive function is called O(N) times, your algo is taking O(N^2). so globally defining it or passing it by reference might fix the issue of TLE
1 Like
Editorial is very nicely written got each point … thank you
3 Likes