DWITE Online Computer Programming Contest
February 2006
Problem 2
Floppy Disk 3 ½- inch High Density
Over the course of approximately 35 years, floppy disks have evolved from 8 inches in size down to 3 ½ inches.
Their storage capacity ranged from 80 kilobytes (KB) to 240 megabytes (MB). Most recently they are becoming
extinct, with floppy disk drives being an optional accessory with the purchase of a new computer.
One of the more commonly used floppy disk, during its time, was the 3 ½ -inch 1.44 MB capacity disk.
Your job in this problem is to put files onto the 3 ½ -inch 1.44 MB capacity disk so that there is a minimum
amount of unused space left on the floppy disk.
The input file (DATA21.txt for the first submission and DATA22.txt for the second submission) will contain
five sets of data. Each set begins with the an integer, N, the number of files available to go onto the floppy disk,
1 <= N <= 25. The next N lines, for each set, will contain S, an integer, the size, in kilobytes (KB), of each of
the files, 1 <= S <= 1440.
The output file (OUT21.txt for the first submission and OUT22.txt for the second submission) will contain five
lines of data. Each line will contain the minimum amount of unused space left on the floppy disk.
Sample Input ( 3 sets of data only)
5
1000
500
100
150
400
6
500
233
650
75
22
875
4
235
578
900
599
Sample Output
40
35
28
Sample Input Analysis
In the first set, the files with sizes 1000 and 400 use up the most storage space on the diskette.
In the second set, the files with sizes 650, 500, 233 and 22 use up the most storage space on the diskette.
In the third set, the files with sizes 599, 578 and 235 use up the most storage space.

how about giving me 100 bits? I think I deserved it

AH! Excellent description Martin If you werent a mod I would give you 100 bits My next question was "I dont get it, explain" I was about to post that but your post made me understand it! I am gonna go over it again and do the rest of the problems that I wasnt able to do which used DP. Thanks a lot

It takes a bit to wrap your head around, but it's not difficult.

You have a sentence written entirely in a single row. You would like to split it into several rows by replacing some of the spaces with "new row" indicators. Your goal is to minimize the width of the longest row in the resulting text ("new row" indicators do not count towards the width of a row). You may replace at most K spaces.

You will be given a String sentence and an int K. Split the sentence using the procedure described above and return the width of the longest row.

Definition

Class: SentenceSplitting
Method: split
Parameters: String, int
Returns: int
Method signature: int split(String sentence, int K)
(be sure your methodis public)


Constraints
- sentence will contain between 1 and 50 characters, inclusive.
- sentence will consist of only letters ('a'-'z', 'A'-'Z') and spaces (' ').
- Each space character in sentence will be between two letters.
- K will be between 1 and 50, inclusive.

Examples
0)


"This is a test sentence"

1

Returns: 13

You should split the sentence between the words "a" and "test".
1)


"TheOnlyWord"

37

Returns: 11

2)


"One veeeeeeeeeeeeeeeeeeery long word"

2

Returns: 22

3)


"Each tournament round is an elimination round"

3

Returns: 15

It's like this.

We know that worst case, we can't fit anything onto the disk. So that's our base case ... d[0]:=true (the rest of the array is initialized to false)

Think of it like a distance thing ... how far away from 0 can we get as a combination of the files?


For each file we go backwards through our table - as bugz said, we don't care which files are put into the table, but that each one can be used once.

For example, suppose instead of 1440 we had 10, and our file sizes were 3, 4 and 5.

Our array to start (blanks are false) - 11 blanks
[T][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
size[1] = 3
from 10 to 0 goes to 0 (the only T element), checks to see if 0 + 3 < 10
It is, so now we have:
[T][ ][ ][T][ ][ ][ ][ ][ ][ ][ ]
The farthest right T represents the most space we can use
Next size[2]=4
Iterating, we figure out the combinations with this.
Either 0 + 4 or 3 + 4 are valid, so we end up with (setting 4 and 7 to true)
[T][ ][ ][T][T][ ][ ][T][ ][ ][ ]
next size[3]=5
7 + 5 is invalid (because it's >10), but 4 + 5 and 3 + 5 are valid and so is 0 + 5
[T][ ][ ][T][T][T][ ][T][T][T][ ]

Now we have an array representing all of the possible file sizes that can be created as a combination of the files. This means that 9 is the most space we can use, but also note that this means it's impossible to create a disk that uses size 1, 2, 6 or 10.