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.

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.webster-dictionary.org/definition/chain ):
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.
A series of things linked together - I think this can be discarded, because predator is a directed edge, not undirected.
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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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

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:

Code: Select all

``````A<->D       G
^   ^       ^
|   |       |
v   v       v
B<->C<->E<->F<->H
^   ^
|   |
v   v
I   J``````
Because if chain is seen as rings put into each other, this is an undirected edge.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
[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 real-life 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

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
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), ..., (ip-1, 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

``````
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:

Code: Select all

``````
A -> B                           A -> B
^    |                           |    |
|    v                           v    v
|    C -> D                      C -> D
|         |
-----------

(c) circuit                      (d) cycle

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

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.
Last edited by Adrian Kuegel on Sun Jul 18, 2004 11:21 pm, edited 1 time in total.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Yeah, you're right again.

Maybe I can make it more clear before it goes to the online judge. Is that possible?

JP.

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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Do you think that if I just say that if A is predator of B then they are in the same chain the problem will be clear enough?

JP.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Yes, I think that is clear enough.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
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 UNION-FIND 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?

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
Hi, everybody!!

I tried to correct the problems during the contest, but occurred a problem with the mail service at UFRN, and I did not receive any question and I think the messages I sent did not arrived.

We are fixing the errors now and I will send the corrected version.

S

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Use dynamic programming by first finding a recurrence..