Теория игр и системы рекомендаций: участники о задачах на VK Cup 23

Финалисты чемпионата по программированию от VK рассказывают, как решали задачи от «Почты», «Дзена» и «ВКонтакте».

VK Cup — чемпионат по программированию, который VK ежегодно проводит с 2012 года совместно с платформами Codeforces и All Cups. В этому году его финал впервые вернулся в офлайн после двухлетнего перерыва и объединил пять дисциплин, две из которых проводились впервые.

За свою более чем 10-летнюю историю VK Cup вырастил целое сообщество разработчиков и специалистов, получивших как новые знания и опыт, так и престиж победителей и лидеров рейтингов лучших программистов. За всё время на чемпионате зарегистрировались более 35 тысяч участников из 50 стран и 750 городов по всему миру, а общий призовой фонд составил 37 миллионов рублей.

В этот раз задачи для трека Engine по спортивному программированию написал Геннадий Короткевич — самый титулованный спортивный программист в мире и трёхкратный победитель VK Cup. Для остальных треков чемпионата задачи подобрали сами сотрудники VK, взяв за основу реальные процессы и вызовы в разработке сервисов компании.

Мы поговорили с участниками финала в офисе VK, чтобы узнать их впечатления от соревнования.

Честно говоря, я даже не думал, что дойду до финала! К заданиям особо не готовился: сам синтаксис Go знаю неплохо, но вот нюансы — не так хорошо, как ожидал. Я по большей части на Go программирую только бэкенд-приложения: это хоть и широкий, но достаточно однонаправленный угол обзора. После сдачи заданий понял, что в последнем решении сделал ошибку из-за незнания каких-то основ. Это большой опыт в плане изучения нового, расширения кругозора.

Первая задача была на работу с многопоточностью Go. Основная сложность — правильно организовать работу связанных между собой функций, но глобально я с ней справился. Вторая задача — более интересная и трудная. Нужно было прочитать файлы с большим количеством чисел и отсортировать, либо оставить только уникальные значения. Это задача на правильную работу с памятью и машинными ресурсами.

Тут я столкнулся с такими задачами, которые я не решал. Это саморазвитие, познание самого себя, а ещё тут можно общаться с умными людьми и понять, какой ты на их фоне.

Интерес к VK Cup у меня был ещё с прошлого года, но я не участвовал — считал себя недостаточно компетентным. А мой друг поучаствовал в треке Design, стал финалистом — и мне захотелось тоже. В этом году появился трек JS, а я как раз фронтенд-разработчик — так произошел мэтч, и я подал заявку.

На треке мы разрабатывали клиент «Почты Mail.ru» для десктопа — это длилось все три этапа от квалификационного отбора до финала. На первом этапе мы делали минимальный функционал, просто чтобы отображались письма и папки. В качестве контента для отображения был файлик json, в котором лежало 200 писем и картинки — весил он примерно 80 мегабайт. Эти файлы нужно было обработать: достать картинки и оптимизировать данные, чтобы их было удобно отдавать на клиент.

Бэкенд нужно было писать на NodeJS, без сторонних фреймворков. Это нетривиальная задача: обычно так никто не делает. Для дизайна фронтенда нам дали макет из Figma, но он был с подвохом: группировка элементов была немного не та. Я несколько часов исследовал продакшн-версию Почты и нашёл несколько багов интерфейса, о чём упомянул при защите.

Я сильно прокачался на VK Cup, потому что решал редкие задачи. Например, я так реализовал всплывающие окна pop over, чтобы при масштабировании интерфейса они не пропадали и аккуратно перемещались. Это оказалось сложно, потому что нужно было отслеживать координаты окна.

На моё участие повлияли две вещи: кто-то из моих друзей ВКонтакте решил податься на отбор, а позже я увидел рекламный пост про новый сезон кубка. Решил подать заявку, а потом дошёл до финала.

Трек Engine — это спортивное программирование. Здесь интересные олимпиадные задачи, которые были мне знакомы ещё со школьных времён: я участвовал в всеросе по математике, отбирался на международную олимпиаду по информатике.

На треке было шесть задач по возрастающей сложности: от стандартных до необычных. Порадовало количество времени: нам дали три часа на шесть задач — это достаточно много, хотя пятая задача потребовала большой реализации. Она была из теории игр: у нас есть бесконечная строка, содержимое которой определяет, кто когда побеждает. Нужно было предсказать, какая из переменных бедует выигрывать статистически чаще.

Мне нравится соревноваться. В ходе соревнования ты улучшаешь себя, прогрессируешь, решаешь более сложные задачи. Конечно, и самооценка повышается. Соревноваться с другими более захватывающе и волнительно: и победа, и проигрыш вызывают много эмоций.

Приятно подниматься в рейтингах: можно потом сказать, что находишься в топ-1000 программистов России. Я вот, получается, топ-2.

Мне интересен VK Cup как инструмент для проверки своих сил. На работе я Go вообще не занимался: это не моя область, но очень сильно им интересуюсь. По Go очень мало учебной информации — точнее, она быстро устаревает. А о чемпионате я узнал как раз благодаря электронным курсам по Go от VK.

Мне нравится, как преподносит информацию автор этого курса, Василий Романов (замтехдира «Облака Mail.ru»). Когда доходишь до определенного уровня развития, начинаешь хотеть узнавать больше, но информации не хватает. И так уходишь в практику, пытаешься что-то сделать для себя.

Так я что здесь just for fun. Решить сложную задачу — а почему нет?

Про VK Cup узнал от друга: мы с ним вместе развивались в сфере ML, прошли через хакатоны, соревнования. Я успел поработать в стартапе по компьютерному зрению — занимался промышленностью, контролем качества, определением дефектов на металлических заготовках. А потом полгода работал в «Яндексе»: через компьютерное зрение определял различные лицевые действия водителей, например, зевают ли они. Это помогало контролировать их уровень усталости.

Атмосфера соревнования — это здорово, особенно в офлайн-формате. Точно знаю, что не начал бы так просто разбираться с рекомендательными системами, если бы не кубок. Благодаря задаче в финале пришлось поизучать, поразвиваться, хотя в итоге я своим предпочтениям в плане области профессионального интереса не изменил. Я прокачал часть своих навыков: теперь знаю, какие подходы применяются в рекомендательных системах типа «Дзена», как можно их улучшить.

Когда я начал пользоваться «Яндекс.Музыкой», первое, что я в ней зачем-то поискал, было phonk remix — так она мне до сих пор рекомендует фонк. Один раз ошибся в жизни, и тебе будут напоминать об этом всегда. Так вот на треке у нас была задача по рекомендации постов, и только последний день мы закинули идею, что можно к ранжированию добавить вес давности поста. Например, если юзер смотрел статью очень давно, то вес у неё должен стать меньше — потому что интересы людей меняются со временем.

Вообще я на VK Cup оказался по заданию от вуза. В техникуме сказали обязательно записаться на олимпиаду — сертификаты потребуются для защиты дипломной работы. Я записался на один чемпионат по Android, но не прошел отбор, стал искать что-то ещё и наткнулся на рекламный пост про VK Cup. Записался по приколу и дошёл до финала.

Большую часть приза отдам родителям за их нервы. Они мне ноутбук купили на Новый год, я их достал своим программированием: сижу дома, никуда не выхожу, что-то делаю за компьютером непонятное. Хотя сами же в седьмом классе меня записали на курсы — по-моему, по C++.

В прошлом году я уже участвовал в VK Cup, но тогда остановился на 84 месте. А теперь дошёл до финала, хотя задачи и тогда, и сейчас были похожими.

На первой квалификации была задача по NLP. Есть сообщество ВКонтакте, в котором есть посты, и нам нужно по их содержимому определить сообщество в одну из 10 заданных категорий по видам спорта. Есть две выборки: одна обучающая, где уже размечено, какие посты к какому виду сообщества относятся, а вторая — рабочая. Основная загвоздка — правильно очистить этот набор данных. Постов, которые подходят к нескольким категориям и снижают точность определения тематики, быть не должно.

Был ещё второй отбор — вот это была весёлая задача. Здесь нас просили рекомендовать статьи для «Дзена». Есть информация о том, как 200 тысяч пользователей смотрели контент, и есть 100 тысяч новых постов, из которых для каждого пользователя нужно выбрать топ-20. Не требуется, чтобы он их лайкнул или дизлайкнул — нужно, чтобы он просто провёл на них очень много времени.

Помимо этой информации есть эмбеддинги — то есть не сами тексты постов, а условные вектора, который характеризуют информацию из поста. Изначально все думали, что взлетит идея, которая используется в face recognition. Если взять вектора поста, который пользователи смотрят долго, и нового поста, а потом посчитать их скалярное произведение, то мы получим число, которое отражает меру их похожести. Но это была ошибка, которую допустили все участники: если две статьи похожи по контенту, это еще не означает, что пользователям они будут одинаково интересны.

А дальше появилась идея построить ALS — матрицу по методу наименьших квадратов, которые основаны на истории просмотра пользователя. Но тут начались особенности объёма данных — если вы неправильно их храните, вам просто не хватит памяти. Поэтому надо использовать специальную sparse matrix, разряженную матрицу — она более компактно хранится в памяти. Потому что всего постов очень много, и каждый пользователь явно не все их смотрел: во многих ячейках обычной матрицы будут просто нули. А разряженная эффективнее хранит информацию.

Для меня соревнование — это способ выйти из зоны комфорта и делать то, что скорее всего никогда не делал. Это самый лучший способ прокачать свои хард скилы. И уметь себя презентовать — тоже очень важно. Если человек не может рассказывать о своём решении, его неинтересно слушать и никто не захочет за этим повторять. Я вот учу студентов и для меня важны софт скилы: рефлексия тоже помогает отдавать себе отчёт, что и почему ты делаешь, и это развивает тебя профессионально.