CHFNFRN - Editorial

djdolls · September 15, 2016, 2:55pm

PROBLEM LINK:

Practice
Contest

Author: Antoniuk Vasyl
Tester: Praveen Dhinwa
Editorialist: Ajay K. Verma

DIFFICULTY:

Easy

PREREQUISITES:

Graph Complement, Two-coloring.

PROBLEM:

Given a graph G = (V, E), determine, whether its vertices can be partitioned into two sets V1 and V2, such that both V1 and V2 form a clique in G.

QUICK EXPLANATION:

Such a partition is possible, iff the complement of graph G is a bipartite graph.

EXPLANATION:

Suppose for a given graph G = (V, E), we can partition the vertices into two sets V1 and V2, such that both V1 and V2 form a clique in G.

Let us say that H = (V, E’) is the complement graph of G, which has the same vertex set as that of G, however an edge (u, v) exists in H iff the edge (u, v) does not exist in G, and vice versa.

Since V1 forms a clique in G (i.e., all vertices of V1 are connected with each other via an edge), it must form an independent set in H (i.e., no two vertices of V1 are connected by an edge in H). The same holds for the set V2.

In other words, the vertex set V can be partitioned into two sets V1 and V2, such that both V1 and V2 form independent set in H. In other words, all edges of H are of the form (u, v), where u belong to the set V1, and v belong to the set V2. In other words, H is a bipartite graph.

Hence, we only need to check whether the graph H is a bipartite graph. This can be done in the linear time (in the number of edges and vertices) using a depth first traversal of the graph as shown here.

TIME COMPLEXITY:

O (N²), where N is the number of vertices in the graph.

Note that the bipartiteness can be checked in linear time, however the complement of input graph may have quadratic number of edges. Hence, the complexity of this method is O (N²).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution will be uploaded soon.

lavee_singh · September 15, 2016, 5:08pm

I just simply implemented the problem statement. What I did was,

Take a person and seat him on the first table(took a set). (This person is preferred to be the one with minimum acquaintances).
For person in the rest of them:
1. if person can’t sit on either(not both) of the tables(there is a person who is not acquaintance): seat him onto the other(making sure he doesn’t conflict there)
2. if person can sit on both of the tables(all of the person on both of the tables are acquaintances): make him wait until others take place
3. if person can’t sit either of the tables: solution is not possible
4. if any unseated person remains, repeat the process.

Here is the code for the same: here

arpitj2412 · September 16, 2016, 12:32am

I tried to solve it in the following way:

Create a 2d n*n matrix. Let say arr.
For j=0:n-1, arr[j][j]=1. "Each of one knows himself.
For every a,b - arr[a-1][b-1]=1 and arr[b-1][a-1]=1. "if a knows b -> b knows a.
Now my logic was to find three different index from the matrix arr - i,j,k such that following equations holds true:
arr[i][j]=0;
arr[i][k]=0;
arr[j][k]=0;
which indicates that there exists three members who doesn’t know each other. Hence can not be seated at the two tables.
But till end I wasn’t able to figure out what’s wrong with this logic as 3 test case failed. Can anyone help? Here is the code for the same: https://www.codechef.com/viewsolution/11389725

explorer · September 16, 2016, 1:06pm

I tried to solve using a different approach:

For every person calculate total friends of it.
create two sets.
pushed person with minimum friends onto first set.
took the next person with minimum friends and checked if it can be accommodated in any of the two sets.
if it cant be accommodated then not possible to have a seating arrangement.
repeat for every element.
If all got seated a seating arrangement is possible.
Getting wrong answer for 7th test case.
Code: https://www.codechef.com/viewsolution/11468337

utkarshg_1998 · September 16, 2016, 1:41pm

@lavee_singh By repeat the process did you mean to say that apply the previous algorithm(above three steps) on these new set of friends?.I tried the same but it was giving wrong answer on one of the test cases of subtask 2.

atulyaanand · September 16, 2016, 3:46pm

I just simply implemented the problem statement. What I did was,

Take a person and seat him on the first table(took a set)).
For the remaining people:
if person knows person1, make him sit in table1.
if person does not know person1, make him sit on table2.
Check if all people in table2 know each other.
If not, display “NO”.
If yes, add each person to table2 and check if they can belong in table2 or not. Those possible,
add them to table2. If not, let them be in table1.
Check if all people in table1 know each other.
If not, display “NO”
If yes, display “YES”.
However, the solution FAILS in 3 test cases out of 12. Please help.

Here is the code for the same: here

prakhariitd · September 16, 2016, 4:22pm

@atulyaanand

The problem is when person can go in both groups you add it to group 1, that is where your code is wrong.

Note: that person can only be temporarily in both the groups not necessariliy after complete groups are formed.

It might happen that putting that person in group 2, allows the groups with desired property to be formed and putting the person in group 1 doesn’t allow the groups to be formed.

debverine · September 16, 2016, 9:51pm

very similar to @arpitj2412


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

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

monikadaryani · September 16, 2016, 10:07pm

@prakhariid
Can u suggest an example for this ? Even I have those 3 same cases fail.

right_brained · September 16, 2016, 10:14pm

I tried to solve it with a simple approach without using any non-linear data structures. It worked perfectly on Dev C++ but gave RE(SIGSEGV) on IDE and on submission.
My approach was this -

Declare two arrays for two tables, let the first friend sit on the first table
Loop from 2 to N to choose the next friend. Then check if he knows all the people sitting on the first table. If yes, then he sits there.
If not, check if he knows all the people sitting on the second table. If yes, he sits there.
If not, print No.
If everything goes right, print Yes.
The approach may be similar to many others, but I used just one header file -> stdio.h

Can somebody go through [it][1] and find the mistake?
[1]: https://www.codechef.com/viewsolution/11517302

ktime · September 16, 2016, 10:17pm

My program failed on test case 7. I used the below approach. I could not come up with any test case that could break my algorithm. ( this is the 3’rd forum where I am asking this (TC,STKOVFL :()
Algorithm:

bool current_placed = false
For (loop) all the friends in the sorted list do the below
  current_placed = false
  if (TA empty) {
      Place current friend on TA
      current_placed = true
  } else {
      // If current friend is connected with all the people already seated on TA.
     if(current friend connected with all on TA){
        Place current friend on TA too.
        current_placed = true
     }
  }

  if(current_placed == false){
     If (TB empty) {
        Place current friend on TB
        current_placed = true
     } else {
       // If current friend is connected with all the people already seated on TB
       if(current friend connected with all on TB){
          Place current friend on TB too.
          current_placed = true;
       } 
    } 
  } 
  if(current_placed == false) {
    ans => NO
    break starting for loop
  } 
// For loop ends
if(current_placed == true) {
   ans => YES
}

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

ktime · September 16, 2016, 10:22pm

@atulyaanand and @right_brained and @monikadaryani
I think you algorithm might break for the below scenario

4 ---- 1 ---- 2 -----3 as you are placing 1, 2, 3, 4 in that order. Where as for this you should place
( 3 and 4 should be placed in any order before 1 and 2)
3,4,1,2
or
4,3,1,2

ktime · September 16, 2016, 10:38pm

@admin and @dpraveen and @djdolls and @antoniuk1

Now that the contest is over, can the admins share the test data, it would save the WA ers … lot of time as we can figure out the problem with our algorithms ourselves

rajesh_jangid6 · September 17, 2016, 12:10am

@arpitj2412 Your code fails for the following test case
1
5 5
1 2
1 3
2 4
3 5
4 5
It should print NO

atulyaanand · September 17, 2016, 5:18pm

@prakhariitd
Thanks for replying. However, I forgot to mention that after I check connection among people in table 2, I also check for each person in table1 whether it’s possible for them to be in table2. If possible, I add them to table2. When none of the persons in table1 can be added to table2, I check if all of the people in table1 know each other. Only, then I display YES or NO. Please check my code.

dusht0814 · September 17, 2016, 6:48pm

I’d like to know the adjacency list implementation of this problem.According to me time limit would exceed as for constructing a complimentary graph for each edge given e(Vi,Vj) we have to iterate from (1 to Vj) and (1 to Vi) and then disconnect both the edges from each other’s adjacency list by erasing it.Thus for M edges we have to iterate from 1 to Vi and from 1 to Vj.

Please correct me if i’m wrong.

naksh9619 · September 17, 2016, 9:09pm

@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

prakhariitd · September 17, 2016, 9:12pm

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

naksh9619 · September 17, 2016, 9:33pm

@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

deepcpp · September 17, 2016, 11:15pm

Can anyone please tell me what’s wrong in my code for Chef and Friends problem:

My logic is:

Create a boolean array in which initially all elements are initialised to false
Make the first person sit on the first table and then check whether all the people the first person knows, knows all the rest of the members and mark them as visited in the boolean array i.e, if the first person knew the members 5,7,9 then check whether 5 knows 7,9,1; 7 knows 9,5,1; 9 knows 5,7,1 and if anyone of them abides by the given condition then mark them as visited.
Then let x be the first person not visited. Find all the non-visited neighbours of x such that they know all the other non-visited neighbours of x, i.e, if the non-visited neighbours of x are 3,10,11 then check whether: 3 knows 10,11,x; 10 knows 11,3,x; 11 knows 3,10,x and if they abide by the condition mark them as visited in the boolean array.
If the complete boolean array’s elements are true then answer is YES else NO.

Probem is that my code gives WA for TASK# 1,4,7. and gives AC for all the other TASKS.

LInk to my submission.

Code:

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifndef ONLINE_JUDGE
 freopen("t.in","r",stdin);
#endif

int t;
scanf("%d",&t);

while (t--) {
	int n,m;
	scanf("%d %d",&n,&m);

	vector<set<int> > g(n+1);
	
	for (int i = 1; i <= m; ++i) {
		int a,b;
		scanf("%d %d",&a,&b);
		
		g[a].insert(b);
		g[b].insert(a);
	}

	for (int i = 1; i <= n; ++i)
		g[i].insert(i);

	bool visited[n+1];
	memset(visited,0,n+1);
	int seen = 0;

	for (auto first = g[1].begin(); first != g[1].end(); ++first) {
		bool flag = 1;

		for (auto beg = g[1].begin(); beg != g[1].end(); ++beg)
			if (g[*beg].find(*first) == g[*beg].end()) {
				flag = 0;
				break;
			}


		if (flag && !visited[*first]) {
			visited[*first] = 1;
			++seen;
		}
	}

	//cout << seen << '\n';
	if (seen == n) {
		puts("YES");
		continue;
	}

	int index = -1;

	for (int i = 1; i <= n; ++i) 
		if (!visited[i]) {
			index = i;
			break;
		}
	//cout << index << '\n';

	for (auto first = g[index].begin(); first != g[index].end(); ++first) {
		bool flag = 1;

		if (!visited[*first]) {

			for (auto beg = g[index].begin(); beg != g[index].end(); ++beg) 
				if (!visited[*beg] && g[*beg].find(*first) == g[*beg].end()) {
					flag = 0;
					break;
				}
			
			
		}

		if (flag && !visited[*first]) {
			visited[*first] = 1;
			++seen;
		}
	}

	if (seen == n)
		puts("YES");
	else
		puts("NO");
}

return 0;

}