DWITE Feb 21, Problem 2

[MysticVegeta]

Quote:

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.

I know this uses DP, I read tuts on dp around a month ago but I cant seem to code this one, I know it uses beginner level DP but incase if you haven't seen my posts, I am one of them

Anyways, DP help will be appreciated.
Please do not tell me to make combos using nested for loops in while loops as I know I can code it using that but it takes time making all possible combos.
Thanks.

[zylum]

here's a program which uses brute force but its not fast enough. it can only handle up to 17 files but the limit is 25... this means that input with 25 files will run 2^8 times longer.

code:

var ifile, ofile : int open : ifile, "DATA21.txt", get open : ofile, "OUT21.txt", put var N, size, maxsize : nat for : 1 .. 5     get : ifile, N     var files : array 1 .. N of int     for i : 1 .. N         get : ifile, files (i)     end for     maxsize := 0     for i : 0 .. 2 ** N - 1         size := 0         for j : 0 .. N - 1             if ((1 shl j) & i) > 0 then                 size += files (j + 1)             end if         end for         if size <= 1440 then             maxsize := max (maxsize, size)         end if     end for     put : ofile, 1440 - maxsize end for close (ifile) close (ofile)

[MysticVegeta]

Sadly it doesnt execute in time with 25 inputs. But I need the DP solution.. brute force is good but in a limit.

[bugzpodder]

The trick here is to realize that what goes on the disk doesn't matter, as long as each file is used at most once.

code:

dp [0] = true; for i:1..nfiles   for decreasing j:1440..0     if dp[j] = true and j+size[i] <=1440 then       dp[j+size[i]]=true     end if   end for end for

[MysticVegeta]

But I dont undersatnd, will it like this? the elements set to true in the dp arrays sum be the max possible under 1440? or will it be the elements set to false in the dp array?

[bugzpodder]

this generates all subset sums of the files under 1440.

[Martin]

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.

[MysticVegeta]

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

[bugzpodder]

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

[Martin]

bugzpodder wrote:

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

Alright, I'll give you 100 bits. I remember you taught me about dynamic programming in grade 11 (I think it was grade 11) with the golf club question.

[Martin]

MysticVegeta wrote:

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

All DP is is induction.

We can solve it for N = 0, and N = 1 isn't that hard (where N = number of files)

For N = 2, we just add to our solution for N = 1. And so on. It takes a bit to wrap your head around, but it's not difficult.

[MysticVegeta]

Martin wrote:

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

Tell me about it. I tried to get the tuts so badly but got them just a little so I was able to do question just exactly like the tuts! The first one I read was about a month ago on TC, when I came across a question from SRM 286 I think. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Edit: Is doing this boolean way more efficient/faster than the using a best variable?

[Martin]

Yes, and using a 'best' variable won't work most of the time.

For the above example (with 10) suppose the numbers were 7, 5 and 4.

You put 7 in. Best is now 7. You try to put 5 in. It doesn't go in, because it's less than 7 and 5+7 > 10.

Same problem with 4... 4 + 7 > 10. So you get a solution of 7, but the right answer is 5+4 = 9.

It's easy to find out what the best is after the fact (just go backwards through the array).

[MysticVegeta]

yeah setting an array true/false is great idea. and going backwards is fairly easy. There are some questions with strings that involve dp too and they are pretty hard like this one, it was used for SRM 285 DIV 2 lvl 2/DIV 1 lvl 1.

Quote:

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

[bugzpodder]

K is at most 50. So this is greedy (try K = 1, 2, ..., 50)... and greedily take the longest word...