how to analyze input in form of tree like to draw it in form of a tree? Could anyone help?
@shivamgor498 because if there is intersection of the children’s (min,max) range then swapping them will have some lower value in the right child(although it will be sorted).For example if left child min-max pair is (1,3) and right child min-max pair is (2,4) then swapping them will make 1 go in right child and 2 go in left child again making it unfeasible because since 2 was in right child and 3 was in left child therefore we sorted but again reached the same dilemma. therefore the segment should not intersect.
Solution(submitted again with comments)->CodeChef: Practical coding for everyone
Hello, thank you for the editorial. Can you please help me with a test case in which my code is failing? I had used the approach in the editorial. So I am really confused where I am going wrong. I also tried various cases for an hour before giving up.
Thanks a lot for your help.
@ruddradev, in your print statement, you are printing tree[idx].rr, tree[idx].rr
Try tree[idx].ll, tree[idx].rr and see, you will spot the issue with the first test case.
1 Like
still didn’t get it.
3 Likes
Can anyone give explanation why top down approach fails or any test case ? @likecs @vijju123 @praveenkumar12
1 Like
For the bonus problem which the Editorialist put forward:
We could maintain something like a parent array which holds the information about the node whose son it is. After completely scanning the input, we could randomly pick a node and move up the parent array until its God parent is detected. The node which we end up now, will be the root node and we will solve this problem rooting with this node.
Pseudocode: (Modifications only)
for i = 1 to N:
parent[i] = i
for i = 1 to N:
scan L,R
if(L != -1):
#usual code
parent[L] = parent[R] = i
else:
#usual code
root=1
while(parent[root] != root):
root = parent[root]
solve(root)
Time Complexity for finding root: O(logN)
where the worst case would be randomly selecting a leaf node and moving all the way up in logN steps.
I hope this approach works.
1 Like
Can anyone help not albe to find where code fails.Did almost same as editorialist @likecs.
link-CodeChef: Practical coding for everyone
@atharva_sarage, did you consider the case that the tree may not be perfectly balanced?
ie) left child = leaf and right a tree or vice versa. The condition still needs to be satisfied even if one side is a tree.
Can someone please explain setter’s solution? I am not able to understand the meaning of statement :
if (kol[p] != mx[p] - mn[p] + 1) ok = false;
TIA.
Hey, I still couldn’t understand the problem statement. How the strings are LL,RL,RR and how the input is converted to a binary tree. Can anyone please explain it properly, that would be really helpful !
The question is interesting 
@likecs In question the constraints has N>=2 but if N=2 then its impossible to build the tree because in question there is mentioned that “non-leaf: has exactly two sons — a left son and a right son”,for root is doesn’t satisfy, am i right to point it out?
Still its a interesting question
Read about vectors. Refer to geeeksforgeeks for BFS and DFS implementations.
Please convert this input into tree
5
3 5
-1 2
2 4
-1 3
-1 1
1 is the root.each line gives 2 children l and r or l=-1 means it’s a leaf.
So 1st line 3,5. so node 3,5 are children of 1. 2nd line is -1,2. so 2nd node is a leaf with value 2. 3 line is 2,4. so 3rd node has chilren 2,4 and so on.
got it thank you!
Try debugging your code for some test cases. Take this one-
Input
1
3
2 3
-1 5
-1 7
Your Output
-1
Correct Output
0 //All leaves already sorted.
Find few more test cases like that and debug using them.
1 Like
Thanks for looking into the code. But the input that you give is invalid according to constraints as it is given in contraints for any child r is less than equal to number of leafs. So in this case L =2
So only possible values for childs is 1 and 2 not 5 and 7.
Oh…lol xD. I didnt use that constraint anywhere in my solution, so kind of missed that.