## 10938 - Flea circus

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

sunmoonstar_love
New poster
Posts: 13
Joined: Wed Aug 24, 2005 8:16 pm

### .....

O(n) for each query is too slow.

Just set a note as a root, use dfs or bfs construct a rooted tree

and for each query, find the nearest common ...... of two node.

then odd or even ........

I'm from China

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

### Re: .....

sunmoonstar_love wrote:O(n) for each query is too slow.
I got AC in 1.258 sec using adjacency lists and O(n) search for each query, but your approach should be faster, of course.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
During the contest I used straight forward BFS to find the path between two nodes and got TLE. Now I use kind of a 2-way BFS and got accepted in less than 4 sec.

But I would really like to know about the solutions that took less than 1 sec. Can anyone give some hints??
Where's the "Any" key?

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

### Why RE!

My approach to this problem is to build the tree while reading the input, for each case. It might not the best one, but I am triyng to make it work. It has given me repeatedly RuntimeError, and I don't know why it cracks.
This is my code for reading the input and bulding the tree, if anybody finds the bug please notice. It should be in the while (a!=0) statement...

Code: Select all

``````  for (i = 1; i <= vertices; i++) {intree[i] = 0; p[i] = 0;}
scanf ("%u %u", &a, &b);
p[b] = a;
intree[a] = intree[b] = 1;
edges = vertices - 2;/*I've already read an edge*/
while (edges--) {
scanf ("%u %u", &a, &b);
if (intree[b] == 0) p[b] = a;
else if (intree[a] == 0) p[a] = b;
else {
/*an edge connecting
two unconnected components of the tree*/
size = 0;
while (a != 0){
queue[size++] = a;
a = p[a];
}
for (i = size - 1; i > 0; i--)
p[queue[i]] = queue[i-1];
a = queue[0];
p[a] = b;
}
intree[a] = intree[b] = 1;
}``````
"From lost to the river" --> Spanish quote

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
But I would really like to know about the solutions that took less than 1 sec. Can anyone give some hints??
You may find some ideas of this paper useful: M. A. Bender, M. Farach-Colton, "The LCA Problem Revisited," sections 2 and 3.
My solution achieves O(log n) time per query by precomputing for each vertex of the (rooted) tree its 1st, 2nd, 4th, 8th, ... parents.
luishhh wrote:edges = vertices - 2;/*I've already read an edge*/
while (edges--) {
Think, what happens to this loop when vertices==1.

elmohandis
New poster
Posts: 1
Joined: Sun Oct 16, 2005 1:40 pm

### whats wrong with this solution ? TLE

sorry for duplicating this post from another thread, but this one seems to be alive

My approach is to make DFS once and fill the s array with the previous of every vertex.
Then for every case construct the path for the deeper and shallower vertex, then find the least common ancestor (the only way i know how). Now Calculate the number of steps between the two vertices , then check odd/even , then move back steps/2 from deeper vertex.

It is giving TLE but i cant find out why ?!

Any help would be highly appreciated .

Here is the code :

Code: Select all

``````#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <cmath>
#include <list>
#include <algorithm>
#include <functional>

using namespace std;

#ifdef ONLINE_JUDGE
istream *fin = &cin;
#else
ifstream *fin = new ifstream("E.txt");
#endif

#define INFIN 9999
enum {UNVISITED,VISITED};

class Graph {

public:

int ncount;
list<short> *matrix;
bool *marks;

Graph(int n)
{
marks = new bool[n+1];
matrix = new list<short>[n+1];
ncount=n;

for (int i=0;i<n;i++)
{
marks[i]=0;
}
}
~Graph()
{
delete []matrix;
delete marks;

}

int n() { return ncount;}

int first (int myv)
{
int ans=INFIN;
if (matrix[myv].size()>0) return *matrix[myv].begin();
return ans;
}

int next (int myv, int oldneigh)
{
int ans=INFIN;
list<short>::iterator itr;
itr = find(matrix[myv].begin(),matrix[myv].end(),oldneigh);
itr++;
if(itr != matrix[myv].end() ) ans = *(itr);
return ans;
}

void setedge( int v1,int v2)
{
matrix[v1].push_back(v2);
matrix[v2].push_back(v1);
}

void deledge( int v1,int v2)
{
list<short>::iterator itr;

itr = find(matrix[v1].begin(),matrix[v1].end(),v2);
if (itr!=matrix[v1].end()) matrix[v1].erase(itr);

itr = find(matrix[v2].begin(),matrix[v2].end(),v1);
if (itr!=matrix[v2].end()) matrix[v2].erase(itr);
}

int getmark(int v) { return marks[v];}

void setmark (int v, bool mark) { marks[v] = mark; }
};

void DFS(Graph* G, int v, short int*s) {
//  PreVisit(G, v);
G->setmark(v, VISITED);
for (int w=G->first(v); w<G->n(); w = G->next(v,w))
if (G->getmark(w) == UNVISITED)
{
s[w] = v;
DFS(G, w,s);
}
//  PostVisit(G, v);
}

int main()
{
short int s[5001];
s[0]=0;

while (1)
{
int n=0,l=0;
(*fin)>>n;
if (n==0) break;

int i,z;
int v1,v2;
int p1,p2;
Graph *G = new Graph(n);

if (n!=1)
{
for (i=0;i<n-1;i++)
{
(*fin)>>v1>>v2;
G->setedge(v1-1,v2-1);
}
G->ncount = n;

DFS(G,0,s);
}

(*fin)>>l;

for (i=0;i<l;i++)
{

(*fin)>>p1>>p2;
p1--; p2--;

if (n==1)
{
cout<<"The fleas meet at "<<p1+1<<"."<<endl;
continue;
}

//process the two positions :

vector<short>::iterator vi;
int steps=0;

int deeppt = p1 , shallowpt=p2;

vector<short> *shallowpath, *deeppath, ncapath;
shallowpath = new vector<short>;
deeppath = new vector<short>;

int current;
current =shallowpt;
while(current!=0)
{
shallowpath->insert(shallowpath->begin(),current);
current=s[current];
}
shallowpath->insert(shallowpath->begin(),0);

current=deeppt;
while(current!=0)
{
deeppath->insert(deeppath->begin(),current);
current=s[current];
}
deeppath->insert(deeppath->begin(),0);

if(shallowpath->size() > deeppath->size())
{
int t;
vector<short> *vt;
vt = shallowpath;
t = p2;

p2 = p1;
shallowpath = deeppath;

p1=t;
deeppath = vt;

}

for( z=shallowpath->size()-1; z>=0; z--)
{
vi = find(deeppath->begin(),deeppath->end(), (*shallowpath)[z]);
if (vi!=deeppath->end()) { break;}
}

current=*vi;
while(current!=0)
{
ncapath.insert(ncapath.begin(),current);
current=s[current];
}
ncapath.insert(ncapath.begin(),0);

steps = deeppath->size() + shallowpath->size() -2*ncapath.size() ;

if (steps %2 == 0) //meet
{
int indexans = deeppath->size() -1 - steps/2;
int meetpt = (*deeppath)[indexans];
cout<<"The fleas meet at "<<meetpt+1<<"."<<endl;
}

else		//dont meet
{
int indexans = deeppath->size() -1 - steps/2;
int meetpt = (*deeppath)[indexans];
int meetpt2 = (*deeppath)[indexans-1];

int minpt,maxpt;
if (meetpt<meetpt2) {minpt=meetpt+1; maxpt=meetpt2+1;}
else {maxpt=meetpt+1; minpt=meetpt2+1;}

cout<<"The fleas jump forever between "<<minpt
<<" and "<<
maxpt
<<"."<<endl;
}

delete shallowpath,deeppath;

} //done processing cases

delete G;
}

return 0;

}
``````

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain
Thank you very much!!!!
I thought the bug was in the loop... but again it was a silly case
AC in 2 tenths, my algorithm was better than I expected
"From lost to the river" --> Spanish quote

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
My solution achieves O(log n) time per query
thnx mf .. now I have one of the better timings.
Where's the "Any" key?

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

### Re: 10938 - Flea circus

My Solution get WA, can anybody give test case?? Here is my solution, i find LCA with reduce it to RMQ problem

Get AC without edit, I wonder why ? I think when I post my code here it gets WA in OJ but now get AC

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

### Re: 10938 - Flea circus

I hope the case below will help you if you get wa:

Code: Select all

``````20
1 2
3 1
3 12
13 12
3 11
11 14
2 8
2 9
9 10
4 3
4 16
4 17
17 18
19 18
19 20
3 5
5 6
7 5
5 15

15
9 15
12 13
14 11
1 3
10 1
20 6
7 5
5 11
5 14
8 12
10 15
10 3
4 3
17 3
18 1
``````

Code: Select all

``````The fleas jump forever between 1 and 3.
The fleas jump forever between 12 and 13.
The fleas jump forever between 11 and 14.
The fleas jump forever between 1 and 3.
The fleas jump forever between 2 and 9.
The fleas jump forever between 4 and 17.
The fleas jump forever between 5 and 7.
The fleas meet at 3.
The fleas jump forever between 3 and 11.
The fleas meet at 1.
The fleas meet at 1.
The fleas meet at 2.
The fleas jump forever between 3 and 4.
The fleas meet at 4.
The fleas meet at 4.
``````
I got lots of wa in this problem before getting ac. i had bug in edge direction,than i made the graph bidirectional and got ac. I've used tarjan's offline algorithm to find lca of every pair of query and used a sparse table to climb to meeting point quickly.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 10938 - Flea circus

LCA for this problem?! I just used normal bfs to solve that and nothing else is needed. Just use one flea's location as source and another flea's location as destination. Then find the path between them. If path length+1 odd then they will jump between two node forever otherwise they will meet.Now,Just think a bit to find the final nodes..

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 10938 - Flea circus

I am getting wa. My idea is finding LCA for (p,q) where level[p]>level[q].k is the distance between query nodes ( k = level[p] - level[LCA]+ level[q] - level[LCA]). if k is even then they meet at k/2 th ancestor of p otherwise they keep jumping forever between k/2 th and (k/2)+1 th ancestor of p.

Code: Select all

``````AC
``````
Such a silly mistake.Instead of writing (1<<j) i wrote (j<<1) . Thanks brianfry713
Last edited by Farsan on Tue May 13, 2014 5:53 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10938 - Flea circus

Input:

Code: Select all

``````81
75 67
67 9
75 56
9 38
56 51
75 69
9 81
67 78
9 50
9 31
9 29
51 62
78 21
51 22
56 61
81 49
61 28
50 63
56 70
75 64
49 4
22 59
4 35
22 7
56 42
78 14
38 48
51 66
64 41
75 65
21 74
67 10
63 27
66 39
62 25
38 20
35 40
51 26
40 55
70 68
69 23
41 2
74 76
42 3
14 44
66 45
51 12
38 11
70 33
61 72
28 80
38 77
78 19
76 15
67 43
20 54
75 58
43 32
65 47
66 30
40 34
80 16
69 36
3 57
33 18
9 73
25 52
56 1
21 60
11 5
52 8
56 71
8 13
42 24
56 37
60 17
14 79
17 46
10 53
55 6
1
77 52
0
``````
AC output:

Code: Select all

``````The fleas jump forever between 56 and 75.
``````
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 10938 - Flea circus

Why WA ?
Printing blank line ??
I used LCA
Give me some critical test Cases

Code: Select all

``````//
//  main.cpp
//  10938 - Flea circus
//
//  Created by Repon Macbook on 11/1/14.
//

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
using namespace std;

/*------- Constants---- */
#define MX 5005
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb push_back
#define gc getchar_unlocked

/* -------Global Variables ------ */
ll euclid_x,euclid_y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;

/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline T extended_euclid_returning_gcd(T a,T b){ if(b==0){d = a;euclid_x=1;euclid_y=0;} else {extended_euclid_returning_gcd(b, a%b);
T x1 = euclid_y; T y1 = euclid_x - (a / b) * euclid_y ; euclid_x = x1 ; euclid_y = y1 ;}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}

int vertex ;
int lev[MX];
int T[MX];
int touch[MX];
int P[MX][22];

void bfs( int s)
{
lev[s] = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int i = 0; i < adjList[u].size(); i ++) {
int v = adjList[u][i];
if( lev[v] ==-1 ){
T[v] = u;

lev[v] = 1 + lev[u];
Q.push(v);
}
}

}

return;

}
void dfs ( int from , int u , int dep )
{

if( touch[u] ) return;

lev[u] = dep;
T[u] = from;
touch[u] = 1;

for (int i = 0; i < adjList[u].size(); i ++ ) {
int v = adjList[u][i];

dfs(u , v , dep + 1);
}

}

void LCA ( int N )
{

ms(P , -1);

int  i , j ;
for ( int  i = 1; i <= N ; i ++ ) {
P[i][0] = T[i];
}

for ( j = 1; (1 << j) < N  ; j ++ ) {
for ( i = 1; i <= N ; i ++ ) {
if( P[i][j - 1] != -1){
P[i][j]  = P[P[i][j-1]][j-1];
}
}
}

}

int counter= 0;

int LCA_QUERY ( int N , int p , int q)
{

int i , log;
if( lev[p ] < lev[q]) swap(p , q);

log = 1;
while (1) {
int next = log + 1;
if( (1 << next ) > lev[p]) break;
log ++;
}

for ( i  = log ; i >= 0 ; i -- ) {
if( lev [p] - (1 << i) >= lev[q] ){
p = P[p][i];
counter += (1<<i);
}
}

if( p == q) return p;

for ( i = log ; i >=0 ; i --) {
if( P[p][i] !=-1 && P[p][i] != P[q][i]){
p  = P[p][i];
q = P[q][i];
counter += (1<<(i +1));
}

}
counter += 2;
return T[p];

}

int ParentFinder ( int p , int s)
{

int log ;
log = 1;

while (1) {
int next = log + 1;
if( (1 << next ) > lev[p]) break;
log ++;
}

for ( int i = log ; i >=0 ; i -- ) {

if( s >=  (1<< i) ){
p = P[p][i];
s = s -(1 << log);
}

}

return p;

}
int main()
{

int a , b , query , one, two ;

while (cin >> vertex && vertex)  {

FOR(i , vertex - 1){
cin >> a >> b;
}
ms(lev, -1);
ms(P , -1);
bfs(1);
LCA(vertex);

cin >> query ;

while (query -- ) {

cin >> one >> two;
if( lev[one ] < lev[two]) swap(one, two);

int qq = LCA_QUERY(vertex, one, two);

counter = lev[one] + lev [two] - 2 * lev[qq];
if( counter & 1){
int v = ParentFinder (one ,  counter / 2);
printf("The fleas jump forever between %d and %d.\n",min(v , T[v]) , max( v , T[v]));

}
else {
int v = ParentFinder (one ,  counter / 2);
printf("The fleas meet at %d.\n",v);
}
counter = 0;
}

ms(touch, 0);
ms(T, 0);

}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10938 - Flea circus

http://www.udebug.com/UVa/10938
Click "Random Input", "Go!"
Check input and AC output for thousands of problems on uDebug!