11299 - Separating Rods

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

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11299 - Separating Rods

Post by sclo » Mon Oct 01, 2007 10:19 am

I don't understand the problem statement. Can someone please explain it more clearly?

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Mon Oct 01, 2007 11:24 am

We have a segment consisting from other segmest.
For example second test: 1 1 10
We have segmens of length 12 (1+1+10).
Now we can make K cut, however we can cut(divide) segment only in places where it is connected.
With one cut from the previous segment we can get only 2(1+1) + 10 or 1 + 11(1+10).

Now we must minimize the longest segment after K cuts, and found the number of ways to achieve this minimum.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 01, 2007 11:28 am

Lomir wrote:We have a segment consisting from other segmest.
For example second test: 1 1 10
We have segmens of length 12 (1+1+10).
Now we can make K cut, however we can cut(divide) segment only in places where it is connected.
With one cut from the previous segment we can get only 2(1+1) + 10 or 1 + 11(1+10).

Now we must minimize the longest segment after K cuts, and found the number of ways to achieve this minimum.
What I don't get is why are there 2 ways of making the longest segment 10.
Nevermind, I now understand.

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Mon Oct 01, 2007 2:55 pm

You dont have to use K separations, the 2 ways are:

(1+1) (10) with 1 separation
(1)(1)(10) with 2 separations

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Oct 02, 2007 8:55 pm

I got many WA on this problem because one of the judge input has n=0
In that case, the correct output is 0 1 which doesn't make sense.

Maybe the maximum element of an empty set is defined to be 0?

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Wed Oct 03, 2007 11:40 pm

In axiomatic set theory, the max of a set is defined to be the supremium
or sup of that set over all values that members of the set can take on.
Actually, the least upper bound (sup or supremum) of the empty set that is a subset of the integers, is negative infinity. However the range of the rods is from [0,+infinity), so it's 0 in this case. It's correct.

See proof below:

Code: Select all


Let K be the miximum length of the rods,

Max({})=Sup({})=min( {0,+infinity} U {0,1,..,K} ) = 0.


Post Reply

Return to “Volume 112 (11200-11299)”