CHFNFRN - Editorial

editorial
, , , ,
21

What’s wrong with this solution?
link text

Checking the bipartiteness using dfs.

Thanks.

22

Showing wrong ans for test cases 1,4,7 what are the test cases?

23

@atulyaanand and @right_brained and @monikadaryani, I also used the same approach and it took me hours to find out the problem. Here is an example-
consider 6 friends with the relations as follows- 1-2, 1-5, 1-6, 2-3, 2-4, 3-4, 5-6
If you go on according to your algo you will find out that when you do it for friend number 5, it can not be placed in any group and hence results “NO”. But the solution is possible which is - table one- 1,5,6 and table two - 2,3,4. At first glance this algo seems to be correct solution but the thing is this is not even a solution, because it just simply does not meant to do what problem asks.

24

Hi All, in @author’s solution he used dfs on Graph G, it supposed to be on H i.e the complement of G can any one please explain why ?

25

Hello, can anyone point out the mistake in my approach, It only fails the first test case (with wrong answer) -

  1. If friends = 1 or 2, YES
  2. else if relations = 0, NO
  3. else if, for every friend-
  4. make an array “x” of people do not know him (have no relations with that particular friend)
  5. All the people in array “x” must know each other, If not, break, NO
  6. If loop ends naturally for all the friends in a test case, YES

In short - If there are any “Three” not related friends then the seating on two tables is not possible.

26

Hello Can someone explain what a clique is?

27

Nice problem and very good editorial. Learned lot’s of new things.

28

very similar to @arpitj2412


[1] faced same problem. Any walkthrough for this ?

  [1]: https://www.codechef.com/viewsolution/11441791
29

@dusht0814 if you want to know about the adjacency list implementation of this problem,then you can refer to my solution below
https://www.codechef.com/viewsolution/11405513

30

You haven’t given the link of the solution, which one should I see??

31

@arpitj2412 @debverine try this case 5 nodes 5 edges 1 2 2 3 3 5 4 5 1 4 output should be NO but your output is YES

32

here is my simple implementation and logic:

  1. make complement matrix
  2. make adjacency list from complement matrix
  3. then simply check graph is bipartite or not.

MyCode