10505 - Montesco vs Capuleto

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10505 - Montesco vs Capuleto

Post by brianfry713 » Wed Jul 31, 2013 2:27 am

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
Check input and AC output for thousands of problems on uDebug!

m.shawkey
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

Re: 10505 - Montesco vs Capuleto

Post by m.shawkey » Wed Jul 31, 2013 4:22 am

thanks, your feedback was helpful :)

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 10505 - Montesco vs Capuleto

Post by nbacool2 » Fri Aug 08, 2014 2:20 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10505 - Montesco vs Capuleto

Post by brianfry713 » Fri Aug 08, 2014 11:04 pm

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
Check input and AC output for thousands of problems on uDebug!

cshung_test
New poster
Posts: 4
Joined: Mon Sep 29, 2014 6:25 pm

Re: 10505 - Montesco vs Capuleto

Post by cshung_test » Mon Sep 29, 2014 6:28 pm

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: !

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10505 - Montesco vs Capuleto

Post by brianfry713 » Tue Sep 30, 2014 9:34 pm

No, the output should be 0 in that case.
Check input and AC output for thousands of problems on uDebug!

uradura
New poster
Posts: 11
Joined: Thu Jan 01, 2015 10:31 am

Re: 10505 - Montesco vs Capuleto

Post by uradura » Thu Jan 01, 2015 10:51 am


bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 10505 - Montesco vs Capuleto

Post by bradd123 » Thu Jan 01, 2015 3:28 pm

@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
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10505 - Montesco vs Capuleto

Post by just_yousef » Thu Feb 05, 2015 6:21 pm

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

Code: Select all

AC
Last edited by just_yousef on Thu Feb 05, 2015 9:36 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10505 - Montesco vs Capuleto

Post by brianfry713 » Thu Feb 05, 2015 9:22 pm

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
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10505 - Montesco vs Capuleto

Post by just_yousef » Thu Feb 05, 2015 9:35 pm

thanks :D

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 10505 - Montesco vs Capuleto

Post by anacharsis » Sat Jan 02, 2016 1:08 am

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?

catweazle352
New poster
Posts: 10
Joined: Wed Aug 14, 2013 7:53 pm

Re: 10505 - Montesco vs Capuleto

Post by catweazle352 » Thu Jul 07, 2016 6:42 pm

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
It's easy to beef about something - but it's much harder to make it better

catweazle352
New poster
Posts: 10
Joined: Wed Aug 14, 2013 7:53 pm

Re: 10505 - Montesco vs Capuleto

Post by catweazle352 » Thu Jul 07, 2016 8:32 pm

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!
It's easy to beef about something - but it's much harder to make it better

Post Reply

Return to “Volume 105 (10500-10599)”