Page 1 of 1
Posted: Sun Oct 16, 2005 7:53 pm
by Cho
My WA-code (unfortunately I cannot get my bug yet) is also O(n*l). It can finish in around 7 seconds. But I remember the time limit in the online contest is 6 seconds. I also want to ask how fast the author's solution could run.
Posted: Sun Oct 16, 2005 8:05 pm
by Per
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.]
Posted: Sun Oct 16, 2005 8:34 pm
by Per
Doh. Sorry.
Posted: Mon Oct 17, 2005 3:20 am
by Cho
tomek wrote: ... By the way, thanks for your tests, Cho ...
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.
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 brute-force simulation code.
Posted: Mon Oct 17, 2005 10:20 am
by little joey
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?
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
Thanks in advance.
Posted: Mon Oct 17, 2005 11:04 am
by Cho
No. The one I posted was incorrect.
I've just updated it with correct output:
10939.zip
And the output of your test case is correct.
Posted: Mon Oct 17, 2005 11:25 am
by little joey
Thanks a lot. Now both our outputs are the same, so at least my program is correct.
Just have to speed it up a little ... sigh.
[Later on]
Got it.
Posted: Tue Oct 25, 2005 1:22 pm
by polone
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.
Posted: Tue Oct 25, 2005 5:52 pm
by Cho
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.
Posted: Tue Oct 25, 2005 6:14 pm
by Per
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.
I disagree.
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 straight-forward implementation of the intended algorithm, you should get TLE, because then you haven't coded it properly.
Note however, that I refer to a "straight-forward implementation of the intended algorithm", which is what the judge solution should be, not a super-optimized implementation of the intended algorithm. It is usually good to set the time limit to something like a factor 3 times the judge solution.
Posted: Wed Oct 26, 2005 3:26 pm
by polone
yes I got ac
I used two DFS per ladybug's landing
It's quick enough
Posted: Mon Jan 09, 2006 11:25 pm
by Khaled_912
I'm using BFS, but I'm mad about my TLE !!
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<n-1;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(x-1,y-1);
if (first==second) cout<<"The fleas meet at "<<first+1<<"."<<endl;
else cout<<"The fleas jump forever between "<<first+1<<" and "<<second+1<<"."<<endl;
}
}
}
Posted: Fri Jun 23, 2006 6:50 pm
by shanto86
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?
Posted: Sun Jun 25, 2006 4:59 pm
by shanto86
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
