Page **1** of **3**

### 10685 - Nature

Posted: **Wed Aug 04, 2004 5:48 pm**

by **Krzysztof Duleba**

I'm not sure what "the largest chain" means here since there may be cycles in the input. What is the right answer for those cases?

3 0

a

b

c

5 4

a

b

c

d

e

b a

c a

b c

c b

4 4

a

b

c

d

a b

b c

c a

d b

2 2

a

b

a b

b a

9 10

a

b

c

d

e

f

g

h

i

b a

c b

d c

e d

c e

f e

g f

e g

a h

i c

0 0

Posted: **Wed Aug 04, 2004 6:21 pm**

by **Larry**

Basically, if a is a predator of b, then they are in the same chain. So you have to find the biggest such chain by using union find or recursion. I don't have my program with me, but I'll run them through later if you're still unclear..

Posted: **Wed Aug 04, 2004 6:53 pm**

by **Krzysztof Duleba**

It is unclear. Now I use DFS starting from each verticle of a graph. That gives me the longest path, but each verticle can appear only once.

If verticles could appear more than once, how should I treat cases with cycles? The answer would be infinity.

Posted: **Wed Aug 04, 2004 7:11 pm**

by **little joey**

Just forget about graphs, this problem is about sets. If A is a predator of B then A and B are in the same set. The problem is about finding the largest set. The description of this problem is misleading (see previous discussions).

The answers to your input are 1 3 4 2 9.

Posted: **Wed Aug 04, 2004 7:37 pm**

by **Krzysztof Duleba**

If it is so, then the problem statement is very, very misleading. Thanks for help. Now it should be pretty easy.

You referred to some "previous discussions". Where can I find them? I searched the board for "nature" with no significant hits.

Posted: **Wed Aug 04, 2004 7:54 pm**

by **little joey**

It's a previous discussion on "Theobaldo's Trip" in the v106 forum. (I still don't know how to include links to message boards in my postings...

)

### Wrong problem number

Posted: **Wed Aug 04, 2004 8:18 pm**

by **rajsekar_manokaran**

Just a small mistake.

The title of the post is 10865 instead of 10685

Posted: **Wed Aug 04, 2004 9:02 pm**

by **little joey**

Well, there is a small, but non-zero chance that problem 10865 will be titled "Nature II" and that it is about graphs, although the description strongly suggests that it is about sets...

Posted: **Thu Aug 05, 2004 12:44 am**

by **Krzysztof Duleba**

So the prob 10865 wasn't used yet? Gosh, I spoiled it. I should never again use my local base of all problems instead of official website.

Of cource now I have to write to 10865's author about it that his problem will be erased and replaced by something else.

I looked at 10685 too and using your advice to forget about graphs, I got AC. Thanks

Posted: **Sat Aug 07, 2004 10:25 am**

by **Maniac**

Just to make sure everybody understands the problem:

If you think in terms of graphs, the goal is to find the largest connected component in the graph, not the longest path or the largest number of vertices in a path. So a chain is a connected subgraph and not a path.

Posted: **Sun Aug 08, 2004 9:56 am**

by **dll**

anyone who got AC give me some IO ?

I got WA. Do I find the largest connected component ?

or I misunderstand the problem ?

thanks

Posted: **Sun Aug 08, 2004 2:33 pm**

by **Krzysztof Duleba**

First you can try my input. Do you get 1 3 4 2 9?

Posted: **Sun Aug 08, 2004 3:47 pm**

by **dll**

for your input, the output of my program is the same as yours.

Posted: **Sun Aug 08, 2004 9:12 pm**

by **anupam**

Can anyone please tell me why the code is getting TLE? I used the same code for "10608 friends".

Please help me. getting TLE 3 times. How to improve or is there any silly mistake?

Here is the code...

Please help...[/i][/b]

Posted: **Sun Aug 08, 2004 9:14 pm**

by **anupam**

And also, what's about the time limit? TIME LIMIT IN THE PROB. STS is 40 seconds. But TLE in 10 sec?

What I got after accepted is that, In pure C you can use binary search, mapping. By using STL and MAP you can get accepted in a very short time.