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
}
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
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
@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.
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.
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.
#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;
@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.
