## 10685 - Nature

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

### 10685 - Nature

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
Last edited by Krzysztof Duleba on Sun Aug 08, 2004 2:34 pm, edited 1 time in total.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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... )

rajsekar_manokaran
New poster
Posts: 9
Joined: Fri Feb 20, 2004 6:48 am
Location: India
Contact:

### Wrong problem number

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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...

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
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
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 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
Nothing is impossible

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
First you can try my input. Do you get 1 3 4 2 9?

dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am
for your input, the output of my program is the same as yours.
Nothing is impossible

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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]
Last edited by anupam on Sun Aug 08, 2004 10:01 pm, edited 1 time in total.
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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.
Last edited by anupam on Wed Aug 11, 2004 10:01 am, edited 3 times in total.
"Everything should be made simple, but not always simpler"