OJ Board

The Online Judge board
https://onlinejudge.org/board/

10505 - Montesco vs Capuleto

https://onlinejudge.org/board/viewtopic.php?t=3280

Page 5 of 5

Re: 10505 - Montesco vs Capuleto

Posted: Wed Jul 31, 2013 2:27 am
by 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

Re: 10505 - Montesco vs Capuleto

Posted: Wed Jul 31, 2013 4:22 am
by m.shawkey
thanks, your feedback was helpful :)

Re: 10505 - Montesco vs Capuleto

Posted: Fri Aug 08, 2014 2:20 am
by 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;
}

Re: 10505 - Montesco vs Capuleto

Posted: Fri Aug 08, 2014 11:04 pm
by brianfry713
Scarecrow wrote: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

Re: 10505 - Montesco vs Capuleto

Posted: Mon Sep 29, 2014 6:28 pm
by 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 :oops: !

Re: 10505 - Montesco vs Capuleto

Posted: Tue Sep 30, 2014 9:34 pm
by brianfry713
No, the output should be 0 in that case.

Re: 10505 - Montesco vs Capuleto

Posted: Thu Jan 01, 2015 10:51 am
by uradura
:oops: :oops: :oops: http://ideone.com/sWsedx
why wrong answer???
http://uva.onlinejudge.org/index.php?op ... oblem=1446

Re: 10505 - Montesco vs Capuleto

Posted: Thu Jan 01, 2015 3:28 pm
by 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

Re: 10505 - Montesco vs Capuleto

Posted: Thu Feb 05, 2015 6:21 pm
by just_yousef
this problem is driving me crazy :evil: :evil: :evil:
please tell me what is wrong with my code

Code: Select all

AC

Re: 10505 - Montesco vs Capuleto

Posted: Thu Feb 05, 2015 9:22 pm
by brianfry713
brianfry713 wrote: 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

Re: 10505 - Montesco vs Capuleto

Posted: Thu Feb 05, 2015 9:35 pm
by just_yousef
thanks :D

Re: 10505 - Montesco vs Capuleto

Posted: Sat Jan 02, 2016 1:08 am
by anacharsis
brianfry713 wrote: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?

Re: 10505 - Montesco vs Capuleto

Posted: Thu Jul 07, 2016 6:42 pm
by 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". :oops:

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

Thx

Christof

Re: 10505 - Montesco vs Capuleto

Posted: Thu Jul 07, 2016 8:32 pm
by 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!
All times are UTC+02:00
Page 5 of 5

Powered by phpBB® Forum Software © phpBB Limited