10939 - Ants, Aphids and a Ladybug

[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.

[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.]

[Per]

Doh. Sorry.

[Cho]

... 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.

[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 

Code: Select all

1 1
3 0
12 0
7 0
16 0
10 0
19 0

Thanks in advance.

[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.

[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.

[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.

[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.

[Per]

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]

yes I got ac

I used two DFS per ladybug's landing

It's quick enough

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

[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?

[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?

Code: Select all

AC

silly mistake! i was initialising an array till 5000 while it was declraed till 1000 only