Pancakes Programming Contest
|Part I||Part II|
THE PANCAKES PROBLEM
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.
Part I of the contest is open only to those who tied for first place in the Squares Programming Contest.
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.
Part II is open to everyone.
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:|
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.
Entries are due by Noon (GMT) on the dates shown at the top of this page.
THE SCORING SYSTEM
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.
GETTING YOUR QUESTIONS ANSWERED
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 firstname.lastname@example.org.
THE DISCUSSION GROUP
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.
MY LAWYER WOULD WANT ME TO SAY THIS
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.
FREQUENTLY ASKED QUESTIONS
Can you give an example of a valid contest entry?
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:
4, 6, 2, 5, 1, 3
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:
2, 3, 4, 2, 6, 3, 2
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.
Can teams enter the contest?
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.
In Part II, how can I find out the subscores for my individual stacks?
You canít find out the subscores for your individual stacks.
Can I enter the contest more than once, using different names?
No, that's strictly prohibited.
Al Zimmermann's Programming Contests ó Pancakes Contest Standings
You are visitor to this site.