CHEFDAG Video Solution

editorial
,
1

Official editorial coming soon
Video link: CHEFDAG Solution - CodeChef March Long Challenge 2020 - YouTube

7 Likes
2

I was eagerly waiting for this, even though I have solved it using intuition, I cant yet mathematically prove that my approach is correct. :laughing:

1 Like
3

https://www.codechef.com/viewsolution/30493537

can u please suggest me a test case where my code gives WA

4

5 3
1 4 5 2 3
1 3 4 5 2
4 1 5 2 3
Try this

1 Like
5

@rioji
i got
2
3 0 0 5 2
which i guess is correct.

6

https://www.codechef.com/viewsolution/30493537

Plz help me to find whats wrong in my code and show that with a test case …
I am not able to figure out whats wrong in it because it gives correct answer for all the test cases i tried…

8

Your greedy algorithm tries to solve maximum bipartite matching but fails. You should read up on other bipartite matching algorithms.

9

In my solution I did not divide the DAG into paths, but left edges such that some nodes had in-degree more than 1. I got Wrong Answer, although I think that such solutions should be allowed. Can someone please tell me whether (a) such solutions are allowed, and I made a mistake somewhere, or (b) the result must be divided into separate paths?

10

You should post the official editorial first before giving the video editorial.

2 Likes
11

Can anyone please check what could go wrong in my logic(or counter example):

1.create adjacency matrix and add edges for all permutation.
2.generate adjacency list from matrix and remove edges such as(if i->j and j->i remove both)
3.sort this list according to their size
4.generate graph from this (every time while adding edge check if this node(in degree>0) is already chosen and any other node available with in degree 0)

Here is code(with comments) link: CodeChef: Practical coding for everyone

12

Earlier I wrote greedy…It passed all tc in subtask 1 and three out of four in subtask 2…The tc are weak!!
link to my greedy solution-
https://www.codechef.com/viewsolution/30286504
link to my bipartite matching solution-
https://www.codechef.com/viewsolution/30288637

13

Can i apply LCS to all permuted sequences to get all the path from node( indegree==0)…atleast for N<10^3…??

15 
while(k--) {
	for(int i=0; i<n; ++i) {
		cin >> a[i], --a[i];
		//remove edges
		for(int j=0; j<i; ++j)
			adj[a[j]][a[i]]=0;
	}
}

consider
4 1
1 2 3 4
here why are we removing edges (1 3), (2 3), (1 4) ,(2 4) ,(3 4) what actually we are trying to do by removing this edge ?? please please help help!!!

17

5 3
1 4 5 2 3
1 3 4 5 2
4 1 5 2 3
Can the answer of this test case be 5 0 0 5 2

18

No.
its

2
3 0 0 5 2

the number of nodes with indegree 0 is 3 in your answer whereas it’s 2 in my answer

19

Getting correct solution for every test case that I tried

If anyone find any counter example please tell me.

Code link:CodeChef: Practical coding for everyone

20

This is my logic

21

In the video solution you said the each node can have at most 1 parent. Can you explain that?
According to the Question each node has outdegree <=1 which might result in two different nodes pointing to the same element and if that’s the case then a node can have more than 1 parent.

22

That will never be optimal. that node could have pointed to something else. Even if it couldn’t, it will not decrease the number of nodes with indegree 0. Therefore optimality can be retained when considering the maximum parents of each node as 1.

23

I am not constructing the complete counter example but a single stage. consider 3 vertices whose adjacency list is of size 2. E.g. 8 -{9,4}; 5-{4,6};3-{6,7}. When you are sorting the list assume the sorted sequence is 3,8,5. Now 3 picks 6 and 8 picks 4. With this assignment 5 is left with nothing. This is clearly not optimal.

1 Like