10505 - Montesco vs Capuleto

[brianfry713]

It looks like your check function is wrong. Try to check at the same time as you run the BFS.
Input:

Code: Select all

1

5
2 2 3
2 1 3
2 1 2
1 5
1 4

AC output:

Code: Select all

1

[m.shawkey]

thanks, your feedback was helpful

[nbacool2]

Can someone help with my code? It passes all the tests in the topic + the sample in the problem statement but I still get WA.

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <utility>
using namespace std;
int N;
vector<int> G[201];
bool visited[201];
int color[201];
vector<int> answers;

int BFS(int root)
{
    queue<int> Q;
    visited[root] = true;
    color[root] = 0;
    Q.push(root);
    bool isBipartite = true;
    int totalSize = 0;
    int black = 0;
    while(!Q.empty())
    {
        int current = Q.front(); Q.pop();
        if(color[current] == 1) ++black;
        ++totalSize;
        for(int i = 0; i < G[current].size(); ++i)
        {
            int child = G[current][i];
            if(!visited[child])
            {
                color[child] = 1 - color[current];
                visited[child] = true;
                Q.push(child);
            }
            else if(color[current] == color[child])
            {
                isBipartite = false;
            }
        }
    }
    //if(isBipartite) cout<<"IT IS\n";
    ////else cout<<"IT IS NOT\n";
    if(isBipartite) return max(black, totalSize - black);
    else return 0;
}
void read()
{
    for(int i = 0; i < 201; ++i) G[i].clear();
    memset(visited, 0, sizeof visited);
    memset(color, -1, sizeof color);
    //now do shit
    cin >> N;
    for(int i = 1; i <= N; ++i)
    {
        int p;
        cin >> p;
        for(int j = 0; j < p; ++j)
        {
            int enemy;
            cin >> enemy;
            G[i].push_back(enemy);
            G[enemy].push_back(i);
        }
        //cout<<" left i: "<<i<<endl;
    }
    int result = 0;
    for(int i = 1; i <= N; ++i)
    {
        if(!visited[i])
        {
            //cout<<"ROOT: "<<i<<endl;
            result += BFS(i);
        }
    }
    answers.push_back(result);
}
int main()
{
    ios::sync_with_stdio(false);
    int M;
    cin >> M;
    for(int i = 0; i < M; ++i)
    {
        read();
        //cout<<"left case: "<<i<<endl;
    }
    //cout<<"Answers:\n";
    for(int i = 0; i < M; ++i)
    {
        cout<<answers[i]<<'\n';
    }
    return 0;
}

[brianfry713]

some input sets are like this. be sure to handle these

Code: Select all

1

5
5 2 4 6 8 10
3 1 3 6
0
0
3 1 6 7

output

Code: Select all

3

[cshung_test]

Wouldn't the problem becomes the maximum independent set problem (which is NP complete) if the graph is allowed to be non-bipartite?

For example,
1 is enemy of 2
2 is enemy of 3
1 is enemy of 3

We can still invite 1.

This problem is full of problems !

[brianfry713]

No, the output should be 0 in that case.

[uradura]

http://ideone.com/sWsedx
why wrong answer???
http://uva.onlinejudge.org/index.php?op ... oblem=1446

[bradd123]

@uradura, In set of connected components, if one component is not bipartite, your program does not give the answer of other bipartite components result
For Example take this input

Code: Select all

1

2 2 3
2 1 3
3 1 2
1 5
1 4

Your code gives 0,but the AC answer is 1

[just_yousef]

this problem is driving me crazy
please tell me what is wrong with my code

Code: Select all

AC

[brianfry713]

Input:

Code: Select all

1

5
2 2 3
2 1 3
2 1 2
1 5
1 4

AC output:

Code: Select all

1

[just_yousef]

thanks

[anacharsis]

No, the output should be 0 in that case.

Why is this the case though?
The problem statement is that a person will accept an invite provided none of his enemies are invited and all of his friends are.
Person 1 has no friends and 2 enemies.
So inviting him should be ok?

[catweazle352]

Hi,

I tested my code with all examples of this thread from page 1 to page 5. Moreover, I used UDebug input with 266 test cases and my output is the same with that of UDebug, but still WA.

My algorithm is as follows:
- I did take into account the case of "neutral" persons who have neither friends nor enemies (of course, each person is a friend of himself)
- I did take into account the case of "contradictory" relationships, i.e. person A is enemy of person B which is enemy of person C which is enemy of person C. In that case I do not invite any of these persons

Technically I use a Bitset of "forbidden" persons, these are those, who have had a contradictory relationship, another Bitset of "neutral" persons.
Moreover I use basically a pair of Bitsets for each person, one for its friends and one for its enemies. Practically, in most cases there are onyl a few pairs of bitsets, because I merge Bitsets whenever possible.

Example: I have Bitset[3] = {1,5,10}, Bitset[4] = {2,3,11,12}, Bitset[5]={6,7,8} and Bitset[6]={9}. This means, that 1,5 and 10 are friends and they have common enemies 2, 3, 11 and 12. 6, 7 and 8 are friends and have the common enemy 9.

If the new enemy relationship e.g. 12,7 is detected, Bitset[4] and Bitset[5] are merged as well as Bitset[3] and Bitset[6].
If the new enemy relationship e.g. 5,10 is detected, {1,5,10,2,3,11,12} all enters the "forbidden" Bitset and Bitset[3] and [4] are deleted (cleared).
If the new enemy relationship e.g. 9,4 is detected and 4 is already in the "forbidden" Bitset, Bitset [6] and Bitset[5] are merged into the "forbidden" Bitset.

and so on.

At the end of my algorithm I initialize countOfGuests to zero, loop thru my Bitset array and for each pair of bitsets add the number of the bigger one (enemy or friend one), i.e. of each bipartit component I add the bigger one.

After that I compare the neutral persons with the forbidden and delete all forbidden persons from the neutral persons. After that I add the remaining neutral persons to the countOfGuests.

I also checked cases with invalid person numbers, which I do ignore.

As I said before, I checked the algorithm with all test cases in this thread and 266 test cases of UDebug. All is fine.

But not for the Judge, who says "WA".

Does anybody see the mistake in my algorithm or can at least provide me with a critical test case?

Thx

Christof

[catweazle352]

Hi,

I finally got AC. For all others:
There are inputs like this (i.e. A Person may be an enemy of himself(!!))

Code: Select all

2

1
1 1

2
1 1
2 1

AC output is

Code: Select all

0
0

Good luck!