Minesweeper incident

Yet another 8:30 start today. Though this time, it was a little more like a 8:45 start since Bernard realised getting to the UNSW labs in time before shovelling down breakfast was less than possible. Instead of the somewhat oversized "Big Brekkie", I thought it would be a good idea to scale down breakfast for today and see how a "Spot Brekkie Roll" was, especially after Evgeny couldn't finish his, being unable to take the Tabasco sauce (which I saw as a challenge).

[I just remembered that we're not meant to be making exhaustively longs posts, so I'll try to keep everything down to a paragraph per notable 5 hour time period]

As scheduled, yet another practice exam today which I found (and I assume everyone else found) significantly more challenging than yesterday's exam. As usual, the first task was reasonably straightforward and was full feedback (meaning we would know whether or not our solutions were correct and sufficiently efficient upon submission). That being said, it was the only problem of the four that anyone completed (which we all did). The final 3 problems took me around 4 hours of good, hard staring to realise that I wasn't going to complete any. At best, I submitted more brute force solutions (which would take a few billion times longer to run than our time limit), resulting in a score far to shameful to disclose. By the time the exam had ended, we all sat quietly at our keyboards for a couple minutes in shame, reflecting upon the sheer shock of the previous 5 hours. When we had finally gathered ourselves together, we went to lunch to relieve ourselves of the pent up stress that we had garnered.

Fish and chips with salad. A good meal. All of us (with the exception of Jarrah) had sat down at a table to eat and talk casually about the problems before our problem session. When everyone had finished eating, Bernard suggested we take advantage of the conversational momentum and have the problem session at the table (also avoiding using up energy walking back to the labs from the food court). So we stayed sitting and begun sifting through the tasks. After entirely skipping the first task (the easiest), we went onto discussing the second task, BEARs. We all had something to say about it, having come up with various ideas that may have contributed to a proper solutions. Of all the ideas that popped up, one seemed to have significant importance so we pursued it, diving into deeper and more complicated algorithms. After nearly half an hour of confused discussion, Bernard gave a hint that allowed us to put ourselves out of our misery and finally arrive at a proper (and elegant) solution. The next problem that we looked at was Candies, which I found comparatively less approachable than BEARs. As I saw it, the problem could be broken into two parts, the second of which I had largely solved. The first part had me completely lost which was what ultimately let me down. After some hand-wavy discussion, we came up with an algorithm that would work correctly and in time for the second subtask, but would only be useful with the assumption that we had already solved the first subtask. During our discussion of Candies, Luke brought up a brilliant insight regarding the first of the two sub-problems. Unfortunately there were some aspects that needed to be fleshed out which made things very much more complicated. Again, as with BEARs, we begun to dive deep into the algorithmic possibilities for solutions to the first subtask, Evgeny describing his solution to it in depth. Midway through his explanation, I felt sufficiently convinced that it was correct, but Bernard was much more critical of it's correctness, again giving us a light push towards the official solution. As usual, the algorithm which we ended up at was amazing and appeared to be so obvious and make so much sense, but unfortunately doing so many hours after the exam.

Off to the labs to have a stab at implementing the solutions to the problems which we had spent the previous 4 or 5 hours discussing. In the end, I was able to submit a complete solution to BEARs, as well as the final task from yesterday's practice paper. During the problem session, Bernard had mentioned something about the final problem (which I failed to mention in the previous paragraph). Summed up, the task was to produce a valid placements of mines in Minesweeper such that the configuration would fit a pattern of numbers describing the number of mines around each cell. The thing that Bernard had mentioned was in regards to the feasibility of the problem with relation to the size of the grid. Apparently, if at least one side length was not equal to 2 modulo 3, then it was computationally possible to efficiently produce a layout of mines that would fit the given grid (assuming such a layout exists). Luke and I searched around for the solution, finally coming across some observations that made today's final problem, Mines, the single most awesome task that I have seen during this training week (awesome enough for me to name this post after it). I would talk far more about the problem and the sheer awesomeness of the solution, but it's probably in my best interest to keep this post only as long as necessary *cough*.

Dinner was pizza. It's nice to have pizza from a place that isn't Pizza Hut or Dominoes. During dinner, the team and our leaders discussed the layout of the coming IOI, including the advantages and disadvantages of various changes that have been made (such as the idea of "release tokens" and the modified forms of submission that have been put in place). Interesting moral debate regarding the informatics spirit ensued.

As of a little over half an hour ago Luke left the room and as of a little a few minutes ago, Robert left too. I must say that it feels terribly unsatisfying to write up such a relatively short blog post after my original plan to write posts of exponentially increasing size (which would have had this post hovering around the 4000 word mark), but it's probably in the best interests of all (particularly myself, having lost a fair few hours of sleep typing away at my netbook). I have a bizarre feeling that there's going to be something crazy like an A-session tomorrow (which is like a normal informatics exam but without the computer, and with the use of more paper and more rigorous proofs). Chances are that I'll be entirely incorrect, but that's my guess.

Until next time

-ken