Recently I was trying out a data structure problem and I couldn't solve it. Can anybody please help me to solve the problem, I would also like to know how to approach such problems.
Problem: You had lost a permutation p={1..N} and want to retrieve it. For each index 1<=i<=N you have the following information
1) The index j of the first number to the left of i such that p[j]>p[i].(It will be 0 if there is no such index)
2) the index j of the first number to the right of i such that p[j]>p[i].(It will be 0 if there is no such index)
The constraint on N is 5*10^5.
If multiple solution exists print the lexicographically smallest permutation.
Sample Input:
5
0 2
0 0
2 0
3 5
3 0
Sample Output: 1 5 4 2 3
Note: 4 5 3 1 2 is also valid but not the lexicographically smallest permutation.
You don't provide link to the problem and sample input, so I'm not sure I understand your question correctly.
If I had, then the solution maybe: add an edge from every j to i (if j==0, add no edge and continue), then get the topological order of this graph and they are corresponding to {N,N-1.....,2,1}.
Sorry for not providing the link or sample input. I will add it for future readers. I think you understood the question correctly.
Yes!!!! the solution you mentioned works. Can you please elaborate on how you got to this solution. I mean the thinking process in getting to the solution. I am new to data structures and struggle to solve problems
I think I should explain from two terms: "why graph?" and "why topological?".
I make a sample permutation like "43152" and try to solve it.
The information of 43152 is: (1)01101 (2)44400
Then, you may find it's hard to deal the information in such format. So, you may try to visualize such information by drawing some arrow on the original "43152" permutation. So far, we get a directed graph and that's how you may realize this problem has sth to do with graph.
Then, trying to solve this sample with human brain, you may find that the maxinum one is easy to find: the position whose both information is zero, since there isn't a number greater than the maxinum one. Having found the maxinum one, you may think that "it would be great if I can solve the remaining problem with the same way" . However, you then find that there are no more position which has both 0-information. Why? Because "5" have some influence on "4" so "4" can't be found by keeping doing the "find position with double 0-information". Then, you may try to find a way to make 5-on-4-influence vanish so that you can solve the subproblem in the same way. So far, it's enougn to realize that the algo I discribed above is exactly what topological sort do. That's how you may think of topological order.
What's more, topological sort requires there are no cycle in the graph. Can this always hold in this problem? Yes, because a cycle in this problem means there is some number who is greater than itself, which is impossible.
However, in fact, I didn't think that much. I just knew that a partial relation often have sth to do with DAG and DAG often have sth to do with topological sort lol
Really nice explanation!!!
I knew that the maximum was easy to find and it's "influence" on other numbers. I was trying to draw out cases like if 2nd maximum is on the left or right then what will happen, if 3rd maximum is on the left and right and so on lol. I made it so complicated and then gave up.
Lol didn't thought it would become a simple DAG problem
Thank you