10939 - Ants, Aphids and a Ladybug

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

Moderator: Board moderators

Post Reply
User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Oct 16, 2005 7:53 pm

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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Oct 16, 2005 8:05 pm

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.]
Last edited by Per on Sun Oct 16, 2005 8:35 pm, edited 1 time in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Oct 16, 2005 8:34 pm

Doh. Sorry.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon Oct 17, 2005 3:20 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Oct 17, 2005 10:20 am

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 

Code: Select all

1 1
3 0
12 0
7 0
16 0
10 0
19 0
Thanks in advance.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon Oct 17, 2005 11:04 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Oct 17, 2005 11:25 am

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.

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Tue Oct 25, 2005 1:22 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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Tue Oct 25, 2005 5:52 pm

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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Oct 25, 2005 6:14 pm

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.

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Wed Oct 26, 2005 3:26 pm

yes I got ac :D

I used two DFS per ladybug's landing

It's quick enough

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post by Khaled_912 » Mon Jan 09, 2006 11:25 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.

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;
		}
		
		
	}
	
	
}

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Fri Jun 23, 2006 6:50 pm

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?
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Jun 25, 2006 4:59 pm

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?

Code: Select all

AC
silly mistake! i was initialising an array till 5000 while it was declraed till 1000 only :(
Self judging is the best judging!

Post Reply

Return to “Volume 109 (10900-10999)”