Australian Maths Trust

Phones down, thumbs up

This blog post accounts for the highlights of the Australian IOI team’s second day of training at the pre-departure camp at UNSW Sydney, as told by Angus Ritossa. Angus is the veteran of this year’s team, and will be competing at his third IOI this year, having won a silver medal last year.

I was unable to come up with a good way to start this blog post, and upon asking for assistance Tunan suggested I begin it with “well, well, well”*. So well, well, well, here we go. Like yesterday, the writer of the blog post was decided by a game over dinner. Today’s game was based on an Informatics problem as old as much of the team – “Polygon Game” from the selection contest that decided the Australian IOI Team who went to Korea in 2002.

The problem goes like this. You’re given a convex polygon with n vertices (for example, a regular hexagon would have n = 6). Each vertex has a positive number written on it. You would like to draw diagonals connecting these vertices, so that no two diagonals intersect. Your score is the sum, for each diagonal, of the product of its two endpoints. Your goal is to obtain the largest score that you can! [Ed. the challenge to algorithmically-inclined readers is to solve this problem in polynomial time!]

An example from the archives: a score of 56 + 48 + 24 = 128!

This time, however, we weren’t able to write a computer program to solve it. Instead, we had two minutes to solve one case by hand. [Ed. The students have an elaborate “phones down” protocol to ensure synchrony and fairness. Phones and hands are placed on the table, while the case is posted in the group chat. They then pick up their phones, and have to write or draw their solution on their phones, before “phones down” when time is up. We shall try to obtain a video of future iterations.]

Camaraderie temporarily laid aside; the competition is intense!

Unfortunately, I missed the easy solution [Ed. the editor who may or may not be the Team Leader also failed in an identical manner] and after conceding defeat, began the task of writing this blog.

Hastily drawn solutions… from least (L) to most (R) optimal!

Today was the rest day between the two CEOI days, our rest being a different 5-hour exam. The exam itself had some good problems, although I had a bit of a fright towards the end when one of my solutions was rejudged with not long left to go, losing 45 points. After spending time frantically trying to improve my code, I discovered that my solution had been re-rejudged and I had gained back the lost points, much to my confusion.

The team engaging in “upsolving” — coding up and solving the problems they didn’t solve during the actual contest. Or as the author prefers to call it, “up” and “solving”.

After the exam, we decided to play a bipartite graph version of frisbee, before switching to the even easier cycle graph version, a phenomena Kevin likened to solving subtasks [Ed. easier versions of IOI tasks that accrue a fraction of the 100 points on offer] on a problem. I don’t think we got that many points.

One “part” of the bipartite graph receiving the disc

On another note, my dearest comrade Tunan (which autocorrect keeps wanting to change to tuna) would like to add that the grammar in his blog post was incorrectly edited without his consultation, with the word “me” being erroneously replaced with I. What’s the chance that the editor chooses to silence th-[Ed. REDACTED]?

*Actually, his first suggestion was “Yo its ya boy pony_joe1 back with another Minecraft video” [Ed. pony_joe1 is the author’s handle] but I chose to go with his second one…