https://habr.com/company/hola/blog/420757/- Спортивное программирование
- Занимательные задачки
- Алгоритмы
- JavaScript
- Блог компании Hola
Большое спасибо всем участникам
конкурса по программированию! Мы рады объявить окончательные результаты конкурса.
В конкурсе участвовали 186 решений. Мы провели между ними турнир в два раунда, как объявляли ранее. Поздравляем победителей:
- Asta — приз 3000 USD.
- Silent Bob — приз 2000 USD.
- Robert Speed — приз 1000 USD.
Специальный приз
400 USD получает участник под псевдонимом
indutny за разработку альтернативной арены для онлайн-тестирования решений с большей пропускной способностью, чем у предоставленной нами. Спасибо!
Официальную таблицу результатов вы найдёте
на GitHub.
Решения
Все решения опубликованы в директории
submissions. В каждой поддиректории находится скрипт
solution.js, который участвовал в тестировании. Если участник прислал архив с исходными текстами, то его содержимое помещено в поддиректорию
src. Рассмотрено (и опубликовано) только последнее из решений, присланных каждым участником.
Затравочные значения
Как и обещали, мы взяли первый твит из
@SpringerTV, появившийся после окончания приёма решений, и поместили его в ранее опубликованный скрипт. Этот скрипт с текстом твита, немного модифицированный для раздельного вывода двух подпоследовательностей, опубликован как
seeds.js.
Первые 500 нечётных членов последовательности помещены в файл
round1.txt и использованы в первом раунде.
Первые 500 чётных членов последовательности помещены в файл
finals.txt и использованы в финале.
Статистика
Участвовавшие в первом раунде 186 решений образовали 34 410 упорядоченных пар. Именно столько сеансов было проведено с каждым из 500 затравочных значений. Общее число сеансов в первом раунде составило 17 205 000. Каждое решение участвовало в 185 000 сеансах.
В 13 868 284 сеансах (80,6%) было достигнуто соглашение. Средний результат сеанса составил 5,8728 очков, а средний результат среди сеансов, в которых было достигнуто соглашение — 7,2858 очков.
Переговоры были прерваны в 626 779 сеансах (3,64%) по различным причинам (недопустимые предложения, исключения, истечение времени).
В финал вышли 50 решений. Они образовали 2 450 упорядоченных пар, и мы протестировали их дополнительно на других 500 затравочных значениях. Для ранжирования финалистов мы использовали также результаты сеансов между ними из первого раунда (но не результаты сеансов с участием решений, не прошедших в финал). Таким образом, места среди 50 лучших решений были определены на основе тестирования на 1000 затравочных значениях. Общее число сеансов составило 2 450 000, а каждое решение поучаствовало в 98 000 сеансах.
В финале соглашение было достигнуто в 2 358 913 сеансах (96,28%). Средний результат сеанса составил 7,0275 очков, а средний результат среди сеансов, в которых было достигнуто соглашение — 7,2989 очков. Впечатляет, насколько хорошо 50 лучших решений используют почти каждую возможность заключить сделку.
В финале переговоры были прерваны в 1 272 сеансах (0,05%).
Протоколы сеансов
Полные протоколы всех 17 205 000 сеансов первого раунда опубликованы в архиве
round1.tar.bz2 (2,1 ГБ), а протоколы 2 450 000 сеансов финала — в архиве
finals.tar.bz2 (322 МБ). Содержимое этих архивов частично перекрывается, так как некоторые сеансы принадлежат и к первому раунду, и к финалу.
В этих архивах в каждом файле вида
S/A-B.json находится протокол сеанса с затравочным значением
S, где решение
A было первым участником, а решение
B — вторым.
Для «воспроизведения» протокола сеанса в удобном для чтения формате можно использовать команду
haggle.js --replay=LOG.json.
Нам будет интересно увидеть в комментариях интересные подходы к анализу этого массива данных.
Таблицы результатов
Условные обозначения к
официальным таблицам результатов:
- S: Сумма набранных очков (это и есть предмет соревнования)
- S/N: Средний результат сеанса
- A: Число сеансов с достигнутым соглашением
- A/N: Процент сеансов с достигнутым соглашением
- S/A: Средний результат сеанса с достигнутым соглашением
- X: Число сеансов, прерванных данным участником (по причине исключений или некорректных результатов)
В первой таблице приведены результаты финалистов, во второй — результаты решений, не прошедших в финал.
Ещё раз благодарим всех участников!