10301 - Rings and Glue

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

Moderator: Board moderators

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

Post by adnan2nd » Fri Oct 07, 2005 12:39 pm

chok's 1st algorithm was wrong.
if there r 4 rings, and (1,3) ,(2,3),(2,4) are coonected pair answer should be 4, not 3.
set union- is OK.
sobhani

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

I still got WA :'(

Post by FAQ » Sun Mar 05, 2006 8:13 am

I searched forum for some tests and passed all of them, but still WA. Please help me

Code: Select all

Aced
Last edited by FAQ on Sun Mar 05, 2006 12:06 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Mar 05, 2006 8:48 am

Read the 'Output' section carefully.
"The largest component contains 1 rings." isn't a grammatically correct answer.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sun Mar 05, 2006 12:06 pm

I got AC, the mistake you mentioned + another mistake in compiler
Thanks a lot

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

10301 Glued with WA

Post by shihabrc » Fri Jul 14, 2006 9:20 pm

Hi all,

I've tried 2 solve this prob with DFS. But getting WA. I've considered 2 circles overlap if dist. between centres >=sum of rad && <=difference of rad. And I've printed "0 rings". instead of"0 ring". Can some1 hlp plz. I'm givin the code below.





Code: Select all

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>

using namespace std;

#define EPS 1e-9
#define SIZE 100

typedef struct Circle
{
	double x,y,rad;
} Circle;

typedef struct Adj_list_
{
	vector<int> v;
} Adj_list;

Circle ring[SIZE];
bool visited[SIZE];
int colour[SIZE];
Adj_list_ adj[SIZE];
int nRings,component;

void build_graph();
void DFS();
void visit(int);

void main()
{
	int i,max,temp;
	
	//freopen("C:\\4.txt","rb",stdin);

	while(scanf("%d",&nRings)==1)
	{
		if(nRings<0) break;

		for(i=0;i<nRings;i++)
		{
			colour[i]=0; 
			adj[i].v.clear();
			visited[i]=false;
			scanf("%lf%lf%lf",&ring[i].x,&ring[i].y,&ring[i].rad);
		}
		
		build_graph();
		DFS();
		max=-1;

		for(i=1;i<=nRings;i++)
		{
			temp=count(colour,colour+nRings,i);
			if(temp>max) max=temp;
		}

		if(max==1) printf("The largest component contains %d ring.\n",max);
		else printf("The largest component contains %d rings.\n",max);

	}
}

void build_graph()
{
	int i,j;
	double dist;
	for(i=0;i<nRings;i++)
	{
		for(j=i+1;j<nRings;j++)
		{
			dist=sqrt((ring[i].x-ring[j].x)*(ring[i].x-ring[j].x)+(ring[i].y-ring[j].y)*(ring[i].y-ring[j].y));
			if(dist<ring[i].rad+ring[j].rad || fabs(dist-fabs(ring[i].rad+ring[j].rad))<EPS )
			{
				if(dist>fabs(ring[i].rad-ring[j].rad) || fabs(dist-fabs(ring[i].rad-ring[j].rad))<EPS )
				{
					adj[i].v.push_back(j);
					adj[j].v.push_back(i);
				}
			}
		}
	}
}

void DFS()
{
	int i;
	component=1;

	for(i=0;i<nRings;i++)
	{
		if(!visited[i])
		{
			visit(i);
			component++;
		}
	}
}

void visit(int u)
{
	int i,size;
	visited[u]=true;colour[u]=component;
	
	size=adj[u].v.size();

	for(i=0;i<size;i++)
	{
		if(!visited[adj[u].v[i]])
			visit(adj[u].v[i]);
	}
}
-Shihab
Shihab
CSE,BUET

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Thu Jan 11, 2007 2:05 pm

I used set-union to solve the problem but it always got WA
My code as follow
Who can help me to find the mistake?

Code: Select all

I find my mistake and get AC!

The input data
4
0.0 0.0 1.0
-1.5 -1.5 0.5
1.5 1.5 0.5
-2.0 2.0 3.5
3
3.0 2.0 2.0
0.0 -0.5 1.0
0.0 0.0 2.0
5
-2.0 0.0 1.0
1.0 -1.0 1.0
0.0 1.0 0.5
2.0 0.0 1.0
-1.0 1.0 1.0
4
0.0 0.0 1.0
0.0 2.1 1.0
0.0 .5 1.0
-2.0 2.0 3.5
2
0.1 0.1 1.1
0.0 0.0 1.0
-1
My Output:
The largest component contains 4 rings.
The largest component contains 2 rings.
The largest component contains 3 rings.
The largest component contains 3 rings.
The largest component contains 2 rings.
Last edited by IRA on Fri Jan 12, 2007 7:09 pm, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jan 11, 2007 5:26 pm

My accepted code returns the following

Output:

Code: Select all

The largest component contains 4 rings.
The largest component contains 2 rings.
The largest component contains 3 rings.
The largest component contains 4 rings.
The largest component contains 2 rings.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Fri Jun 29, 2007 9:48 am

Why WA???? Please help......
Last edited by shakil on Sat Jun 30, 2007 6:34 am, edited 1 time in total.
SHAKIL

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Jun 29, 2007 10:17 am

Before posting your code, make sure that it passes the samples correctly.
Ami ekhono shopno dekhi...
HomePage

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Sat Jun 30, 2007 6:32 am

shakil wrote:Why WA???? Please help......

Code: Select all

#include<stdio.h>
#include<math.h>
long double x[109],y[109],t,t1,r[109];

void main()
{
long n,i,j,count,max;

while(1)
{
scanf("%ld",&n);
if(n==-1)
break;

for(i=0;i<n;i++)
scanf("%Lf %Lf %Lf",&x[i],&y[i],&r[i]);

max=0;

for(i=0;i<n;i++)
{
count=0;

for(j=0;j<n;j++)
if(i!=j)
{
t=x[i]-x[j];
t=t*t;
t1=y[i]-y[j];
t1=t1*t1;
t=t+t1;
if(t<=(r[i]+r[j])*(r[i]+r[j]))
{
	t1=r[i]-r[j];
	if(t1<0)
	t1=-t1;
if(t1*t1<=t)
count++;
}
}
count++;
if(count>max)
max=count;
}

printf("The largest component contains %ld ring", max);
if (max != 1) printf("s"); 
printf(".\n");
}
}
Jan now you can help me.....
My program give all output of the sample input.......
SHAKIL

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

Post by asmaamagdi » Thu Oct 18, 2007 11:24 pm

Can someone tells me the output for:
2
0 0 1
0 0 1

Should it be 1 ring or 2 rings??!!
---
Asmaa Magdi

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Oct 20, 2007 5:21 pm

My code prints 1 ring for your case.
Ami ekhono shopno dekhi...
HomePage

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

Post by asmaamagdi » Sat Oct 20, 2007 6:01 pm

Thnx Jan for ur reply.
This is what I was doing before and I got WA. I really don't know the trick here :S
---
Asmaa Magdi

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Oct 20, 2007 10:26 pm

I just converted all numbers to integers, and used integer calculations.
Ami ekhono shopno dekhi...
HomePage

ghooo
New poster
Posts: 3
Joined: Tue Sep 01, 2009 2:13 pm

Re: 10301 - Rings and Glue

Post by ghooo » Tue Sep 01, 2009 2:16 pm

I got AC after considering these cases
the output should be:

....1 ring.
....0 rings.
....x rings.

Post Reply

Return to “Volume 103 (10300-10399)”