My performance at the Student Battle Dev Season 11

by Noah Ó Donnaile

I had a lot of fun yesterday evening competing in the 11th edition of the #battledev competition. I hadn't taken part before, but decided it might be worth checking out what competitions happen beyond Ireland's shores, and a French friend recommended this one.

The competition is French, but it allows anyone from an EEC country to compete. It lasts two hours, and consists of six questions. You must solve the first question before you can see the second question, and so on. The winner is the first person to solve the last question, then the second person to solve it, and so on for everyone who solved the last question, followed by the first person to solve the second last question, etc.

The first 3 questions were in miscellaneous topics, but were all reasonably easy.

  • Problem allyoucaneat required adding given %-discounts to orders of given sizes, and outputting the final sum of transactions.
  • tripadvisor involved finding the location from the input with the highest average rating, based on its rating in three subcategories, and outputting this average.
  • Then rocky13 asked you to find your k friends who's ratings for previous films most closely matched your own rating (by sorting by their minimum total difference in ratings), and output the average of their ratings for a new film.

I did quite well at these.

Then came pancakes, which was a Towers-of-Hanoi-like problem. The inputs were small enough to brute force the optimal solution with a tiny bit of tree-pruning.

Problem #5 was tramways12, and it was much more difficult. The input described a circle of vertices 0 to N-1, and a matrix of the number of people who wanted to get from each vertex to each other vertex. You were asked to output the maximal possible number of people you could take by building edges between nodes, with the following caveats:

  • Each vertex can only touch at most one edge.
  • No edge connecting vertices A and B can intersect the edge connecting vertices C, and D. The input essentially described a regular N-gon, and you could not draw lines between corners of the N-gon that would intersect.

The solution needed to be O(N^3).

I realised you could use dynamic programming. The optimal arrangement of edges within the bounds of vertices [A, B] was independent of the arrangements of edges at vertices outside of this range. However, I found that the implementation of this dynamic programming was easier said than done.

I tried many non-working solutions, that missed edge cases, or that accidentally didn't try some arrangement of vertices, but in the last minute of the competition, I uploaded my final solution. It evaluated... and evaluated...

Seeing as the submission system was flaky (and went offline a few times during the contest, under heavy load), I re-submitted.

Around the final second of the contest, it finished evaluating, and told me my solution was correct.

Although I emailed the judges to enquire about this, in the end it seems they decided my solution didn't count. Oh well! It was an exciting end to the competition.

While I didn't get to see it during the competition, afterwards I read ducks7, the sixth and final problem, which appeared to be some form of duck-themed max-flow.

The following day (today), they released the results, in a blog post, and via email.

Bonjour,

Merci d'avoir participé à la Battle Dev.  
Les résultats définitifs de la saison 11 sont désormais connus.

Vous êtes 41eme sur 3322 au classement général.

There were 3322 competitors, of whom 2385 solved at least one problem. Out of that, I came 41st! I'm delighted. Had my final submission been accepted, I would have jumped up to 29th place, but as they say, c'est la vie.

However, it was pointed out in the blog post, that Dublin City University was ranked as the #2 university in the competition! I guess many of the people above me in the rankings were not representing a university.

All in all, it was a fun competition, a little different to most I take part in. I was expecting to need to translate problems from French, but in the end they provided links to PDFs in English.

It seems bizarre to see DCU ranked highly in a French competition; I have saved the screenshot for future laughs. Let's see if we reach #1 next time!