10199 - Tourist Guide

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

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sat Mar 20, 2004 9:25 am

I also got WA. My program passed all previous sample in/out s in this thread. Please help me to identify my problem. here is the code:
[c]#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define min(a, b) (a < b) ? a : b
#define MAXV 105
#define MAXE 5100

int adj[MAXV][MAXV], dfn[MAXV], L[MAXV], num, n;
int edges[MAXE][2], e;

char ara[MAXV][35];

int get_indx(char s[])
{
for(int i=1; i<=n; i++)
if(!strcmp(ara, s))
return i;
return 0;
}

void art(int u, int v)
{
int w;
dfn = num;
L = num;
num++;

for(w=1; w<=n; w++)
{
if(adj[w])
{
if(!dfn[w])
{
edges[e][0] = u;
edges[e++][1] = w;
art(w, u);
L = min(L, L[w]);
}
else if(w!=v)
L = min(L, dfn[w]);
}
}
}

int comp(const void *a, const void *b)
{
char *x = (char *)a;
char *y = (char *)b;
return strcmp(x, y);
}

void main()
{
char a[35], b[35], ans[MAXV][35];
int points[MAXV];
int i, j, count, u, v, root, r_count, map=0, m;

while(1==scanf("%d", &n) && n)
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++) adj[j] = 0;
dfn = 0;
}
for(i=1; i<=n; i++) scanf("%s", ara);
scanf("%d", &m);
while(m--)
{
scanf("%s%s", a, b);
i = get_indx(a);
j = get_indx(b);
adj[j] = adj[j] = 1;
}
e = 0;
num = 1;
art(1, 0);

for(i=1; i<=n; i++) points = 0;
root = 1;
r_count = 0;
count = 0;
for(i=0; i<e; i++)
{
u = edges[0];
if(u==root)
{
r_count++;
continue;
}
if(points) continue;
v = edges[1];
if( L[v] >= dfn)
{
count++;
points = 1;
}
}
if(r_count > 1)
{
count++;
points[root] = 1;
}
if(map) printf("\n");
printf("City map #%d: %d camera(s) found\n", ++map, count);

for(i=1, j=0; i<=n; i++)
if(points)
strcpy(ans[j++], ara[i]);
qsort((void *)ans, j, sizeof(ans[0]), comp);
for(i=0; i<count; i++) printf("%s\n", ans[i]);
}
}[/c]
( I have got 315 AC with almost same code )

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

Post by Jan » Sun Jul 17, 2005 8:37 pm

Can anyone tell me what is the output of the following input set...

Input:

Code: Select all

5
a
b
c
d
e
4
a b
b c
a d
d c
0
Thanks...
Ami ekhono shopno dekhi...
HomePage

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Mon Dec 26, 2005 12:30 am

output:

Code: Select all

City map #1: 0 camera(s) found
Nothing helpful. So I guess the error lies in your algorithm.

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm

Post by indyman » Thu Nov 30, 2006 12:42 pm

Can anybody help me out? I am getting WA even though I get correct answers for all examples posted on this topic. What is the program really supposed to do for disconnected graphs? Many people have asked this before on this topic, but it hasnt really been answered yet. I am just wondering if thats where I am doing something wrong.

If I am not doing anything wrong with disconnected graphs, are there any other gotchas besides the alphabetical order?

Also, I am having a trailing extra endl at the end since I use it to insert space between cases. Is that right? I tried both ways - with the extra endl and without - I got WA both times. I am bummed!

Here are the inputs & outputs (all compiled from prior posts under this topic) my code gives me:

Code: Select all

Input:
6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
6
a
b
d
c
e
f
7
a b
a d
d c
b d
c e
c f
e f
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f g
7
g
f
e
d
c
b
a
7
a b
b c
c d
d e
e f
f g
g a
7
g
f
e
d
c
b
a
5
b c
c d
d e
e f
f g
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
5
a
b
c
d
e
4
a b
b c
a d
d c 
0 

Code: Select all

Output:
City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

City map #3: 2 camera(s) found
c
d

City map #4: 5 camera(s) found
b
c
d
e
f

City map #5: 0 camera(s) found

City map #6: 1 camera(s) found
f

City map #7: 2 camera(s) found
a
c

City map #8: 0 camera(s) found

:oops: :oops:

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

Post by Jan » Thu Nov 30, 2006 12:50 pm

My accepted code returns...

Output:

Code: Select all

City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

City map #3: 2 camera(s) found
c
d

City map #4: 5 camera(s) found
b
c
d
e
f

City map #5: 0 camera(s) found

City map #6: 4 camera(s) found
c
d
e
f

City map #7: 1 camera(s) found
a

City map #8: 0 camera(s) found
Dont worry about presentation. If your output format is not correct you will get accepted(presentation error).
And if the graph is disconnected just print the articulations from each connected subgrapth.
Hope these help.
Ami ekhono shopno dekhi...
HomePage

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm

Post by indyman » Thu Nov 30, 2006 10:43 pm

Jan,

Thanks for the output from your accepted code. I fxed my code and am getting the same answers for this input as you posted. Still WA. Any ideas as to which test cases might help? I am bummed.

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

Post by Jan » Fri Dec 01, 2006 1:06 am

Try the cases...

Input:

Code: Select all

6
a
b
c
d
e
f
3
a f
b c
e d
6
a
b
c
d
e
f
6
a f
b c
e d
f e
a d
b d
6
x
y
z
a
b
c
0
6
x
y
z
a
b
c
7
x y
y z
z x
a b
b c
a c
a z
0
Output:

Code: Select all

City map #1: 0 camera(s) found

City map #2: 2 camera(s) found
b
d

City map #3: 0 camera(s) found

City map #4: 2 camera(s) found
a
z
Hope these help. If your code passes, post your code.
Ami ekhono shopno dekhi...
HomePage

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm

Post by indyman » Fri Dec 01, 2006 1:45 am

Hi Jan,

My code passed the above test cases you posted:
This is the output:

Code: Select all

City map #1: 0 camera(s) found

City map #2: 2 camera(s) found
b
d

City map #3: 0 camera(s) found

City map #4: 2 camera(s) found
a
z

This is my code... Hope you can help..

Code: Select all

Code Removed
Hope you can help.... Thanks...
Last edited by indyman on Fri Dec 01, 2006 10:32 am, edited 1 time in total.

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm

Post by indyman » Fri Dec 01, 2006 2:01 am

Jan,

I think the following test case also might help me figure out whats wrong:

Input:

Code: Select all

6
a
b
c
d
e
f
4
a b
a f
c d
d e
0
The output I get, is:

Code: Select all

City map #1: 1 camera(s) found
a

Although, if you make the graph, its like this:

Code: Select all

b ------ a ------- f

c ------ d ------- e
where there are two disjoint parts of the graph. Shouldnt the answer be

Code: Select all

City map #1: 2 camera(s) found
a
d
What does your code give?

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

Post by Jan » Fri Dec 01, 2006 2:04 am

My code returns

Code: Select all

City map #1: 2 camera(s) found
a
d
which is correct.
Ami ekhono shopno dekhi...
HomePage

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm

Post by indyman » Fri Dec 01, 2006 2:10 am

Just as I thought. Thanks man. If you get any insights from my code, please let me know. I am thinking theres something wrong with the way I compute my low[] in the function low2[].

Thanks.

indyman
New poster
Posts: 7
Joined: Thu Nov 30, 2006 12:36 pm

Post by indyman » Fri Dec 01, 2006 10:37 am

Jan,

Thank you very much for the test cases and advice. I figured out the error in my code. In my implementation of articulation points, I was calculating low using regular edges instead of the edges from the DFS tree. Doh! :))

Thanks a lot once again!

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Mar 01, 2007 5:35 am

I have no idea for which input my code fails..
I am getting WAs

Code: Select all

Removed after got Accepted

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Mar 01, 2007 7:44 am

I hv found my mistake..
Thanks to Sunny.

raymond-luxury-yacht
New poster
Posts: 1
Joined: Fri Mar 02, 2007 10:26 pm

Post by raymond-luxury-yacht » Fri Mar 02, 2007 10:42 pm

Is there any problem with finding articulation points just by removing the point from the graph and counting if the number of graph components increased? My program works fine for all the input mentioned in this topic, but still got WA :-?

Post Reply

Return to “Volume 101 (10100-10199)”