On day 1 we had (pebbling) odometer, (parachute) rings and (crayfish) scrivener.
Odometer was really weird. The most amazing thing is... Gennady didn't solve it!... that's right! Gennady didn't solve pebbling odometer!! Don't believe me? Well here's the IOI results. Still don't believe me? I don't believe it either. But on to the actual problem.
In odometer you were given a whole new programming language to control a robot in a grid. The grid consisted of a bunch of squares each with a number of pebbles in it. You had to do a number of tasks on the grid such as putting the robot in the middle square of two pebbles or putting the robot in the square with the minimum number of pebbles. The crazy thing is that since this is a whole knew programming language, you don't have memory! You don't have variables! All you know is where you are in your program. It's pretty crazy which is the only reason (I think) Gennady didn't solve it. Me, junkbot and goldy got the first two subtasks giving us 21 points while nic got subtasks 1 and 3 giving him 28 points.
The second problem was rings. You are given a bunch of rings which can be connected. We define a chain as one or more rings that forms a single non-cyclic path. We also define a critical ring to a be a ring which you can remove such that the remaining rings are chains, not necessarily all in one chain but a set of chains. You want to support two operations, connecting two rings and finding the number of critical rings. Basically, it was a whole bunch of icky and tripsy data structure foobar... that's all the detail I can go into in a blog. :/
Me and goldy got the first subtask giving us 20 while junkbot got 55.
The final problem was scrivener. You had to implement a machine which could type a character or undo the last x operations. The trick was that an undo counts as an operation in itself and undoing an undo would redo all the undone operations... yeah, tricky. [SPOILER] After a few observations, you realised that you could turn the operations into a tree and use logarithmic parent lookup, similar to that in lowest common ancestor algorithms. [/SPOILER] Me, nic and junkbot got 100 on this and goldy got 60.
