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.
Problem link : CodeChef: Practical coding for everyone
My Solution : https://www.codechef.com/viewsolution/30307347
Correct solution (of @vd_patel ) : CodeChef: Practical coding for everyone
I have checked my code and vd_patel’s code on like 15-16 different input and everytime both output are same but still i am getting WA in all subtask.
so, can you please tell me where am I going wrong or any testcase where my output is wrong.
can i know what approach did you followed?
@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
I used the same logic.
Can you please help me?@anon38711361
Problem link : CodeChef: Practical coding for everyone
My Solution : https://www.codechef.com/viewsolution/30307347
Correct solution (of @vd_patel ) : https://www.codechef.com/viewsolution/30378162
I have checked my code and vd_patel’s code on like 15-16 different input and everytime both output are same but still i am getting WA in all subtask.
so, can you please tell me where am I going wrong or any testcase where my output is wrong.
5 3
1 4 5 2 3
1 3 4 5 2
4 1 5 2 3
Can the output of the code be
2
5 0 0 5 2
Please help me to clear my confusion?
Okay I see the problem with this. I was trying a similar approach in the beginning. Think of a case like this:
list[1] = {3, 4}
list[2] = {3}
list[3] = {}
list[4] = {3}
In this case, I think you will output
3
3 0 0 0
Whereas the right answer is
2
4 3 0 0
I don’t know if this is the optimal solution but your edges are valid. However, should it not be
3
5 0 0 5 2
?
It’s not optimal
2
3 0 0 5 2
@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.
Thanks a lot…Yeah the number of 0 indegree should be 3…
Here you go:
1 Like
Thanks man!, great explanation .
Thanks for actually posting an editorial, it really helped.
No problem 
You have used dfs in your code to find match, can you tell what is the name of this algorithm as it seems easier to understand than maximum bipartite matching. And best resource to learn n understand this algo.
Sorry, I checked my solution and did’t use Hopcroft-Karp, It was the Hungarian (or Kuhn’s) algorithm
1 Like