Austin2600 Codedown

Rules

There will be three problems of varying difficulty: an easy, medium, and hard problem.
Whoever solves the most difficult problem wins, if there is a tie, I will decide who's solution is the most elegant. Elegance will be judged on algorithm time complexity, algorithm space complexity, and algorithm design. Elegance will not be judged on the choice of language, program formatting, comments, or choice of identifiers. The number of problems solved or time taken is immaterial, only the most difficult correct problem submission is considered. If your most difficult problem submission is found to be incorrect, your next most difficult problem submission is considered.
Solutions are submitted by transferring them to the testing machine (which could be your own if my machine can't run your code) by any sane means.
You will have 2 hours to code your solutions. You may use any resources you bring to the competition including: computers, books, writing materials, performance enhancing drugs, etc. You may not use the Internet or communications with anyone else. Your solution must be your own work or some material you bring to the competition. No resource sharing is allowed, ie. you can't let another player borrow one of your books or your laptop during the coding phase.
You may use any programming language you like as long as there exists before the competition a compiler or interpreter that runs in a POSIX environment and takes input on standard in and produces output on standard out. The competition will go much faster if you don't try to fuck around on this rule. Using something like C or Java will make testing submissions very easy and we will find a winner by the time we goto Kerby (or whatever).
The correctness of a solution will be determined by testing. If you can provide a complete proof that your code is correct, please do, otherwise I'm just going to run test cases I or anyone else comes up with. After the coding phase you can look at everyone's code and help with the testing phase. There is no points awarded for challenges like in Top Coder (there aren't any points anyway).
All problem specifications will be written up by one person and shared with no one before the competition. This person will not be able to compete. Any clarifications to the problems can be discussed with this person (in private if you like) and a clarification will be presented to all competitors.
The competition will start when I say so and if you have any technical or biological problems during the coding phase, too bad. If you miss the start you can join late but you won't be given any extra time. There's probably going to be more than one of these so don't throw a fit.

Time and Place

If everything works out, we'll have a competition at the next meeting, if these rules change I'll try to let you know.

F.A.Q.

Q. Can I use any language I want?

A. As long as it has a compiler or interpreter for a POSIX environment.

Q. Can I use cshell?

A. Yes.

Q. Why can't I use the Internet? Most of my language refernece material is online!

A. Because it's possible that there are solutions to the problems published online already. Try downloading your reference material and bringing that. You should also use a language you know well enough that you don't need refernece material.

Q. When is it?

A. Friday! I'll start the competition around 8pm, but no later than 9.

Q. Are the problems given out at the meeting?

A. Yes. The problems are probably going to be distributed on paper to anyone wanting to compete.

Q. Can you borrow someone's laptop?

A. Only if it's in your posession during the entire competition. This would count as bringing it yourself, you just happened to have your friend carry it for you.

Q. Is it going to be at Spider House?

A. Yes, unless we already had that one and I haven't updated this page.

Q. Was this whole idea yours?

A. I came up with the format and the rules and I'm going to write the problems for this one.

Q. So is this a bragging rights competition?

A. I guess so. There's no material prizes.

Q. So what kind of questions are you asking?

A. Stuff that requires a program to read something from stdin and write something to stdout.

Q. Is it testing algorithm knowledge or testing coding times?

A. Time doesn't matter, as long as you do it within 2 hours. It's mostly algorithm knowledge, or extreme cleverness.

Q. Do we get an example question/problem?

A. Sure, why not?

Easy problem (recently changed):

Your program will read from stdin a space (0x20) delimited list of commands
terminated by a newline (0x0A) followed by a space delimited list of numbers on
which to operate. Your program will write to stdout the result of applying in
order the list of commands to the input. The commands are "L" and "R". The
numbers are decimal integers in the inclusive range 0 to 4294967295. The list of
numbers has a length of the form 2^N and there are no more than N commands in
the sequence. The "L" command removes every other number from the list starting
from the left and the "R" command removes every other number from the list
starting from the right. The output will be a space delimited list of decimal
integers.

Example 1:
R L
4 28 0 42

Output:
0

Example 2:
R R R
7 3 8 8 4 9 2 1 7 5 6 1 7 4 9 2

Output:
7 7

There is at least one very elegant solution to this problem with a time complexity in O(n) and a space complexity in O(1). This solution does not store any portion of the input list. It also begins producing output as soon as it reads in the first number that is in the result. These are all properties of an elegant solution. The naive approach of reading in both lists and applying the commands one at a time may not be good enough to win the competition. However, if you can write the naive one in 30 minutes then playing with that solution should give you a good idea what is actually going on and then write a more elegant solution in the remaining 90 minutes.