Darkness 1998-12-14 00:00:00 UTC
 
Twilight 1998-12-15 00:00:00 UTC
 
Daylight 1998-12-16 00:00:00 UTC
 
Finish 1998-12-21 00:00:00 UTC

Binpack - Rules

Arrow_down  Download Sample Code

The Challenge

You work for a large record company that markets a line of greatest hits compact discs --- "70's Super Funk", "Partridge Family Unlimited", "Three Tenors in Antarctica, Again!". For each CD, you have a list of possible songs, their lengths, and the CD's maximum length.

You would like each CD to be as close to full as possible, but you have a large catalog of CD's to fill, in anticipation of an 80's revival. It's okay to leave a bit of empty space on each CD to get the job done quickly. You have decided to use MATLAB to determine the set of songs for each CD.

Problem

You will be provided with a list, in vector form, of song times, and the length of a CD. Not all the songs will fit on the CD. Your job is to return a single vector of indices into that vector of the songs you have chosen for this CD.

The sum of the song times that you select should not be greater than the provided media length. You need not use all of the provided songs; there may be more songs than you have space for on a single CD. There were a lot of great disco songs, but you only want to produce a single disco CD.

In MATLAB syntax, the function header should look like this:

function indexList = binpack(songList, mediaLength)

More precisely, given a vector of arbitrary length, songList, find a vector of indices, indexList, such that

  • sum(songList(indexList)) <= mediaLength, and
  • gap = (mediaLength - sum(songList(indexList))) / mediaLength is minimized.
Example: 

If songList = [10.2 30 14 20.8], with a target time of mediaLength = 45, then a good solution is to pick the elements 30 and 14, since 30 + 14 = 44, which is very close to 45. Therefore, indexList = [2 3], since songList(indexList) = [30 14] and sum(songList(indexList)) = 44, leaving a gap of 1 minute on the CD. Not bad, but not optimal. The optimal solution indexList = [1 3 4] leaves a gap of 0. Either solution is valid.
 

Example Song Lists and Entries

Example songlists are available. Use mediaLength = 45 with these examples.

An example entry is also available. This function is listed in the rankings as the entry BINPACK EXAMPLE by contest@mathworks.com.

Judging Criteria

Note: you are not required to find the optimal solution!

There are two criteria for the judging of this contest:

  • the gap, time remaining at the end of the CD, i.e.
    gap =
    (mediaLength - sum(songList(indexList))) ---------------------------------------- mediaLength
  • the execution time of the algorithm.
Both the gap and the time should be as small as possible to minimize your score for each trial:

    score = gap * (time + alpha)

where alpha is 0.018 sec to increase the relative importance of the gap measure.  This ensures that a very fast, very stupid entry with zero time but with awful performance does not win.

We will run your algorithm through a suite of tests. We will measure CPU time and the gap for each test point, to score the entry for each test point. The winning entry is the one with the lowest average score over the test suite.

Note on Scoring:
Note that your score is the average of the scores for each individual test point. The time and blank space displayed on the contest rankings are the average time and average blank space ratings over all the test points. They are listed to give you an idea of how your entry performed, but they are not the numbers used to compute your score. It may be that the highest ranking entry does not have the lowest average time or lowest average performance rating, since in general,

     score = mean(gap_i*time_i)
         != mean(gap_i)*mean(time_i).

Your only strict requirements are:

  1. Each song may be used zero or one times in the play list.
  2. Do not exceed the target time mediaLength.
  3. Return valid answers for the test suite in 90 seconds or less.
  4. The entry must run without error in MATLAB version 5.2. Other toolbox functions will not be available.
  5. Some standard MATLAB functions have also been disabled for this contest. See the fine print below for details.

Deadline

The contest will end on Friday, December 18, 1998. The contest will close to new submissions at 5:00 PM EST (22:00 GMT). The winner of the contest overall will be determined after all entries remaining in the queue have been processed. Winners will be announced and contacted by e-mail no later than Wednesday, December 23, 1998.

Editing Existing Entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and modify any entries in the queue. The contest server maintains a history for each modified entry. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

Prizes

The final author of the winning entry will receive a CD of the greatest hits of the 70's and a MATLAB denim shirt. To encourage collaboration, the judges will acknowledge every significant contributor to the winning entry.

Winning entries must be original or must be substantial improvements on other entries. The contest administrators reserve the right to disqualify trivial changes.

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against MATLAB version 5.2.

Tip: You can use the which function to check whether a function you would like to use is part of a toolbox or part of the standard MATLAB distribution.

The following are prohibited:

  • MEX-files
  • eval, feval, etc.
  • Shell escape such as !, dos, unix
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, and flops

For More Information

Please send any comments or questions to the MATLAB Programming Contest.

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

  • Darkness - You can't see the code or scores for any of the entries.
  • Twilight - You can see scores but no code.
  • Daylight - You can see scores and code for all entries.
  • Finish - Contest end time.