10685 - Nature

[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

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

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

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

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

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

[rajsekar_manokaran]

Just a small mistake.
The title of the post is 10865 instead of 10685

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

[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

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

[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

[Krzysztof Duleba]

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

[dll]

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

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

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