Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 DWITE Feb 21, Problem 2
Index -> CompSci.ca, Contests -> DWITE
Goto page Previous  1, 2
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
MysticVegeta




PostPosted: Sat Feb 25, 2006 10:01 pm   Post subject: (No subject)

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.
Sponsor
Sponsor
Sponsor
sponsor
bugzpodder




PostPosted: Sun Feb 26, 2006 8:29 am   Post subject: (No subject)

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




PostPosted: Sun Feb 26, 2006 12:00 pm   Post subject: (No subject)

Greedy is mean but helpful Very Happy But what exactly "is" to take all in that problem?

Also, does it require knowing a prerequiste concept of something?
bugzpodder




PostPosted: Sun Feb 26, 2006 6:07 pm   Post subject: (No subject)

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




PostPosted: Mon Feb 27, 2006 2:32 pm   Post subject: (No subject)

ok, I am gonna go find some tuts on greedy.
Martin




PostPosted: Mon Feb 27, 2006 7:46 pm   Post subject: (No subject)

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




PostPosted: Wed Jul 05, 2006 8:36 am   Post subject: (No subject)

Martin wrote:
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.


How do you know how many array spaces to start with?
MysticVegeta




PostPosted: Sat Jul 08, 2006 11:49 am   Post subject: (No subject)

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
Sponsor
Sponsor
Sponsor
sponsor
Display posts from previous:   
   Index -> CompSci.ca, Contests -> DWITE
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 2  [ 23 Posts ]
Goto page Previous  1, 2
Jump to:   


Style:  
Search: