ACM ICPC World Finals 2019
Disclaimer This is an unofficial analysis of some possible ways to solve the problems of the ACM ICPC World Finals 2019. They are not intended to give a complete solution, but rather to outline some approach that can be used to solve the problem. If some of the terminology or algorithms mentioned below are not familiar to you, your favorite search engine should be able to help. If you find an error, please send an e-mail to austrin@kth.se about it.
— Per Austrin, Bruce Merry, and Jakub Onufry Wojtaszczyk
| A | Azulejos |
| B | Beautiful Bridges |
| C | Checks Post Facto |
| D | Circular DNA |
| E | Dead-End Detector |
| F | Directing Rainfall |
| G | First of Her Name |
| H | Hobson’s Trains |
| I | Karel the Robot |
| J | Miniature Golf |
| K | Traffic Blights |
The contest started out with the University of Warsaw making an amazing start, at one point being in the lead with 5 problems solved while the team in second place still only had 2 problems solved. But after solving seven problems in the first two hours, they slowed down, and ultimately ended up with 8 solved in 4th place.
The last hour of the contest was very exciting in the judge’s room (and for careful viewers of ICPC Live as well), with MIT and Moscow State battling for the first place: 3 minutes into the last hour, MIT took the lead by solving K in the first attempt, but a few minutes later Moscow State solved both I and K in quick succession, putting them ahead by one problem. However their penalty time was pretty high due to several incorrect attempts on K, so MIT had a window of 30 minutes to solve another problem and take the lead. With just 30 seconds remaining of that window, they submitted a correct submission on I and regained first place, with the same number of problems solved and a single penalty minute less than Moscow. However, their lead was short-lived: just a minute later, 21 minutes before the end of the contest, Moscow submitted a correct solution on F, reaching 10 solved problems, which earned them the victory.
Congratulations to Moscow State University
for successfully defending their title as the ICPC World Champions!
As general statistics, here are two graphs showing the number of submissions made for each problem and for each programming language, respectively. The positive y axis has the number of accepted solutions made, and the negative y axis has the number of rejected solutions made.
As can be seen, the most popular language was (as usual) C++, this year by an even wider margin than usual: more than 95% of all submissions were made in C++.
A note about solution sizes: below the size of the smallest judge and team solutions for each problem are given. These numbers are just there to give an indication of the order of magnitude. The judge solutions were not written to be minimal (though some of us may overcompactify our code) and can trivially be made shorter by removing spacing, renaming variables, and so on. And of course the same goes for the code written by the teams during the contest!
Explanation of activity graphs: below, for each problem a team activity graph is shown. This graph shows the number of submissions of different types made over the course of the contest: the x axis is the time in minutes, the positive y axis has the number of accepted solutions made, and the negative y axis has the number of rejected solutions made.