for each permutation i stored from j>i and j<N elements in a set and stored them as pair in vector. Eg 1324 {1,(3,2,4)}, {3,(2,4)}, {2,(4)} and if in other permutations there is an element such that it violates topological sort, i have removed those. Eg: if in new permutation {2,{1,3}} , so now i will have {1,(3,4)}, {3,(4)} from 1st permutation and second will have {2,()}. I have kept a frequency array to store how many time a number is occuring over all sets and then finally to choose which node will point its outer edge to which i thought of if a node has multiple elements choose which is least in frequency array and has’nt been used before. If all the elements have been used then the 1st element of the set is assigned to the node.
I hope i have explained my logic, Please help in any way possible
Using hash set has reduced the time constraints , its just adding then removing nodes which violates and is deciding just by observing which nodes to be used as the number of nodes with indegree has to be minimum.
I would love to but my solution is getting WA, waiting for pro coders to judge if my approach is correct or not. If they point me the mistake i will improve and explain you in detail.
@tri123
First of all i created a list where list[i] contained all the nodes except i which means that if n=5 then list[1] will contain 2,3,4,5 and list[2] will contain 1,3,4,5 and so on.Now for each of the next k lines which is a permutation of 1 to N , I took the input in array a and removed a[j] from the list of a[i] for all j<i and I did this for all i<=n.Let’s take an example;
Suppose the permutation is : 3 2 4 1 5
Then i removed 3 from list[2]
removed 3 and 2 from list[4]
removed 3,2 and 4 from list[1]
and removed 3,2,4 and 1 from list[5]
After doing this for each one of the k lines , i iterated over all the list and counted the occurence of each element in the list.
For eg:if list[1]=5
list[2]=4,5
list[3]=2,4,1,5
list[4]=1,5
list[5]=empty
then c[1]=2(in list[3] and list[4])
c[2]=1
c[3]=0
c[4]=2
c[5]=4
then created an array flag initialised to 0
Now for each i , the answer would be the node present in list[i] with minimum count && flag[node]==0 and if the list is empty or flag of all the elements is 1 then answer will be 0 and will set the flag[ans]=1
@everule1@anon38711361 can anyone of you tell me the right approach to this question, the video solution by @tmwilliamlin is his own unique observation. Your both approach is different i guess, it would be really great if you post an unofficial editorial.
Thanks in advance
I will try an explanation with a small example. Considere a case with N=4. If we put all nodes in two columns as shown in the image, an edge going from for example 2 in first column to 3 in the second means that 2 can be a child of 3. At the begining, that is, without taking account the given permutations yet, all nodes can be childs of all nodes (except itself), as you can see in the image.
Let’s consider that the first permutation that we are given is 1 2 3 4. That means that 1 can not be the child of other node (so remove the edges from 1 to all others), 2 can not be the child of 3 or 4 (so remove the edges from 2 to 3 and to 4), and so on. The two columns representation should look like this now.
The statement of the problem states that nodes of the second column can recibe at most one edge (they are the father of at most one node) so the problem now is reduced to keep as much nodes from column 1 connected to nodes of column 2 with the condition that at most one edge go to each of the nodes of the second column. To transform this into a max matching problem we have to be sure that at most one edge goes out from each node of column 1 but we can asume that because it’s irrelevant to our answer if a node is a child of one or more nodes, we just need to know if it can be a child of some node. So any max matching algorithm can give us the answer now. The answer will be N - matching.
Coming back to our example, after removing the minimum number of edges that let us stablish a one to one correspondence, the matching is 3, so our answer is 4 - 3 = 1.
