10000 - Longest Paths

All about problems in Volume 100. 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
User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Sun Dec 26, 2004 9:07 am

very complex implementation of BFS indeed.
you have used adjacency list.
while(v && e)
{
j=0;
while(p[v].paths[j]>=0)j++;
p[v].paths[j]=e;
scanf("%d %d",&v,&e);
}
for the colored part you can use another counter array.it will reduce the time.


set max=-1;


for(j=0;j<=N;j++)
{
if(p[j].dis>max)
{
max=p[j].dis;
end=j;
}
}


why j=0,don't know.

no need of the condition , atleast for this program
if(counter>p[p[q].paths[j]].dis)
so u can remove it.

by the way the matrix method implementation is easier for this program.
cuii e

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

10000 Why TLE ??

Post by Ali Arman Tamal » Sun Jan 30, 2005 8:25 am

I'm getting TLE :cry: don't know why...

Here is my code

Code: Select all

#include <stdio.h>

int a[101][101],parent[101],d[101];
int n,root,casecount=0;

void process(int k);
void findpath();

int main()
{

	int i,j;

	while(1)
	{
	scanf("%d",&n);
	if(n==0)break;

	casecount++;

	for(i=1;i<=n;i++)
	{
		parent[i]=-1;
		d[i]=0;
		for(j=1;j<=n;j++)a[i][j]=0;
	}

	scanf("%d",&root);
	parent[root]=-1;

	while(1)
	{
	scanf("%d %d",&i,&j);
	if(i==0 && j==0)break;
	a[i][j]=1;
	}

	process(root);

	findpath();

	}

return 1;
}



void process(int k)
{

	int i=1;

	while(i<=n)
	{
		if(a[k][i]==1)if(d[k]+1>d[i]){ d[i]=d[k]+1; parent[i]=k; }
		i++;
	}

	i=1;
	while(i<=n){ if(a[k][i]==1)process(i); i++; }

}


void findpath()
{
int k,max=root,count;

for(k=1;k<=n;k++)
{
if(d[k]>d[max])max=k;
else if(d[k]==d[max] && k<max)max=k;
}

count=0;

if(max!=root){
	k=max;
	while(parent[k]!=-1){ k=parent[k]; count++; }
}

printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",casecount,root,count,max);

}
The problem description says
You can assume that the graph has no cycles (there is no path from any node to itself),
My code will certainly give TLE if the graph is cyclic, but I'm not sure if it is the reason. :o


THANKS FOR READING !! :) [/quote]

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue Feb 01, 2005 1:00 pm

hi
i have used only BFS algorithm and just got AC
u can use BFS algorithm

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

Post by Ali Arman Tamal » Mon Feb 07, 2005 4:03 am

The previous attempt was buggy. Now I got AC with BFS :D

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

10000, help me to understand the meaning of "p,q"

Post by ImLazy » Thu Feb 24, 2005 9:13 am

Does the pair of p and q means:
1.There is a path from p to q. And there may be some other nodes between p and q. For example, it can be p->1->2->q
Or
2.There is a edge from p to q in the graph. That is p->q, no other nodes between them.
Which of the two understanding is right?
I stay home. Don't call me out.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 10000, help me to understand the meaning of "p,q&qu

Post by CDiMa » Thu Feb 24, 2005 10:18 am

ImLazy wrote:Does the pair of p and q means:
1.There is a path from p to q. And there may be some other nodes between p and q. For example, it can be p->1->2->q
Or
2.There is a edge from p to q in the graph. That is p->q, no other nodes between them.
Which of the two understanding is right?
The latter will do...

Ciao!!!

Claudio

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Feb 24, 2005 10:24 am

Thank you, CDiMa.
And I was so silly because the first understanding doesn't fit the sample output.
I stay home. Don't call me out.

kruslan
New poster
Posts: 2
Joined: Wed Jun 08, 2005 9:17 pm
Location: KZ
Contact:

10000 WA

Post by kruslan » Wed Jun 08, 2005 9:24 pm

Cant find the problem... I'm always getting WA...

Code: Select all

const maxn = 100;

var a : array [0..maxn,0..maxn] of integer;
    q,l : array [0..maxn*maxn] of integer;
    c,n,i,x,y,st,max,maxi,t,j,yk,yp,cur : integer;
    w : array [0..maxn+1,0..maxn+1] of boolean;
    h : boolean;

begin
{  assign(input,'input.txt'); reset(input);
  assign(output,'output.txt'); rewrite(output);
}
  n:=1;
  c:=0;
  while n<>0 do
  begin
    readln(n);
    if n>0 then
    begin
      {}
      readln(st);
      fillchar(a,sizeof(a),0);
      x:=1; y:=1;
      while not((x=0)and(y=0)) do
      begin
        readln(x,y);
        if not((x=0)and(y=0)) then
        begin
          inc(a[x,0]);
          a[x,a[x,0]]:=y;
        end;
      end;
      {}
      max:=0; maxi:=st;
      yk:=1; yp:=1; q[yk]:=st; l[yk]:=0;
      while yk<=yp do
      begin
        cur:=q[yk];
        for i:=1 to a[cur,0] do
        begin
          if w[a[cur,i],l[yk]+1]=false then
          begin
            w[a[cur,i],l[yk]+1]:=true;
            inc(yp);
            q[yp]:=a[cur,i];
            l[yp]:=l[yk]+1;
          end;
        end;
        if (l[yk]>max)or((l[yk]=max)and(q[yk]<maxi)) then
        begin
          max:=l[yk];
          maxi:=q[yk];
        end;
        inc(yk);
      end;
      {}
      inc(c);
      writeln('Case ',c,': The longest path from ',st,' has length ',max,', finishing at ',maxi,'.');
      writeln;
      {}
    end;
  end;
{  close(input); close(output);}
end.

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Thu Jun 09, 2005 9:28 am

I tested it on:

Code: Select all

2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
2
1
1 2
0 0
0
And it produced:

Code: Select all

Case 1: The longest path from 1 has length 1, finishing at 2.

Case 2: The longest path from 3 has length 4, finishing at 5.

Case 3: The longest path from 5 has length 2, finishing at 1.

Case 4: The longest path from 1 has length 0, finishing at 1.
The output should be:

Code: Select all

Case 1: The longest path from 1 has length 1, finishing at 2.

Case 2: The longest path from 3 has length 4, finishing at 5.

Case 3: The longest path from 5 has length 2, finishing at 1.

Case 4: The longest path from 1 has length 1, finishing at 2.
... since input data for Case 1 and Case 2 is the same. :)

Try initializing the w[][] variable before anything else is done. :wink:

Code: Select all

for i := 0 to maxn+1 do
  for j := 0 to maxn+1 do
    w[i][j] := false;

kruslan
New poster
Posts: 2
Joined: Wed Jun 08, 2005 9:17 pm
Location: KZ
Contact:

Post by kruslan » Thu Jun 09, 2005 10:22 am

What a silly mistake....
Thank you very much

I added line fillchar(w,sizeof(w),false);
And got AC

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

10000 Longest Paths - TLE

Post by pipo » Tue Feb 14, 2006 6:43 pm

hi all...

I solved this problem(10000-longest paths) using back-tracking algorithm technic...

it gave me correct answers for the sample input..

but.. judger replied the code was TLE...

it is so fool of me... :cry:

how do I speed up using back-tracking algorithm technic ??

and would you give me a sample test case which occurs TLE ??

thanks in advance...

ps.. sorry for poor english... excuse me :)

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Tue Feb 14, 2006 10:12 pm

You can speed it up simply using some pruning. say you are in node n and you know it was previously explored in depth d[n]. if you reach this node again from another path with depth curr_depth you only explore it if d[n]<curr_depth.

hope it helps..

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Wed Feb 15, 2006 5:08 am

Using DFS should work as well. I got AC using DFS and C++ STL for a reasonable time. Keeping track of visited nodes will help.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Sun Mar 05, 2006 1:19 am

Salamo Aleko
As for ur code u need to prune ur search as guided above........
But you also can solve this problem easily by using floyd warshal algorithm to find shortest path... :P Only you need to minor changes
To make it find the longest path

Using bfs or dfs I got ac in 0.387s
Using floyd I got ac in 1.275

http://acm.uva.es/problemset/usersjudge.php?user=8957CA

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

10000 `algo

Post by smilitude » Thu May 11, 2006 8:36 am

Is my algo wrong??

Code: Select all

/*
 * 10000 longest path
 * submission 1 WA
 * coded at 1157am , may 11, 2006
 */

#include <cstdio>
#include <queue>
#define max(a,b) (((a)>(b)) ? (a):(b))
using namespace std;

int main() {
    struct {
        int edge[100];
        int nedge;
        int dist;
        bool processed;
        bool discovered;
    }node[101];
    
    int n,s,i,j,a,b,cur,max,end,cases=0;
    int cedge;
    queue<int> Q;
    
    while(scanf("%d",&n)==1 && n) {
        scanf("%d",&s);
        
        //init
        for(i=1;i<=n;i++) {
            node[i].nedge=0;
            node[i].dist=0;
            node[i].processed=node[i].discovered=false;
        }
        
        //input
        while(true) {
            scanf("%d%d",&a,&b);
            if(a==0 && b==0) break;
            node[a].edge[node[a].nedge++]=b;
        }
        
        //bfs
        Q.push(s);
        while(!Q.empty()) {
            cur=Q.front();
            Q.pop();
            for(i=0;i<node[cur].nedge;i++) {
                cedge=node[cur].edge[i];
                node[cedge].dist=max(node[cedge].dist,node[cur].dist+1);
                if(node[cedge].processed) continue;
                if(!node[cedge].discovered) {
                    node[cedge].discovered=true;
                    Q.push(cedge);
                }
            }
            node[cur].processed=true;
        }
        
        //finding max
        max=0;
        for(i=1;i<=n;i++) {
            if(node[i].dist>max) {
                max=node[i].dist;
                end=i;
            }
        }
        printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",++cases,s,max,end);
    }
return 0;
}
I am getting wrong answer, :o
Can anyone help me ?
fahim
#include <smile.h>

Post Reply

Return to “Volume 100 (10000-10099)”