302 - John's trip

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

Moderator: Board moderators

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Fri Nov 04, 2005 6:17 pm

I got Accepted after got WA many times.

If you are trying to solve it, you must realize:

There are something wrong in this problem.

The street number can be large than 44. ( I think it is less than 2000 )

And John lives at the street of the first line of each data block.
not the "number 1" street!

and you can just use DFS to solve it.
or you can use euler cycle method.

Mr.south
New poster
Posts: 11
Joined: Thu Jan 25, 2007 1:45 pm

help 302

Post by Mr.south » Mon Feb 12, 2007 7:16 pm

i use eulerian circuit to solve this question
but i got a problem
I have some problem when i got a vertex, this vertex has more than two edges, my code will choose the smallest num of vertex to put in the stack, but i think this is wrong

ex. when i got node 2, this node has edge 1, 2, 3, 4, 5. what edge should i choose and push the related vertex in the stack

this is part of my code

void find_circuit(int i)
{
int j, min;

if(degree == 0)
{
push(stack, i);
return;
}
for(j=0;j<45;j++) // check the whole neighbors
{
if(adj[j] > 0) //there exist more than 1 edges
{
if(visited[j] > 0) visited[j]--; //i use this to check whether the graph is connected
adj[j]--; //kill one edge (i, j) (j, i)
adj[j]--;
degree--;
degree[j]--;
find_circuit(j);
}
}
push(stack, i);
}

porker2008
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

Why 302 TLE?

Post by porker2008 » Fri Oct 17, 2008 9:53 am

I have solved 302 by using DFS Algorithm. However, I get TLE.

I don't know what kind of cases will lead to TLE. Can somebody tell me.

I find my program run fast on my computer even though the cases are very complicated.

I think I must ignore some special cases that beyond my thinking.

porker2008
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

Re: Why 302 TLE?

Post by porker2008 » Fri Oct 17, 2008 10:01 am

Code: Select all

#include<iostream>
#include<vector>
using namespace std;

void check(int i,int loc);

vector<int> a1,a2,street;
int order[2000];
bool finish=false,pass=false;
int num;
bool used[2000];
bool checked[2000];

int main(){
    int b1,b2,st;
    while(cin>>b1>>b2){
                       a1.clear(); a2.clear(); street.clear();
                       if(b1==0&&b2==0) break;
                       a1.push_back(b1);
                       a2.push_back(b2);
                       cin>>st;
                       street.push_back(st);
                       while(cin>>b1>>b2){
                                          if(b1==0&&b2==0) break;
                                          a1.push_back(b1);
                                          a2.push_back(b2);
                                          cin>>st;
                                          street.push_back(st);
                       }
                       num=street.size();
                       memset(used,0,sizeof(used));
                       int loc=min(a1[0],a2[0]);
                       finish=false;
                       pass=false;
                       memset(order,0,sizeof(order));
                       check(0,loc);
                       if(pass){
                                for(int i=0;order[i]!=0;i++) {cout<<order[i]; if(order[i+1]!=0) cout<<" ";}
                                cout<<endl<<endl;
                       }
                       else
                       cout<<"Round trip does not exist."<<endl<<endl;
    }
    return 0;
}
//Using DFS to find the order.
void check(int i,int loc){
     if(i==street.size()&&loc==min(a1[0],a2[0])){pass=true;finish=true;return;}
     int min=-1;
     int tmin=2000;
     int num=0;
     for(int j=0;j<street.size();j++)
             if(!used[j]&&(a1[j]==loc||a2[j]==loc)) num++;
     for(int k=0;k<num&&!pass&&!finish;k++){
             int tmin=2000;
             int l=2000;
             for(int j=0;j<street.size();j++)
                     if(!used[j]&&(a1[j]==loc||a2[j]==loc)&&street[j]>min&&street[j]<tmin) {tmin=street[j];l=j;}
             min=street[l];
             used[l]=true;
             if(l==2000) {break;}
             if(a1[l]==loc) {order[i]=street[l]; check(i+1,a2[l]);}
             else {order[i]=street[l]; check(i+1,a1[l]);}
             used[l]=false;
             if(!pass) order[i]=0;
     }
     return;
}

sami001
New poster
Posts: 3
Joined: Thu Jun 17, 2010 5:19 pm

Re: 302 (John's trip) test cases

Post by sami001 » Tue Nov 23, 2010 10:32 pm

i'm getting RTE... :cry: pls... somebody help me::

Code: Select all

#include <stdio.h>

int main()
{

	int j1,j2,r,i,k,a,b,c,H,m,n,p,p1,sum,j,q,l,s,t,u,junc[50][2],result[2000],search,flag,mem;

	while(1){

		int g[50][2000]={0},g1[50][2000]={0};
		a=0;
		b=0;
		n=0;
		flag=0;
		
		for(i=0;;i++)
		{
			
			scanf("%d %d",&j1,&j2);
			if(j1==0 && j2==0 && i==0){n=1;break;}
			else if(j1==0 && j2==0)break;
			scanf("%d",&r);
			
			if(i==0)
			{
				if(j1>j2)H=j2;
				else H=j1;
			}
			
			
			if(j1!=j2)
			{
				g[j1][r]=g1[j1][r]=1;
				g[j2][r]=g1[j2][r]=1;
			}
			
			else if(j1==j2)
			{
				g[j1][r]=g1[j1][r]=2;
				g[j2][r]=g1[j2][r]=2;
			}
			
			if(r>a)a=r;
			if(j1>b)
			{
				b=j1;
				if(j2>j1)b=j2;
			}
		}
		
		if(n==1)break;
		n=0;
		
		for(i=1;i<=b;i++)
		{
			sum=0;
			for(k=1;k<=a;k++)sum+=g[i][k];
			if(sum%2==1){printf("Round trip does not exist.\n");printf("\n");n=1;break;}
		}
	
	    if(n==1)continue;
	    i=H;
	    m=a+1;
	    junc[0][0]=H;
		
		
		p=0;
	    s=0;

	    while(p!=a)
		{

			search=0;
			if(flag==1)mem=result[p+1];
			
			n=0;
		    q=0;
		
		    for(j=1;j<=a;j++)if(g[i][j]==1)n++;
		

		    if(n<=1)
			{
			    for(j=1;j<=a;j++)if(g[i][j]==2)
				{
				    result[p+1]=j;
					g[i][j]=0;
				    p++;
				    q=1;
					search=1;
				}
				
			}

		    n=0;
			
			for(j=1;j<=a;j++){
				
				if(j==m)continue;
					
				if(g[i][j]==1)
				{
					
					if(q==0){
						 for(k=1;k<=a;k++){
							 if(g[i][k]==2 && k<j){g[i][k]=0;result[p+1]=k;search=1;p++;}
							 else if(g[i][k]==2 && k>j)break;
						 }
					}
					result[p+1]=j;
					p++;
					search=1;
					l=i;
					for(i=1;i<=b;i++)g[i][j]=0;
					
					break;
				  }
			}
			
			
			if(search==0){
				s--;
				i=junc[s][0];
			    m=1;
				if(flag==0)p1=p;
				
				flag=1;
				
				p=junc[s][1];
			    continue;
			}
			
			else if(search==1 && flag==1){


				for(t=p1;t>=p+1;t--){
					c=result[t];
					for(u=1;u<=b;u++)g[u][c]=g1[u][c];
				}
				for(u=1;u<=b;u++)g[u][mem]=g1[u][mem];
				
				flag=0;
			}
			
			m=j;
			for(k=1;k<=b;k++){
				if(g1[k][j]==1 && k!=l)i=k;
			}
		    
			s++;
		    junc[s][0]=i;
			junc[s][1]=p;
		}
		
		for(s=1;s<=a;s++)
		{
			if(s<a)printf("%d ",result[s]);
			else printf("%d\n\n",result[s]);
		}
			
		}
		
		return 0;

}

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 302 - John's trip

Post by dibery » Mon Feb 23, 2015 11:14 am

Note that the "lexicographical order" is not what we used for strings.
Rather, it's for numeric values.
For example, if "9 10" & "10 9" are both solutions, we should print "9 10" instead of "10 9" because 9 goes before 10.
Life shouldn't be null.

Post Reply

Return to “Volume 3 (300-399)”