----------------------------------- MysticVegeta Tue Feb 21, 2006 8:55 pm DWITE Feb 21, Problem 2 ----------------------------------- 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 0 then size += files (j + 1) end if end for if size 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 Wed Feb 22, 2006 11:08 pm ----------------------------------- 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 Wed Feb 22, 2006 11:15 pm ----------------------------------- how about giving me 100 bits? I think I deserved it ;) ----------------------------------- Martin Thu Feb 23, 2006 1:25 am ----------------------------------- 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 Thu Feb 23, 2006 2:03 am ----------------------------------- 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 Thu Feb 23, 2006 10:18 am ----------------------------------- 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 Thu Feb 23, 2006 8:13 pm ----------------------------------- 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 Sat Feb 25, 2006 12:16 pm ----------------------------------- 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. 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 Sat Feb 25, 2006 8:46 pm ----------------------------------- K is at most 50. So this is greedy (try K = 1, 2, ..., 50)... and greedily take the longest word... ----------------------------------- MysticVegeta Sat Feb 25, 2006 10:01 pm ----------------------------------- Is greedy a hard concept to grasp? cause I dotn wanna be wasting time on learning it not knowing it is too much a wide concept for my puny little brain. ----------------------------------- bugzpodder Sun Feb 26, 2006 8:29 am ----------------------------------- Not at all. let me do an example. In a class Miss Thompson offered you and other people in your class candies. What you do in a greedy situation istake all the candies and not share it with any of your classmates. ----------------------------------- MysticVegeta Sun Feb 26, 2006 12:00 pm ----------------------------------- Greedy is mean but helpful :D But what exactly "is" to take all in that problem? Also, does it require knowing a prerequiste concept of something? ----------------------------------- bugzpodder Sun Feb 26, 2006 6:07 pm ----------------------------------- Fix a width, say w. Basically you are to determine if u can break the setence up with at most K spaces such that each line has width w or less. So u keep on taking words (greedily) until the next word would exceed the width, and break the line. count how many breaks you've used to ensure it doesnt exceed K. Finally do that for all possible width and take the least one (start from the smallest, the first width you find would be the answer). ----------------------------------- MysticVegeta Mon Feb 27, 2006 2:32 pm ----------------------------------- ok, I am gonna go find some tuts on greedy. ----------------------------------- Martin Mon Feb 27, 2006 7:46 pm ----------------------------------- This is one of those cases where you have to realize what information is and isn't important. We need to know the length of the words, but not the actual words. Also, we know that there are no double spaces between words, so we can safely load it all into an array of ints representing the length of each word (if we have n ints, then there are n - 1 spaces). Now, we set numLines = max (K, n-1), because we obviously can't split more spaces than we have (for example, a sentence 'hello world' with K = 5 is valid, but we can really only make 1 split). So now we have a list of numbers. Keeping in mind that a space represents a single character (so the line 'Hello World' is length 5 + 1 + 5 = 11), we now are going to generate the possible lengths of each line. So let's say that our word lengths are 7 5 2 11 3 5 and K = 2 (meaning we will have 3 lines). Now we just try all logical combinations (ie. 7 + 1 + 5 is a valid line length, but 7 + 1 + 2 is not), remembering to add 1 for spaces in a line, and you're in business. ----------------------------------- mckhatri1 Wed Jul 05, 2006 8:36 am ----------------------------------- It's like this. We know that worst case, we can't fit anything onto the disk. So that's our base case ... d How do you know how many array spaces to start with? ----------------------------------- MysticVegeta Sat Jul 08, 2006 11:49 am ----------------------------------- well you know you have to reach the sum closest 1440. so the array length would be 1441. Since dp[0] would always be true so that it can used as a previous state meaning the previous reached sum. Kinds hard to explain but you would get it if you read the entire post by him