@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
@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
@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.
Please correct me if i’m wrong.
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.
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;
}
please provide some test cases.I tested my code with various inputs.But when i submit it shows wrong awnser for test case 1,4,7
@Antoniuk_Vasyl : n is not declared in your solution [Author’s solution]
Showing wrong ans for test cases 1,4,7 what are the test cases?
@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.
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 ?
Hello, can anyone point out the mistake in my approach, It only fails the first test case (with wrong answer) -
- If friends = 1 or 2, YES
- else if relations = 0, NO
- else if, for every friend-
- make an array “x” of people do not know him (have no relations with that particular friend)
- All the people in array “x” must know each other, If not, break, NO
- 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.
Hello Can someone explain what a clique is?
Nice problem and very good editorial. Learned lot’s of new things.
very similar to @arpitj2412
[1] faced same problem. Any walkthrough for this ?
[1]: https://www.codechef.com/viewsolution/11441791@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
You haven’t given the link of the solution, which one should I see??
@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