10939  Ants, Aphids and a Ladybug
Moderator: Board moderators
I did an O(n*l) solution (DFS, and I stop searching as soon as I reach the target). It takes roughly 1.1 secs.
[edit: no I didn't. But for 10938 I did.]
[edit: no I didn't. But for 10938 I did.]
Last edited by Per on Sun Oct 16, 2005 8:35 pm, edited 1 time in total.
Oops... the others may not understand what you are talking about. I once posted some test cases to ask for verification, but I got my mistake before anyone reply. So that post was removed already.tomek wrote: ... By the way, thanks for your tests, Cho ...
One hint for those who got WA. It's not hard at all to generate yourself some small random test cases. Then you can compare your output to the output of a bruteforce simulation code.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hi Cho,
Was the I/O you published yesterday correct? My program is still too slow, but my output has many differences with your output, so I might have a wrong interpretation of the problem.
Is this I/O correct?
Thanks in advance.
Was the I/O you published yesterday correct? My program is still too slow, but my output has many differences with your output, so I might have a wrong interpretation of the problem.
Is this I/O correct?
Code: Select all
20
1 2
2 3
3 4
4 5
2 6
6 7
7 8
6 9
9 10
9 11
2 12
12 13
13 14
14 15
6 16
16 17
17 18
9 19
19 20
7
11
5
15
8
18
10
20
1
1
0
Code: Select all
1 1
3 0
12 0
7 0
16 0
10 0
19 0

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
How can I determine each ant's location after every ladybug's landing in a short time?
I did it step by step (every ant's move the 1'st step...then 2'nd step...so)
before every ant move one step I do a DFS to determine which could move and which not.
but that's too slow.. I coule remove the DFS and got WA in runtime.
I did it step by step (every ant's move the 1'st step...then 2'nd step...so)
before every ant move one step I do a DFS to determine which could move and which not.
but that's too slow.. I coule remove the DFS and got WA in runtime.
I need to apply DFS twice for each ladybug's landing.
There may be some simpler way to get the solution as my solution is pretty slow. (So slow that it cannot pass the time limit of the online contest.)
But in my opinion, for programming contest, if someone gets an algorithm which has the same time complexity as the judge's solution. He should pass the time limit no matter how slow (say, 10 times slower) his implementation is.
There may be some simpler way to get the solution as my solution is pretty slow. (So slow that it cannot pass the time limit of the online contest.)
But in my opinion, for programming contest, if someone gets an algorithm which has the same time complexity as the judge's solution. He should pass the time limit no matter how slow (say, 10 times slower) his implementation is.
I disagree.Cho wrote:But in my opinion, for programming contest, if someone gets an algorithm which has the same time complexity as the judge's solution. He should pass the time limit no matter how slow (say, 10 times slower) his implementation is.
First, what you suggest cannot be implemented, since there simply is no way to distinguish between good time complexity and bad constants versus bad time complexity and good constants.
Second, a programming contest is not just about finding good algorithms, it is also about being able to program them in a reasonably efficient way. If your solution is 10 times slower than a straightforward implementation of the intended algorithm, you should get TLE, because then you haven't coded it properly.
Note however, that I refer to a "straightforward implementation of the intended algorithm", which is what the judge solution should be, not a superoptimized implementation of the intended algorithm. It is usually good to set the time limit to something like a factor 3 times the judge solution.

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm
I'm using BFS, but I'm mad about my TLE !!
Here's my code, please tell my if I can optimize any part.
Here's my code, please tell my if I can optimize any part.
Code: Select all
#include <iostream>
#include <fstream>
#include <queue>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
bool a[5005][5005];
int v[5005];
int p[5005];
int d[5005];
int first,second;
int n;
void bfs(int x,int y)
{
int i;
for (i=0;i<n;i++) v[i]=0;
queue <int> q1,q2;
q1.push(x); q2.push(y);
d[x]=0; d[y]=0; bool f1=true, f2=true;
while(!q1.empty()!q2.empty())
{
if (!q1.empty()) {x=q1.front(); q1.pop();}
else f1=false;
if (!q2.empty()) {y=q2.front(); q2.pop();}
else f2=false;
if (x==y) {first=y; second=y; return;}
if (v[y]==1) {first=y; second=p[y]; return;}
if (v[x]==2) {first=x; second=p[x]; return;}
if (v[x]==0&&f1)
{
v[x]=1; d[x]=d[p[x]]+1;
for (i=0;i<n;i++)
if (a[x][i]) {q1.push(i); p[i]=x;}
}
if (v[y]==0&&f2)
{
v[y]=2; d[y]=d[p[y]]+1;
for (i=0;i<n;i++)
if (a[y][i]) {q2.push(i); p[i]=y;}
}
}
}
void init()
{for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j]=false;}
void main()
{
while(cin>>n&&n>0)
{
init();
int x,y;
for (int i=0;i<n1;i++)
{
cin>>x>>y; x; y;
a[x][y]=a[y][x]=true;
}
int m; cin>>m;
while(m)
{
int x,y; cin>>x>>y;
bfs(x1,y1);
if (first==second) cout<<"The fleas meet at "<<first+1<<"."<<endl;
else cout<<"The fleas jump forever between "<<first+1<<" and "<<second+1<<"."<<endl;
}
}
}
well... you people are talking about 2 DFS. i can figure out one that is from the landing place to mark out the path that should be followed by the ants. but what is the work of other?
i have not yet coded, but what i though about is, 1 DFS (the above one) and the simulator which will move the ants by 1move then 2moves then 3 and so on until an ant reach ladybug.
am i right?
i have not yet coded, but what i though about is, 1 DFS (the above one) and the simulator which will move the ants by 1move then 2moves then 3 and so on until an ant reach ladybug.
am i right?
Self judging is the best judging!
why am i getting WA? i have tried all Cho's case and it gave same result. not only that, i used 2DFS. but my code ran for 9.958S it is too much serprizing for me that only 2DFS per ladybug got so much time. i can't figure out what's the mistake! can any one please help me?
*Does pointer link list take much time than vector?
silly mistake! i was initialising an array till 5000 while it was declraed till 1000 only
*Does pointer link list take much time than vector?
Code: Select all
AC
Self judging is the best judging!