10681 - Teobaldo's Trip

Adrian Kuegel · 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 · 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 · 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 ...

Adrian Kuegel · 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 · 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...

jpfarias · 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 · 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.

jpfarias · 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 · 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 · 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 · Post by **Adrian Kuegel** » Sun Jul 18, 2004 11:38 pm

Yes, I think that is clear enough.

technobug · 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 · 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

sohel · 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 · Post by **Larry** » Mon Aug 09, 2004 2:41 pm

Use dynamic programming by first finding a recurrence..

OJ Board

10681 - Teobaldo's Trip

10681 Teobaldo's Trip - facing problems