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