Al Zimmermann's Pancakes Programming Contest

Part I

Part II

First Prize:		$250
Second Prize:		$50
Begins:		31 January, 2004
Ends:		21 February, 2004

First Prize:		$250
Second Prize:		$50
Begins:		22 February, 2004
Ends:		22 May, 2004

Consider a stack of pancakes, each of which has a different diameter. As the breakfast cook for the Prefix Reversal Diner, your job is to sort them so that the largest pancake is at the bottom of the stack and the smallest at the top. The only operation you can perform on the stack is to insert your spatula into the stack and flip over (that is, reverse the order of) the top portion of the stack.

For example, suppose the stack contains (from top to bottom) pancakes of diameters 4, 6, 2, 5, 1 and 3. Here's what the stack might look like when viewed from the side:

You can use your spatula to flip the top 2 pancakes so that the diameters are in sequence 6, 4, 2, 5, 1, 3:

And you can finish the job of sorting the stack with 6 more flips (of 3, 4, 2, 6, 3 and 2 pancakes):

So, in this example, you used a total of seven flips to sort the stack. You get paid for each stack of pancakes you sort, so you want to be able to sort each stack with as few flips as possible. The pancake problem is to determine the shortest sequence of flips which will sort a given stack.

The Contest is in two parts. The entries to Part I determine the problems that must be solved in Part II.

Not all stacks of pancakes are equally difficult to sort. Submit a stack of 100 pancakes (with diameters 1 through 100) which you think requires a lot of flips to sort. I'll include your stack among those to be sorted in Part II of the contest. If yours is the stack that takes the most flips to sort in Part II, you win Part I.

First prize for Part I is $250. Second prize is $50. In case of a tie, the earlier entry wins.

I'll provide you with several stacks of pancakes to be sorted. All but five of the stacks will come from Part I of the contest. The other five stacks will be random arrangements of the 100 pancakes. For each stack, submit as short a sequence of flips as possible to sort it. I'll compute a score for you (see below). The highest score wins.

The stacks to be sorted will appear on the Standings page beginning on February 22.

First prize for Part II is $250. Second prize is $50. In case of a tie, the entrant who reached the tied score first wins.

HOW TO ENTER

To enter either part of the contest, use the Automated Contest Administrator (ACA). You'll find links there that enable you to:
	register for the contest, submit entries to the contest, and view the standings page.

You'll need to register in order to submit entries, but not to view the standings.

If you are eligible to enter Part I, you may enter Part I as often as you like. The ACA will retain only your latest entry.

You may enter Part II as often as you like. For each stack to be sorted, the ACA will retain only your best entry.

Part I will not be scored until Part II has begun. Once Part II begins, each entry submitted in Part I will receive a difficulty score. The score will be the smallest number of flips with which any entrant in Part II has been able to sort it. The highest difficulty score wins.

The scores for Part I will change as Part II progresses. As this happens, the changing rankings will be available but not the scores themselves. I will post the scores for Part I after Part II ends.

First, I determine which are the 25 most difficult stacks to sort. I use the Part I difficulty score, above, to do this. For the remainder of the Part II scoring algorithm I use only these 25 stacks. Entries which sort any of the other stacks do not contribute to your score.

I give each entrant a subscore for each of the 25 stacks. These subscores are values from 0 to 1. The sum of your 25 subscores is your contest score. The highest contest score is the winner.

Here's how I compute your subscore for a given stack. If your sequence of flips is the shortest sequence that was submitted for that stack, it gets 1 point; otherwise it gets only a fraction of a point. The fraction is the length of the shortest sequence of flips submitted for that stack, divided by the length of your sequence for that stack. For example, consider stack A. Suppose that the shortest sort anyone has submitted for stack A uses 28 flips. And suppose your own sort uses 40 flips. Then your subscore for stack A is 28 / 40 = 0.7.

First, check the FAQ section below. If you can't find the information you need there, send your question to the discussion group. If your question is of a personal nature, you can send email directly to alzimmerma@aol.com.

If you think you might enter the contest, it is important that you join the contest discussion group. You can join either by sending a blank email to this address or by clicking here. The discussion group serves two purposes. First, it allows people to ask for clarifications to the rules. Be aware that sometimes these requests result in changes to the rules, and the only place those changes are announced is in the discussion group. Second, the discussion group allows contestants to interact with each other regarding programming techniques, results and anything else relevant to the contest.

I reserve the right to discontinue the contest at any time. I reserve the right to disqualify any entry or entrant for any reason that suits me. I reserve the right to interpret the rules as I see fit. I reserve the right to change the contest rules in mid-contest. In all matters contest-related, my word is final.

When you follow the appropriate link at the Automated Contest Administrator site, you'll find a box into which you can type or paste your entry. The link is easy to recognize -- it's called "Submit An Entry" -- but for the link to appear you first have to Register and then Log In.

For Part I, your entry is a comma-delimited list of pancake diameters. For example, if you wanted to enter the 6-pancake stack that appears at the top of this page you would just put the following text into the box:

For Part II, your entry is a comma-delimited list of the number of pancakes in each flip. So, if you wanted to enter the 7-flip sequence used to sort the stack at the top of this page, you'd enter:

Do I have to submit a sequence of flips for every pancake stack? There might be as many as 72 of them and you're only going to use 25 of them to compute my score.

No, you don't need to sort every stack. If there are any stacks in the "top 25" that you haven't sorted, I'll assume that you can sort them in 200 flips each.

What if there is a tie for the 25th most difficult stack? How will you choose which 25 stacks to base the scoring for Part II on?

If there's a tie for the 25th most difficult stack, I'll use more then 25 stacks and then "normalize" the scores. For example, if there's a 4-way tie for the 24th most difficult stack I'll use the top 27 stacks and then multiply the resulting scores by 25/27.

I’m going to join the contest discussion group. Are there any topics that are prohibited there?

Naturally, postings should pertain to the contest. But there are a couple of additional restrictions. First, you can’t post solutions (that is, specific sequences of flips that sort one of the contest's pancake stacks). If you want to tell everyone how few flips it takes you to sort stack X, go right ahead – just don’t show them the sequence itself. Second, you can’t post computer programs. These restrictions are lifted after the contest ends.

Yes, but with some restrictions. Once a team submits an entry, it cannot add or delete names from its membership. Also, a person can't be on more than one team. In interpreting this rule, individual entrants are considered teams of one. This means that once you submit an entry as an individual, you cannot subsequently join a multi-person team. And once you are part of a multi-person team, you can't split off and submit individual entries.