Saturday, October 18, 2008

Dini Programming, Fall '08

This is what I spent the whole of to-day on.

Roughly thirty people entered the room. After registering and helping ourselves to soda nearby, we placed ourselves before an assigned computer and prepared our IDE of choice. (I used Eclipse, it being the most modern of the tools available to us.) I spoke to some lovely people sitting near me, including a fellow freshman, David, who was wearing Gavin's 802.11 shirt. (He had it off most of the time, to save battery power.)

Eventually, they gave us a practice problem: "fermat", in which we were given some positive number 'n' and were to return whether or not there was some equation "a^n+b^n=c^n", where a, b, and c were all real integers. (The algorithm was surprisingly simple.) I actually didn't complete it in time; I had decided to use C++, with which I had all of four weeks experience. Switching over to Java midway left me with too little time; still, my neighbors (notably the chap just to my left, whose name I forget) helped me finish it, which would prove essential to the rest of the contest.

Also, between the completion of the practice problem and the contest itself, the organizers announced that ACS had scheduled all of the computers in the lab to reboot into Windows in an hour. (They were running Linux, as any proper computer will.) To forestall their restarting while we were hard at work, we contestants were forced to reboot them prematurely. It was... very silly.

The contest proper lasted six hours, from just after 12:30 to just after 6:30. There were seven problems, all of which used essentially the same input structure: we were given a series of lines of input through stdin, the first of which would tell us how many test cases we were to evaluate. Then, for each test case, there would be a line of metadata, and then individual points of data on all succeeding lines until the end of the case. For instance, input for a "dominoes" problem (finding the minimum number of dominoes that needed to be shoved to knock them all over) might read:
4 3
1 2
2 3
3 4

Indicating that there was one test case, within which there were four dominoes and three lines describing their interactions. Domino 1 knocked over 2, 2 knocked over 3, and 3 knocked over 4; that one required only 1 push.

I can describe that problem in so much detail because I spent half the time - three hours - working on it alone. And I still didn't get it.

There were many other problems, though. There were easy problems, like a problem calculating the distance traveled by a logo turtle or another problem so easy that literally everyone got it, and so easy that I can't remember anything about the problem itself. (Tragically, those two were the only ones I got. Ah well! I hardly alone in that.) Most of the problems were harder, such as the aforementioned domino problem, or a "construction crane" problem finding the maximum non-overlapping area covered by a set of circles of varying radius and position, or one finding the size of social networks; these less than half of the class got. The two last problems were hardest of all. The first, which just two people got, involved a street with some number of houses placed at varying distances along it; with some number of "wi-fi access points", you were supposed to minimize the maximum distance of any house from the closest wi-fi point, and then report that maximum distance. Very odd.

The last problem involved a rocket with one to one-thousand stages, each stage having a varying mass, thrust, fuel mass, and fuel consumption rate; one was supposed to find the final speed of the rocket after it had expended the totality of its thrust. The solution, as noted in the problem description, involved integrals.*

No-one got that one.

The most any student got was 5 problems; the David mentioned earlier was one of the three who got that many. (One of the organizers managed to solve six of them. Not the rocket one, though!) The cut-off for placing, and therefore getting cash prizes, was solving three problems. I did not make it. (One of my friends did. I was a bit jealous.)

Was I sad?


I was - and am - FLUSHED WITH TRIUMPH!

Just for the joy of competition? The thrill of battle - a battle of wits, the noblest sort?


I snagged loot! Treasure threefold:
- Soda! A can of Sprite and of root beer, left-over from the competition. We were urged to take the remainders so that the organizers would not need to throw them out; I did so with glee.
- Some kind of snack! I'm not really sure what it was. But it was unopened and I knew that my suitemates would appreciate a contribution to the communal pantry (we actually have a communal pantry. It's in the wall, and filled mostly with junk food), so I took it anyway. Looked like this.
- And - most glorious of all - won by random chance - a $100 gift card for mysterious home of food-related items, "Ralph('s)"!

So I'm pleased as punch.

Hooray for non-League related, rambling, slightly boring posts!

EDIT: This link may be informative.


mr sex said...

truly, you are the god of the modern computing world

also that was so cool


i was there too, i solved all 8 problomes

Cavalcadeofcats said...

Amazing! You are the king of the gods of the modern computing world!