Конкурс по программированию: Торговля (итоги)

Большое спасибо всем участникам конкурса по программированию ^[1]! Мы рады объявить окончательные результаты конкурса.

В конкурсе участвовали 186 решений. Мы провели между ними турнир в два раунда, как объявляли ранее. Поздравляем победителей:

1. Asta — приз 3000 USD.
2. Silent Bob — приз 2000 USD.
3. Robert Speed — приз 1000 USD.

Специальный приз 400 USD получает участник под псевдонимом indutny за разработку альтернативной арены для онлайн-тестирования решений с большей пропускной способностью, чем у предоставленной нами. Спасибо!

Официальную таблицу результатов вы найдёте на GitHub ^[2].

Решения

Все решения опубликованы в директории submissions ^[3]. В каждой поддиректории находится скрипт solution.js, который участвовал в тестировании. Если участник прислал архив с исходными текстами, то его содержимое помещено в поддиректорию src. Рассмотрено (и опубликовано) только последнее из решений, присланных каждым участником.

Затравочные значения

Как и обещали, мы взяли первый твит из @SpringerTV ^[4], появившийся после окончания приёма решений, и поместили его в ранее опубликованный скрипт. Этот скрипт с текстом твита, немного модифицированный для раздельного вывода двух подпоследовательностей, опубликован как seeds.js ^[5].

Первые 500 нечётных членов последовательности помещены в файл round1.txt ^[6] и использованы в первом раунде.

Первые 500 чётных членов последовательности помещены в файл finals.txt ^[7] и использованы в финале.

Статистика

Участвовавшие в первом раунде 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 ^[8] (2,1 ГБ), а протоколы 2 450 000 сеансов финала — в архиве finals.tar.bz2 ^[9] (322 МБ). Содержимое этих архивов частично перекрывается, так как некоторые сеансы принадлежат и к первому раунду, и к финалу.

В этих архивах в каждом файле вида S/A-B.json находится протокол сеанса с затравочным значением S, где решение A было первым участником, а решение B — вторым.

Для «воспроизведения» протокола сеанса в удобном для чтения формате можно использовать команду haggle.js --replay=LOG.json.

Нам будет интересно увидеть в комментариях интересные подходы к анализу этого массива данных.

Таблицы результатов

Условные обозначения к официальным таблицам результатов ^[2]:

• S: Сумма набранных очков (это и есть предмет соревнования)
• S/N: Средний результат сеанса
• A: Число сеансов с достигнутым соглашением
• A/N: Процент сеансов с достигнутым соглашением
• S/A: Средний результат сеанса с достигнутым соглашением
• X: Число сеансов, прерванных данным участником (по причине исключений или некорректных результатов)

В первой таблице приведены результаты финалистов, во второй — результаты решений, не прошедших в финал.

Ещё раз благодарим всех участников!

Автор: feldgendler

Источник ^[10]