«

My performance at the Student Battle Dev Season 11

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.

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:

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!

Share Comment on Twitter