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

Kevin Waugh
New poster
Posts: 4
Joined: Sun Feb 01, 2004 12:44 pm

Post by Kevin Waugh »

The problem statement claims that the graph has no cycles, but my BFS times out unless I check that I only visit each node once. When I do the check, my program WAs.

When I searched the forums there's a post under the Fix Forum that the dataset for this problem was increase. It seems as if this new data has cycles in it?

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

Post by little joey »

My program would shurely time out on cycles, and it doesn't, so there are no cycles.
Don't cause unnecessary panic, please.

Kevin Waugh
New poster
Posts: 4
Joined: Sun Feb 01, 2004 12:44 pm

Post by Kevin Waugh »

The following code wrong answers on 10000:

[cpp]
#include <cstdio>
#include <queue>
#include <utility>
#include <map>
#include <list>

using namespace std;

int main() {
int n;
int c = 1;
while (scanf(" %d", &n) == 1 && n) {
map<int, list<int> > edge;
bool visit[101] = {false};
int s;
scanf(" %d", &s);
int p, q;
while(scanf(" %d %d", &p, &q) == 2 && p && q)
edge[p].push_back(q);

queue< pair<int, int> > bfs;
bfs.push(pair<int,int>(s,0));
int md, mn;
md = 0;
mn = s;
while(!bfs.empty()) {
int cn = bfs.front().first;
int d = bfs.front().second;
bfs.pop();
visit[cn] = true;

if (d > md || (md == d && cn < mn)) {
md = d;
mn = cn;
}

for(list<int>::iterator i = edge[cn].begin();
i != edge[cn].end(); ++i)
if (!visit[*i])
bfs.push(pair<int,int>(*i, d+1));
}

printf("Case %d: The longest path from %d has length %d,"
" finishing at %d.\n\n", c++, s, md, mn);
}
}
[/cpp]


This code times out, and the only thing that is changed is that this code has no checking for revisiting nodes.
[cpp]
#include <cstdio>
#include <queue>
#include <utility>
#include <map>
#include <list>

using namespace std;

int main() {
int n;
int c = 1;
while (scanf(" %d", &n) == 1 && n) {
map<int, list<int> > edge;
int s;
scanf(" %d", &s);
int p, q;
while(scanf(" %d %d", &p, &q) == 2 && p && q)
edge[p].push_back(q);

queue< pair<int, int> > bfs;
bfs.push(pair<int,int>(s,0));
int md, mn;
md = 0;
mn = s;
while(!bfs.empty()) {
int cn = bfs.front().first;
int d = bfs.front().second;
bfs.pop();

if (d > md || (md == d && cn < mn)) {
md = d;
mn = cn;
}

for(list<int>::iterator i = edge[cn].begin();
i != edge[cn].end(); ++i)
bfs.push(pair<int,int>(*i, d+1));
}

printf("Case %d: The longest path from %d has length %d,"
" finishing at %d.\n\n", c++, s, md, mn);
}
}
[/cpp]

So either the sample data has cycles or I'm missing something obvious :) Didn't mean to cause a panic.

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape »

Kevin Waugh wrote:The following code wrong answers on 10000:

...

This code times out, and the only thing that is changed is that this code has no checking for revisiting nodes.
...

[/cpp]

So either the sample data has cycles or I'm missing something obvious :) Didn't mean to cause a panic.
Data has no cycles. BFS can revisit a node even with no cycles.

Code: Select all

1 -> 2
1 -> 3
2 -> 3
No cycles there, and BFS would do: 1 2 3 (from 1) 3 (from 2, revisited)

Saludos,
HoraPe

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape »

horape wrote: BFS can revisit a node even with no cycles.
BFS won't revisit nodes only if graph is a tree.

An undirected graph has no cycles iff it is a tree, maybe your mistake comes from that.

A directed graph can have no cycles and not be a tree.

Saludos,
HoraPe

tlucz
New poster
Posts: 6
Joined: Tue Jan 27, 2004 1:41 pm
Location: Poland/Katowice

Post by tlucz »

I found, why my program gave WA. That was a long line in my program:


[cpp]cout << "Case " << przypadek << ": The longest path from " << poczatek << " has length " << maks << ", finishing at " << najm[poczatek] << "." << endl << endl; [/cpp]

My mail klient wrap this line.

When I change this line on 4 lines

[cpp]cout << "Case " << przypadek << ": The longest path from " << poczatek;
cout << " has length ";
cout << maks << ", finishing at ";
cout << najm[poczatek] << "." << endl << endl;[/cpp]

I've got Accepted reply.
So, you must watch on too long lines.

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape »

tlucz wrote:I found, why my program gave WA. That was a long line in my program:

My mail klient wrap this line.

...

So, you must watch on too long lines.
Or use other mail client. Submitting with the web form is even better.

Saludos,
HoraPe

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier »

Can someone check my code?

[pascal]
Var
c,f,i,l,n,p,q,t: byte;
a: array [1..100,1..100] of boolean;

Procedure visita(v: byte);
var j: byte;
begin
for j:= 1 to n do
if not a[v,j] then
begin
a[v,j]:= true;
Inc(t);
visita(j);
end;
if (t>l) or ((t=l) and (v<f)) then
begin
l:= t; f:= v;
end;
Dec(t);
end;

Begin
readln(input,n); c:= 0;
While (n<>0) do
begin
Inc(c);
fillchar (a, sizeof(a), true);
readln(input,i);
l:= 0; f:= i; t:= 0;
readln(input,p,q);
While (p<>0) and (q<>0) do
begin
a[p,q]:= false;
readln(input,p,q);
end;
visita(i);
writeln(output,'Case ',c,': The longest path from ',i,' has length ',l,', finishing at ',f,'.');
writeln(output);
readln(input,n);
end;
End.
[/pascal]

I checked it severeal times but I keep getting WA! Thanks for your time!
There are 10 kind of people on this world: those who understand binary and those who don't!

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier »

Could someone check my code? Thanks!
There are 10 kind of people on this world: those who understand binary and those who don't!

tymoszenko
New poster
Posts: 3
Joined: Tue Dec 30, 2003 6:24 pm
Location: Brazil
Contact:

10000

Post by tymoszenko »

Please help me.
I really don`t know why I got WA with this code.

Code: Select all

#include <stdio.h>
int g[101][101], marked[101], parent[101], leaf[101], nl;

void refreshMarks(int u, int value, int n){
   int i;
   for(i=0;i<n;i++)
     if (parent[i]==u){
       marked[i]=value;
       break;
   }
   if (i<n) refreshMarks(i, value+1, n);
}

void DFS_visit(int u, int length, int n){
   int i, sons=0;
   marked[u]=length;
   for(i=0;i<n;i++){
     if (g[u][i]&&!marked[i]){
       sons++;
       parent[i]=u;
       DFS_visit(i, length+1, n);
     }
     else if (g[u][i]&&marked[i]<length+1){
       parent[i]=u;
       sons++;
       marked[i]=length+1;
       refreshMarks(i, length+2, n);
     }
   }
   if (sons==0) leaf[nl++]=u;
}

int DFS(int s, int n){
   int i;
   nl=0;
   for(i=0;i<n;i++) marked[i]=0;
   for(i=0;i<n;i++) parent[i]=i;
   for(i=s;i<n;i++)
     if (!marked[i])
        DFS_visit(i, 1, n);
}

int calculeLengthPath(int i, int length){
   if (i==parent[i]) return length;
   else calculeLengthPath(parent[i], length+1);
}

int main(){
   int n, s, i, j, cont=1, max, longNode;
   while(1){
     scanf("%d", &n);
     if (!n) break;
     scanf("%d", &s);
     memset(g, 0, sizeof(g));
     scanf("%d%d", &i, &j);
     while(i>0&&j>0){
       g[i-1][j-1]=1;
       scanf("%d%d", &i, &j);
     }
     DFS(s-1, n);
     longNode=101;
     for(i=max=0;i<nl;i++) {
        j=calculeLengthPath(leaf[i], 0);
        if (max<=j) {
           max=j;
           if (longNode>leaf[i]) longNode=leaf[i];
        }
     }
     printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",
         cont++, s, max, longNode+1);
   }
   return 0;
}
Thanks a lot![/c]
Alexandre Tymoszenko

Bodo
New poster
Posts: 4
Joined: Tue Dec 02, 2003 2:47 pm
Location: Germany
Contact:

Topological Sorting

Post by Bodo »

I tried to solve the problem as follows:
1. Order the nodes topologically (we have an acyclic graph here).
2. Dist(v) = -1 for all nodes, D(Source)=0.
3. For all nodes v in that order:
- For all edges from v to x:
- if(D(v)+1>D(x))
- D(x)=D(v)+1
4. Output the node x with maximum D(x) (if there is a tie, smallest x).

Is there something wrong with my algorithm?

Examiner
New poster
Posts: 28
Joined: Thu Feb 19, 2004 1:19 pm

Re: Topological Sorting

Post by Examiner »

Bodo wrote:2. Dist(v) = -1 for all nodes, D(Source)=0.
If you put Dist[v] = -inf, then your algorithm should be accepted.
What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.
Alan J. Perlis

Bodo
New poster
Posts: 4
Joined: Tue Dec 02, 2003 2:47 pm
Location: Germany
Contact:

Re: Topological Sorting

Post by Bodo »

Examiner wrote:
Bodo wrote:2. Dist(v) = -1 for all nodes, D(Source)=0.
If you put Dist[v] = -inf, then your algorithm should be accepted.
Actually, I handle -1 as -inf. The problem was not my algorithm, but the input. See the "Fixing mistakes" section for more details. Now I received "AC" with my algorithm.

tymoszenko
New poster
Posts: 3
Joined: Tue Dec 30, 2003 6:24 pm
Location: Brazil
Contact:

Post by tymoszenko »

I corrected this problem and got AC. I changed DFS for BFS.

[c]void BFS(int u, int n){
int tail, head, i, t;
for(i=0;i<n;i++) marked=-1;
head=tail=0;
queue[tail++]=u;
marked=0;
while(head!=tail){
u=queue[head++];
for(i=0;i<n;i++)
if (g&&marked<marked+1){
marked=marked+1;
queue[tail++]=i;
}
}
}[/c][/c]
Alexandre Tymoszenko

joshila21
New poster
Posts: 5
Joined: Fri May 07, 2004 12:15 am
Location: bangladesh
Contact:

10000-why wrong answer?

Post by joshila21 »

:oops:
i submitted the following code and get wrong answer.
is there any critical input or i am making a silly mistake?
please some one help me.


#include <stdio.h>

struct {
long s;
long d;
long length;
}x[11000],max;

void find_largest_distance(long,long,long);

void main (void)
{
long i,j,k,l,n,temp1,temp2,start,count=1;
while(1)
{
scanf("%ld",&n);
if(!n)break;
if(count!=1)printf("\n");
scanf("%ld",&start);
i=0;max.length=-1;
while(1)
{
scanf("%ld%ld",&temp1,&temp2);
if(!temp1 && !temp2)break;
x.s=temp1;
x.d=temp2;
x[i++].length=0;
}
find_largest_distance(start,1,i);
printf("Case %ld: The longest path from %ld has length %ld, finishing at %ld.\n",count,start,max.length,max.d);
count++;
}
}

void find_largest_distance(long vertex_,long length_,long n)
{
long i;
for(i=0;i<n;i++)
if(vertex_==x.s)
if(x.length<length_)
{
x.length=length_;
if(length_>=max.length)
{
max.length=length_;
max.d=x.d;
}
find_largest_distance(x.d,length_+1,n);
}
}
be a good man

Post Reply

Return to “Volume 100 (10000-10099)”