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

witto
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:

10505 - Montesco vs Capuleto

Post by witto » Thu Jun 19, 2003 4:32 am

What should be the output for this input:
1

2
0
1 5

It seems that the judge input has something like that.
I've put an assert() to check that.

As for the algorithm, I'm trying to find all the bipartite components of the graph build from input and inviting the people from the bigger set of each bipartition. Does that solve the problem?


Thanks in advance,
Witto

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Jun 19, 2003 11:26 am

You can ignore the numbers >n (it makes no difference if you do it or not if your algorithm is correct).
When you search for bipartite components, and you find out that they are not bipartite, do you mark all nodes in the component so that you don't use them again? That was my mistake.
If I understand your algorithm, it should solve the problem.

witto
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:

Solved...

Post by witto » Fri Jun 20, 2003 1:20 am

I was missing out something in the vertex coloring process....
I rewrote the function and got accepted.

Many thanks.
[]'s
Witto

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

Is input correct?

Post by Alexander Kozlov » Wed Jun 25, 2003 5:46 pm

Is this input correct?

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

If YES what sould be the answer: 0 or 3?

lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

My guess

Post by lucindo » Wed Jun 25, 2003 11:36 pm

My accepted program outpus '0' for this input
[]'s

Lucindo

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: My guess

Post by windows2k » Wed Jul 02, 2003 11:16 am

lucindo wrote:My accepted program outpus '0' for this input
What about the input?
3

6
1 2
2 3 1
1 4
2 1 2
3 1 2 3
1 1

6
2 23
1 3
1 1
1 6
1 4
0

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

thx

lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

Post by lucindo » Wed Jul 02, 2003 5:50 pm

Hello windows2k,

The output of my program for this input is:

Code: Select all

0
1
1
I used the algorithm that witto wrote above.
[]'s

Lucindo

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Thu Jul 03, 2003 6:09 pm

lucindo wrote:Hello windows2k,

The output of my program for this input is:
1
[/code]

I used the algorithm that witto wrote above.
Can you tell me why the ans is 1
8
2 2 4
1 3
1 4
0
3 6 7 8
2 7 8
1 8
0

if i choose 1 and 3 or 2 and 4,we can choose two
or i misunderstanding the meaning?

witto
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:

Re: My guess

Post by witto » Fri Jul 04, 2003 2:59 am

windows2k wrote:
lucindo wrote:My accepted program outpus '0' for this input
What about the input?
3
(...)
thx
The output of my solution for that input is:

Code: Select all

0
2
2
Good Luck
[]'s
Witto

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: My guess

Post by windows2k » Fri Jul 04, 2003 4:03 am

The output of my solution for that input is:

Code: Select all

0
2
2
Good Luck[/quote]
To witto,My program outputs the same result
But I get WA:(
Could someone tell me what's wrong
[cpp]
#include <stdio.h>
#include <string.h>
bool graph[201][201];
char color[201];
int cc[2];
int n;
bool DFS(int node,int cn)
{
color[node]=cn;
cc[cn]++;
for(int i=1;i<=n;i++)
if(graph[node])
{
if(color==cn) return false;
if(color==-1)
{
if(!DFS(i,1-cn)) return false;
}
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(graph,false,sizeof(graph));
memset(color,0xff,sizeof(color));
for(int i=1;i<=n;i++)
{
int l,t;
scanf("%d",&l);
for(int j=0;j<l;j++)
{
scanf("%d",&t);
graph[t]=graph[t]=true;
}
}
int ans=0;
for(int i=1;i<=n;i++)
if(color==-1)
{
cc[0]=cc[1]=0;
if(!DFS(i,0)) continue;
if(cc[0]>cc[1]) ans+=cc[0];
else ans+=cc[1];
}
printf("%d\n",ans);
}
return 0;
}
[/cpp]

witto
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:

Post by witto » Sat Jul 05, 2003 3:38 am

Try doing a BFS insted of DFS... it worked for me.
[]'s
Witto

huksy
New poster
Posts: 3
Joined: Sun Jul 13, 2003 7:00 pm

hmm.. the code above

Post by huksy » Sun Jul 13, 2003 7:03 pm

I think you just made a mistake//

variable t is simply duplicated.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: hmm.. the code above

Post by windows2k » Mon Jul 14, 2003 9:24 am

huksy wrote:I think you just made a mistake//

variable t is simply duplicated.
I don't understand your meaning :(
Could you explain more clearly , thx :)

huksy
New poster
Posts: 3
Joined: Sun Jul 13, 2003 7:00 pm

Post by huksy » Mon Jul 14, 2003 12:25 pm

outer while lv t & inner t 8) :P

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Mon Jul 14, 2003 4:09 pm

huksy wrote:outer while lv t & inner t 8) :P
I have modified my code,but still get WA.
Maybe there exists some trick input? @@

Post Reply

Return to “Volume 105 (10500-10599)”