Всем привет! 5 февраля завершился очередной VK Cup, в котором в этот раз впервые была секция посвящённая Go. О конкурсе я узнал случайно в одном из Телеграм каналов и решил посмотреть, что же там за задачи. Соревнование состояло из из 3 этапов:
Квалификация: нужно было реализовать несколько функций, чтобы прошли тесты. Дальше проходило 256 человек.
Отбор: задача про внешнюю сортировку и построение кучи, которая не вмещается в RAM. Дальше проходило 16 человек.
Финал: построение коллажа из 1000+ картинок размером 512×512 px.
Про первые 2 раунда я рассказывать в этой статье не буду, возможно сделаю отдельную статью, а расскажу про финал и решение, которое принесло победу. Код решений всех раундов можно посмотреть на GitHub'е.
В финале были чёткий критерий оценки: кто быстрее построит коллаж, тот и победил. Решение «в лоб» решает эту задачу за ~16 секунд на моём AMD Ryzen 7 5800H (16 HT cores). Если интересно как его ускорить до 0.23 секунды, прошу под кат, там много текста, кода, картинок и даже немного ассемблера.