10600 - ACM Contest and Blackout

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

Moderator: Board moderators

SupeRaskao
New poster
Posts: 2
Joined: Wed Feb 18, 2004 5:50 am

10600 - ACM Contest and Blackout

Post by SupeRaskao » Wed Feb 18, 2004 5:56 am

Im getting WA on this one. here is a description of my algorithm:

I use kruskal to calculate the MST. then for each edge in the solution recalculate MST without that edge. so the first solution is the one given by kruskal and the second on is the min among the other solutions.

Is this ok?

sorry about my english....

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Right

Post by sohel » Wed Feb 18, 2004 11:24 am

Hi SupeRaskao,

Your method looks similar to mine.
The key part was to remove edges only from the MST and not the other edges. From your post it looks like you have considered that too.

Maybe you made a minor mistake in your coding.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Feb 23, 2004 12:00 pm


check out
coremen(CLRS) for
"second best minimum tree"
in the chapter
"minimum spanning tree."
hope it will help you.
--
Anupam
"Everything should be made simple, but not always simpler"

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sat May 15, 2004 8:24 pm

Hello!
I think i solve this problem,my program works right for symple inputs ,but gets WA.Can somebody give me any input and output.
Thanks before.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Mon May 17, 2004 10:15 pm

I passed the example test data, but also got WA first time.
Turned out there is a problem when the graph is not connected (it happens when trying to find the second minimum value).
I fixed that and now it is AC. Try this:

Input:

Code: Select all

1
4 4
1 4 5
1 2 2
2 3 3
1 3 4
Output:

Code: Select all

10 11

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue May 18, 2004 5:07 pm

I hade already find the problem with graph not connectivity,but your test help me to find that my program is getting not WA but RE(for Pascal Online Judge is giving WA instade of RUN-TIME ERROR).I fix and got AC.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

10600

Post by mlvahe » Tue Aug 24, 2004 5:06 pm

I can't understand why do I keep getting WA's on 10600, while it look's an easy problem with Kruskal algorithm.
[cpp]
AC
[/cpp]
Last edited by mlvahe on Thu Aug 26, 2004 4:36 pm, edited 1 time in total.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue Aug 24, 2004 5:50 pm

Hello Vahe.
Did you watch case when graph is not connected.
What is your answer for this test case.
Input

Code: Select all

1 
4 4 
1 4 5 
1 2 2 
2 3 3 
1 3 4 
Output

Code: Select all

10 11
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

Post by mlvahe » Tue Aug 24, 2004 6:34 pm

Hi Eduard.
Yes, I have considered that case.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Wed Aug 25, 2004 10:02 am

A really small mistake. It also took a while before I saw it. Look at this lines:
[cpp]for (i = 0; i < n; i++)
used = 0;[/cpp]
(should be i<m of course)

User avatar
mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

Post by mlvahe » Thu Aug 26, 2004 4:38 pm

Hi krijger.

Thank you very very much.
I got AC.

zzzzzddddd
New poster
Posts: 6
Joined: Tue Sep 21, 2004 5:53 pm

10600, i have got wa for n times!

Post by zzzzzddddd » Tue Sep 21, 2004 5:57 pm

can anyone tell me what's wrong?
[cpp]#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Tedge{
int u,v;
}e[20010],mt[110];
int n,m,tot,ans1,ans2,totcase;
int g[110][110],opt[110][110];
bool mark[110][110];

int cmp(const void *a,const void *b){
Tedge *e1=(Tedge*)a,*e2=(Tedge*)b;
return e1->u-e2->u;
}

inline int max(int a,int b){
return a>b?a:b;
}

inline int min(int a,int b){
return a<b?a:b;
}

void bfs(int v)
{
int i,cl,op,low,now;
int que[110];
bool use[110];

memset(use,false,sizeof(use));
que[0]=v,use[v]=true;
cl=0,op=1;
while (cl<op){
now=que[cl];
for (low=0;low<tot;low++)
if (mt[low].u==now) break;
for (i=low;mt.u==now;i++)
if (!use[mt.v]){
que[op++]=mt.v;
use[mt.v]=true;
opt[v][mt.v]=max(opt[v][now],g[now][mt.v]);
}
cl++;
}
}

void solve()
{
int i,j,minv,u,v;
int dis[110],pre[110];
bool vis[110];

for (i=2;i<=n;i++) pre=1,dis=g[1],vis=false;
dis[1]=0,vis[1]=true;
for (i=2;i<=n;i++){
minv=-1;
for (j=1;j<=n;j++)
if (!vis[j]&&dis[j]>0)
if (minv==-1||dis[j]<dis[minv]) minv=j;
mt[tot].u=pre[minv],mt[tot].v=minv; tot++;
mt[tot].u=minv,mt[tot].v=pre[minv]; tot++;
mark[pre[minv]][minv]=mark[minv][pre[minv]]=true;
ans1+=dis[minv];
vis[minv]=true;
for (j=1;j<=n;j++)
if (g[minv][j]>0&&(!vis[j])&&(dis[j]==0||dis[j]>g[minv][j]))
pre[j]=minv,dis[j]=g[minv][j];
}

ans2=1000000000;
qsort(mt,tot,sizeof(Tedge),cmp);
for (i=1;i<=n;i++) bfs(i);
for (i=0;i<m;i++){
u=e[i].u,v=e[i].v;
if (!mark[v]) ans2=min(ans2,ans1+g[v]-opt[v]);
}
}

int main()
{
int i,u,v,cost;

scanf("%d",&totcase);
while (totcase--){
memset(g,0,sizeof(g));
memset(opt,0,sizeof(opt));
memset(mark,false,sizeof(mark));

scanf("%d%d",&n,&m);
for (i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&cost);
e[i].u=u,e[i].v=v;
g[v]=g[v]=cost;
}
tot=ans1=ans2=0;
solve();
printf("%d %d\n",ans1,ans2);
}
return 0;
}
[/cpp]

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

10600 ACM contest and Blackout

Post by 898989 » Wed Mar 01, 2006 1:55 am

Salamo Aleko.
I have some thing strange about this problem
I solve it using prime algorithm and got ac in 0.086s..... :D
And now after coding it with kruskal algorithm using "Union with path compression path" I get wrong answer. I can not find any logical reason
for this.....Can any one help me :roll: .......Thanks in advace. :wink:

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

kruskal..

Post by sohel » Wed Mar 01, 2006 4:36 pm

I solved this problem using kruskal.

So, there must be some minor mistake in your kruskal implementation.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Sun Mar 05, 2006 1:04 am

Salamo Aleko
Finally I detect this minor Mistake and get accepted in 0.184
Is this good time or .... :roll:
Thanx...... :o
http://acm.uva.es/problemset/usersjudge.php?user=8957CA

Post Reply

Return to “Volume 106 (10600-10699)”