Page 1 of 3

### 10685 - Nature

Posted: Wed Aug 04, 2004 5:48 pm
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
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
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
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
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
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
Just a small mistake.
The title of the post is 10865 instead of 10685

Posted: Wed Aug 04, 2004 9:02 pm
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
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
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
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
First you can try my input. Do you get 1 3 4 2 9?

Posted: Sun Aug 08, 2004 3:47 pm
for your input, the output of my program is the same as yours.

Posted: Sun Aug 08, 2004 9:12 pm

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

Code: Select all

``````removed after ac
``````

Posted: Sun Aug 08, 2004 9:14 pm
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.