10681  Teobaldo's Trip
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
No, it makes sense with my interpretation of the problem description.
You are given a predator relation, that means directed edges in a graph.
Now an alimentary chain is just a path in this graph, at least this is the most logical interpretation of chain, and chain was nowhere defined.
So I have to find largest chain, that means longest path in the graph.
You are given a predator relation, that means directed edges in a graph.
Now an alimentary chain is just a path in this graph, at least this is the most logical interpretation of chain, and chain was nowhere defined.
So I have to find largest chain, that means longest path in the graph.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
This is what I found as definition of chain in the internet (http://www.websterdictionary.org/definition/chain ):
So it is a series of things following each other in succession. Therefore longest path = largest chain seems to be the most logical interpretation of the problem.
A series of things linked together  I think this can be discarded, because predator is a directed edge, not undirected.A series of things linked together; or a series of things connected and following each other in succession; as, a chain of mountains; a chain of events or ideas.
So it is a series of things following each other in succession. Therefore longest path = largest chain seems to be the most logical interpretation of the problem.
Yes, I also don't think that such a thing is regarded as a "chain":
Code: Select all
A>D G
 ^
v 
B>C>E>F>H
 
v v
I J ...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Why? I think such a thing is only a chain, if edges are undirected, like:
Because if chain is seen as rings put into each other, this is an undirected edge.
Code: Select all
A<>D G
^ ^ ^
  
v v v
B<>C<>E<>F<>H
^ ^
 
v v
I J
[EDIT] What I want to say is, the word "chain" in the decription makes us think about "chain letters", "chain reaction" etc and misunderstand the problem. The result? Loads of WAs of course!
No one creates unsolvable problems in a contest, right? What we want is just clear problem descriptions! The idea of relating tasks to reallife situations is good; but in this case, it's annoying.
Btw, now I think this task is no different from ACM 10608 Friends, whose instructions is much clearer than Prob E...
No one creates unsolvable problems in a contest, right? What we want is just clear problem descriptions! The idea of relating tasks to reallife situations is good; but in this case, it's annoying.
Btw, now I think this task is no different from ACM 10608 Friends, whose instructions is much clearer than Prob E...
Last edited by Observer on Mon Jul 19, 2004 12:04 pm, edited 3 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Get a graphs book and look for chain. I've found this definition:
Path: A path from node (i0 to node ip) is a sequence of arcs P = { (i0, i1), (i1, i2), ..., (ip1, ip) } in which the initial node of each arc is the same as the terminal node of the preceding arc in the sequence. Thus each arc in the path is directed "toward" ip and away from i0.
Chain: A chain is a similar structure to a path except that not all arcs are necessarily directed toward ip.
Then it shows two pictures, one with a path and one with a chain, I'll try to mimic:
Following it defines a circuit and a cycle.
Circuit: A circuit is a path with ip = i0. Thus a circuit is a closed path.
Cycle: A cycle is a closed chain.
Every path is a chain, but not vice versa. Every circuit is a cycle, but not conversely.
Again, mimic of pictures:
The version I own of this book is just a copy os some chapters, I'll try to find out the author and everything else to properly identify it, and I'll post that info here.
JP.
Path: A path from node (i0 to node ip) is a sequence of arcs P = { (i0, i1), (i1, i2), ..., (ip1, ip) } in which the initial node of each arc is the same as the terminal node of the preceding arc in the sequence. Thus each arc in the path is directed "toward" ip and away from i0.
Chain: A chain is a similar structure to a path except that not all arcs are necessarily directed toward ip.
Then it shows two pictures, one with a path and one with a chain, I'll try to mimic:
Code: Select all
A > B A > B
 ^
v 
C > D C > D
(a) A path (b) A chain
Circuit: A circuit is a path with ip = i0. Thus a circuit is a closed path.
Cycle: A cycle is a closed chain.
Every path is a chain, but not vice versa. Every circuit is a cycle, but not conversely.
Again, mimic of pictures:
Code: Select all
A > B A > B
^   
 v v v
 C > D C > D
 

(c) circuit (d) cycle
JP.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Thank you for these definitions. I learn something new
But as far as I understood, in your problem description you need another definition of chain, otherwise the answer would be to find largest distance between two points in a tree.
So for example, if the relations are like
b a
c b
d c
e d
f c
The largest chain would be a b c d e with length 5,
and largest connected component would have size 6.
But as far as I understood, in your problem description you need another definition of chain, otherwise the answer would be to find largest distance between two points in a tree.
So for example, if the relations are like
b a
c b
d c
e d
f c
The largest chain would be a b c d e with length 5,
and largest connected component would have size 6.
Last edited by Adrian Kuegel on Sun Jul 18, 2004 11:21 pm, edited 1 time in total.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I am not sure who adds the problems to the online judge.
Maybe you can write an email to problemset@acm.uva.es
At least this is the right address for problems in the problemset.
Maybe you can write an email to problemset@acm.uva.es
At least this is the right address for problems in the problemset.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
coming back to problem A.... it does not mention that teobaldo cant do something like:
1 > 2 > 3 > 1 > 4
Is teobaldo allowed to go back to a city AFTER one day? It simply mentions that he cant do it in the next day..
i was thinking that as it doesnt mention such a thing, we are supposed to do a UNIONFIND check and then a DFS in order to find a valid way.... as BFS would be as bad as DFS when in its worst case....
anyway, i could not run away from TLE.... how did anyone solve it?
1 > 2 > 3 > 1 > 4
Is teobaldo allowed to go back to a city AFTER one day? It simply mentions that he cant do it in the next day..
i was thinking that as it doesnt mention such a thing, we are supposed to do a UNIONFIND check and then a DFS in order to find a valid way.... as BFS would be as bad as DFS when in its worst case....
anyway, i could not run away from TLE.... how did anyone solve it?
10681 Teobaldo's Trip  facing problems
I looked at the previous thread but found nothing cos it was mainly about other problems.
I used bfs without coloring and got memory limit exceeded, and rightly so cos the value of D is quite significant.
> can the destination be one of the nodes in the intermediate path?
The submission and the ac number of this problem seems to be quite high.. am I missing something here?
Some hints would be appreciated.
I used bfs without coloring and got memory limit exceeded, and rightly so cos the value of D is quite significant.
> can the destination be one of the nodes in the intermediate path?
The submission and the ac number of this problem seems to be quite high.. am I missing something here?
Some hints would be appreciated.