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

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

10685 - Nature

Post by Krzysztof Duleba » 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
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:

Post by Larry » 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..

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

Post by Krzysztof Duleba » 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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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.

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

Post by Krzysztof Duleba » 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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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... :cry:)

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

Wrong problem number

Post by rajsekar_manokaran » Wed Aug 04, 2004 8:18 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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...

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

Post by Krzysztof Duleba » 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 :-)

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » 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.

dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am

Post by dll » 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
Nothing is impossible

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

Post by Krzysztof Duleba » Sun Aug 08, 2004 2:33 pm

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

Post by dll » Sun Aug 08, 2004 3:47 pm

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:

Post by anupam » 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
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:

Post by anupam » 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.
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"

Post Reply

Return to “Volume 106 (10600-10699)”