10938 - Flea circus

[sunmoonstar_love]

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

[little joey]

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]

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

[luishhh]

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

[mf]

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.

edges = vertices - 2;/*I've already read an edge*/
while (edges--) {

Think, what happens to this loop when vertices==1.

[elmohandis]

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]

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

[Solaris]

My solution achieves O(log n) time per query

thnx mf .. now I have one of the better timings.

[marcadian]

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]

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]

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]

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

[brianfry713]

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.

[Repon kumar Roy]

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]

http://www.udebug.com/UVa/10938
Click "Random Input", "Go!"