WA in CHEFDAG

[everule1]

It’s not optimal

2
3 0 0 5 2

[aashu_01]

@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

[carre]

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.

[avail2001]

Thanks a lot…Yeah the number of 0 indegree should be 3…

[anon38711361]

Here you go:

CHEFDAG - Unofficial Editorial

Hi, someone asked me to upload an editorial with my approach to CHEFDAG because it apparently seemed easier than the video tutorial. Here it is: Observations: It is suboptimal for the in-degree of any node to be >1 The resultant graph is based upon a topological sort so it will definitely be acyclic, we don’t have to specifically check If we restrict the in-degree and out-degree of all nodes to <= 1, the problem breaks down to finding the maximum number of edges we can create in the graph. N…

[aashu_01]

Thanks man!, great explanation .

[aashu_01]

Thanks for actually posting an editorial, it really helped.

[anon38711361]

No problem

[aashu_01]

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.

[carre]

Hopcroft–Karp

Sorry, I checked my solution and did’t use Hopcroft-Karp, It was the Hungarian (or Kuhn’s) algorithm

[idgaf_99]

Here’s an article on topcoder.