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

в 19:20, , рубрики: hola, javascript, node.js, nodejs, Алгоритмы, Блог компании Hola, занимательная задача, занимательная задачка, занимательные задачи, Занимательные задачки, ИИ, искусственный интеллект, итоги конкурса, ищем таланты, конкурс, конкурсы, конкурсы разработчиков, переговоры, соревнование, соревнования, соревнования по программированию, Спортивное программирование, теория игр

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

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

  1. Asta — приз 3000 USD.
  2. Silent Bob — приз 2000 USD.
  3. 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: Число сеансов, прерванных данным участником (по причине исключений или некорректных результатов)

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

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

Автор: feldgendler

Источник

Поделиться

* - обязательные к заполнению поля