Пост рассчитан на новичков и программистов с промышленным опытом но без опыта участия в алгоритмических соревнованиях и описывает опыт участия в Google hash code 2019.
Девизом участия в GHC в этом году стало “Just for fun” по ряду причин:
Алгоритмы и структуры данных не являются моей основной специализацией
Призовых мест без основательной подготовки тут не получить. Как выглядит человек с основательной подготовкой https://www.youtube.com/watch?v=kMDSltQN0MY
Я простудился и вообще официально на больничном
Результаты
No alt text provided for this image
По хабу: 17 из 32
По Украине: 192 из 385
Глобально: 3057 из 6671
Команда
Выступали в 2м. https://www.linkedin.com/in/gleb-shvydkov-7b3a19161/ и Я. Особо не готовились кроме решения задач на hackerRank в свободное время.
Место проведения
Особенность GHC это социальная направленность. Компании и коворкинги предоставляют место для проведения соревнований - хабы, но можно и писать из дома. Как показывает практика в хабе веселее. 2й раз участвовал из https://www.facebook.com/TseHUB/ . Подал заявку поздно и нам выдали место за барной стойкой) Когда одна из команд свалила - пересели за нормальный стол
Соревнования
Прочитать и обсудить задание
Парсинг входных данных. Сделать из примера объекты и конвертировать в выходной формат https://github.com/LyashenkoGS/googleHashCode2019/commit/32adf2adb427e51fe77692b7d9b5e67c60422442 - 45 мин (с учетом прочитать и понять задание)
Простейший брутфорс алгоритм https://github.com/LyashenkoGS/googleHashCode2019/commit/04458d64632f6ce21f993d8b752cb01c7c81c316 - 30 мин
Подсчет очков(чтоб не отсылать каждый раз ответ на сервера гугла, ждать, сравнивать с прошлыми очками) https://github.com/LyashenkoGS/googleHashCode2019/commit/93da1742d0eff1e7038f2b0560ade06bc741bb08 - 70 мин (тут потеряли много на суету и попытку делать параллельно)
Оптимизировать алгоритм - не успели. Потрачено - 60 мин. Отлавливали баги в процессе реализации.
Первые 4 пунктов плохо распараллеливаются между 2мя людьми. Поэтому писали по очереди в духе парного программирования. Иногда все таки делали параллельно и скидывали куски кода по Skype.
Где считали рациональным - добавляли тесты. Примерно каждый час был перерыв на 5-10 минут.
Оптимизация решения
Задача напоминает https://en.wikipedia.org/wiki/Knapsack_problem. Идея была в том чтоб после реализации брутфорса добавить подбор оптимального следующего слайда из допустим 10 следующих фотографий используя функцию скоринга.