10681 - Teobaldo's Trip

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

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 6:03 pm

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 6:10 pm

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

Post by Observer » Sun Jul 18, 2004 6:18 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 6:27 pm

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

Post by Observer » Sun Jul 18, 2004 6:34 pm

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

Post by jpfarias » Sun Jul 18, 2004 8:58 pm

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 11:11 pm

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:

Post by jpfarias » Sun Jul 18, 2004 11:19 pm

Yeah, you're right again.

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

JP.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 11:26 pm

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:

Post by jpfarias » Sun Jul 18, 2004 11:29 pm

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 11:38 pm

Yes, I think that is clear enough.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Mon Jul 19, 2004 7:47 am

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:

Post by sergio » Mon Jul 19, 2004 3:28 pm

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

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

10681 Teobaldo's Trip - facing problems

Post by sohel » Mon Aug 09, 2004 1:17 pm

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:

Post by Larry » Mon Aug 09, 2004 2:41 pm

Use dynamic programming by first finding a recurrence..

Post Reply

Return to “Volume 106 (10600-10699)”