Negg Hunt '11 Scheduling and Supply Solutions
High-Scores | Solutions | Portals | Memorable Comments
Scheduling Content Puzzle | Supplies in a Bag Puzzle
It's nice that there are solutions for these particular problems, but wouldn't it be nicer to know how to find a solution to any problem like this one? We're going to tell you the secret now. First, take all the articles and make a list sorted by end date. This means the article with the earliest end date comes first. For any article on your list, the one that comes after it either needs to have the same end date or a later end date. This of course means the last article on your list has the latest end date. Okay, so the articles are now sorted. How does that possibly help? Certainly taking the first bunch of articles or last bunch of articles isn't a good solution. In fact, unless all the articles are short, doing that after sorting makes it more likely that two articles overlap.
Here's some simple facts we know:
- If there were no articles to schedule, the best word count would be 0.
- If there was only one article, the best word count would just be the word count for that article.
- Each article is either in the solution, or it isn't.
- If we pick an article with start date 5/AA and end date 5/BB, any article earlier on our list that we pick must have an end date of at latest 5/AA. Remember that these dates are Month/Day.
These facts are all we need in order to put together an easy solution. All you need is a place to keep a bit of work - word processor, pen and paper, spreadsheet software - whatever works for you.
- Number your sorted list, giving #1 to the article with the earliest ending, #2 to the article with the next earliest ending, and so on. This helps so in the chart we're about to make we don't have to keep writing article names. This step is optional.
- Make sure on your list to leave extra space next to each article - you will need it as "scratch space" to show the best word count using only that article and the articles higher up on your list.
- In the space for #1, fill in the word count of article #1 since as observed before, if we only have one article, it will always be better to take it.
- Starting with article #2 and going all the way up to the last article, fill in each space in the following manner:
Let's call the article we're currently considering Article #C (C for current). Find the latest ending article you could take if you did take the article you're currently considering. We'll call that Article #P (P for previous). Figure out if the row for #P added to the word count for article #C is bigger than the row for article #(P-1). Whichever of the two numbers is bigger, write down for article #C.
- The best word count is the number in the row for the article that's last on your list, since that row shows what the best word count is when you consider ALL of the articles.
- To get which articles we actually used, we just need to keep track of how we got each number. If we got a number by choosing #C's word count and the number from row #P, that means our solution uses article #C, and it uses whichever articles we used to get the number for row #P. If we used the number from row #(P-1), it means the article we're looking at wasn't used, and the solution just uses whichever articles were used to get the number for row #(P-1).
In case you're a bit confused, or just curious to see this in action, you can click here for a step by step example. As a final note, to make the addition easier if you know what GCD (greatest common denominator) means you could have found the GCD for a content writer's potential articles and divided everything by it to get numbers more like 1-15 instead of 400-4200.