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... :cry:)

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

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

Code: Select all

removed after ac
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.