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

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

.....

Post by sunmoonstar_love » Sat Oct 15, 2005 5:31 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 ........

:D
I'm from China

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

Re: .....

Post by little joey » Sat Oct 15, 2005 6:24 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sun Oct 16, 2005 2:08 pm

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!

Post by luishhh » Mon Oct 17, 2005 8:31 pm

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:

Post by mf » Mon Oct 17, 2005 9:42 pm

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

Post by elmohandis » Tue Oct 18, 2005 12:15 am

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

Post by luishhh » Tue Oct 18, 2005 11:26 pm

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 :D
"From lost to the river" --> Spanish quote

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sat Oct 22, 2005 9:53 pm

My solution achieves O(log n) time per query
thnx mf .. now I have one of the better timings.
Where's the "Any" key?

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

Re: 10938 - Flea circus

Post by marcadian » Sat Jun 14, 2008 9:54 am

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

Post by Shafaet_du » Tue Oct 25, 2011 11:09 pm

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
Location: Bangladesh
Contact:

Re: 10938 - Flea circus

Post by Imti » Tue Nov 15, 2011 12:06 am

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

Post by Farsan » Sun May 11, 2014 5:39 am

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) :evil: . 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

Post by brianfry713 » Mon May 12, 2014 10:41 pm

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

Post by Repon kumar Roy » Fri Oct 31, 2014 11:06 pm

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.
//  Copyright (c) 2014 Repon Macbook. All rights reserved.
//


#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 ;
vector<int>  adjList[MX];
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;
			adjList[a].pb(b);
			adjList[b].pb(a);
		}
		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;
		}
		
		
		FOR(i, vertex+1) adjList[i].clear();
		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

Post by brianfry713 » Wed Nov 05, 2014 11:16 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”