Закончен VK Cup 2015. Я очень рад, что получился большой интересный Чемпионат с захватывающим Финалом. Такой драматической развязки и неожиданного хода соревнования я не видел очень давно.

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

Если вы понимаете о чем я, и:

• вы прошли в Раунд 3 чемпионата
• или имеете титул "Мастер" (оранжевый цвет) или выше,

то у вас есть замечательная возможность присоединиться к разработке самой большой соцсети Европы (и, ИМХО, лучшей в мире). Обратите внимание, что команда ВКонтакте целиком русскоязычная, а разработка ведется из Санкт-Петербурга.

От себя отмечу, что партнерство ВКонтакте и Codeforces имеет большую историю. ВКонтакте был основным спонсором Codeforces несколько лет. Вот уже два раза мы вместе проводили Чемпионат — с ВКонтакте работать очень приятно и комфортно. Коллектив разработчиков в большой степени ориентирован на олимпиадников, так что уверен, здесь вы будете чувствовать себя в своей тарелке.

VK Cup 2015 завершен! Это было что-то невероятное — частая смена лидеров, тяжелый ход контеста фаворита, посылки топовых команд на последних секундах!

Сегодня же вечером в торжественной обстановке в зале "Толстой" отеля Кортъярд Марриотт были подведены результаты.

• 1 место: команда из ИТМО в составе Геннадия «tourist» Короткевича и Нияза «niyaznigmatul» Нигматуллина — Чемпионы VK Cup 2015 и приз в 1048576 рублей,
• 2 место: команда из ИТМО в составе Адама «subscriber» Бардашевича и Бориса «qwerty787788» Минаева — приз в 524288 рублей,
• 3 место: команда из ИТМО в составе Ивана «Belonogov» Белоногова и Ильи «izban» Збаня — приз в 262144 рублей,
• 4 место: команда из Нижегородского ГУ в составе: Владислав «vepifanov» Епифанов (ННГУ) и Николай «KAN» Калинин
• 5 место: команда из Уральского ФУ в составе Ильи «KuchumovIlya» Кучумова и Олега «Merkurev» Меркурьева
• 6 место: команда из Московского ГУ в составе: Василия «SirShokoladina» Мокина и Глеба «GlebsHP» Евстропова
• 7 место: команда из Уральского ФУ в составе Алексея «Um_nik» Данилюка и Никиты «sivukhin» Сивухина
• 8 место: команда из МФТИ в составе Михаила «Endagorion» Тихомирова и Александра «map» Машрабова

Команды с 4-го по 8-е места завоевали призы в размере 131072 рублей! Все участники финала получили ценный подарок и сертификат финалиста.

Вот несколько фотографий с закрытия соревнования.

VK Cup 2015 - Finals состоится уже сегодня! Мы желаем удачи всем участникам, а болельщикам — насладится интересным соревнованием.

Лучшие 20 команд по результатам серии отборов собрались в Санкт-Петербурге, чтобы встретиться в финале и побороться за титул Чемпиона и солидный призовой фонд:

• 1 место — 1048576 рублей,
• 2 местo — 524288 рублей,
• 3 местo — 262144 рубля,
• 4-8 места — 131072 рубля.

Болеть за команды можно будет по ссылке http://codeforces.me/spectator/contest/562/standings, которая будет доступна после старта соревнования.

Удачи! Желаем только положительных эмоций. На старт! Внимание! ...

Генераторы — это такие вспомогательные программы в задаче по программированию, которые выводят тесты. Далеко не всегда ручные тесты в задаче достаточно маленькие, чтобы обойтись только ими. В этом случае на помощь и приходят генераторы. Если вы пишете генератор на С++, то использование testlib.h — хороший выбор.

Виды генераторов

Есть два вида генераторов: обычные и мультигенераторы.

1. Первые за один свой запуск выводят ровно один тест. Обычно, чтобы сгенерировать несколько тестов, такой генератор надо запустить несколько раз с разными параметрами командной строки. Такие генераторы выводят тест в стандартный поток вывода (на экран).
2. Мультигенераторы за один запуск выводят сразу много тестов. Такие генераторы выводят тесты в файлы (один файл — один тест).

Пример простого обычного генератора на testlib.h

Выводит пару чисел от 1 до n, где n — переданный параметр запуска генератора.

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
    int n = atoi(argv[1]);
    cout << rnd.next(1, n) << " ";
    cout << rnd.next(1, n) << endl;
}

Зачем testlib.h?

При невнимательном взгляде кажется, что testlib.h почти не нужен для написания генератора. На самом деле это неправда. Почти в каждом генераторе нужна возможность получать случайные значения, и есть большое искушение использовать rand(). Не делайте этого. Основной принцип написания генератора: генератор должен выводить один и тот же тест при компиляции любым компилятором на любой платформе, если он запущен одинаковым способом. При использовании rand() или классов C++11 вроде mt19937/uniform_int_distribution ваша программа будет выводить разные тесты после компиляции разными компиляторами.

Генератор случайных значений в testlib.h гарантирует, что будет сгенерировано одно и то же, независимо от генератора и платформы. Кроме того, в testlib.h есть разные удобности для генерации тестов, например, rnd.next("[a-z]{1,10}") вернет случайное слово длины от 1 до 10 из букв от a до z.

Что есть у testlib.h?

Чтобы инициализировать testlib-генератор, первая строка вашего генератора должна иметь вид registerGen(argc, argv, 1); (где 1 — это версия используемого генератора случайных чисел). После этого можно будет пользоваться объектом rnd, который будет проинициализирован хешем от всех аргументов командной строки. Таким образом, результат вывода g 100 и g.exe "100" будет одинаков, а у g 100 0 будет отличаться.

Объект rnd имеет тип random_t, то есть вы можете создать и свой генератор, но обычно это не нужно.

У объекта rnd есть много полезных членов-функций. Вот примеры:

Кроме того, не надо использовать std::random_shuffle, используйте shuffle из testlib. Он так же принимает два итератора, но работает, используя rnd.

Пример: генерация неориентированного дерева

Ниже основной код генератора неориентированного дерева, который принимает два параметра — количество вершин и степень его вытянутости. Например, при n = 10, t = 1000 наверняка будет сгенерирована цепь, а при n = 10, t =  - 1000 наверняка будет сгенерирована ромашка (звездочка).

registerGen(argc, argv, 1);

int n = atoi(argv[1]);
int t = atoi(argv[2]);

vector<int> p(n);

/* setup parents for vertices 1..n-1 */
forn(i, n)
    if (i > 0)
        p[i] = rnd.wnext(i, t);

printf("%d\n", n);

/* shuffle vertices 1..n-1 */
vector<int> perm(n);
forn(i, n)
    perm[i] = i;
shuffle(perm.begin() + 1, perm.end());

/* put edges considering shuffled vertices */
vector<pair<int,int> > edges;
for (int i = 1; i < n; i++)
    if (rnd.next(2))
        edges.push_back(make_pair(perm[i], perm[p[i]]));
    else
        edges.push_back(make_pair(perm[p[i]], perm[i]));

/* shuffle edges */
shuffle(edges.begin(), edges.end());

for (int i = 0; i + 1 < n; i++)
    printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);

Как написать мультигенератор?

Мультигенератор за одно исполнение может вывести более одного теста. Тесты таким генератором выводятся в файлы. В генераторе на testlib.h достаточно перед выводом теста написать startTest(test_index). Это приведет к переоткрытию (freopen) потока стандартного вывода на файл с именем test_index. Обратите внимание, что в системе Polygon в таком случае в скрипте надо писать что-то вроде multigen a b c > {4-10} (если предполагается, что запуск мультигенератора вернет тесты 4, 5, 6, 7, 8, 9 и 10).

На что еще обратить внимание?

• Строго следуйте формату теста — пробелы, переводы строк должны быть идеально соблюдены. Тест должен заканчиваться переводом строки. Например, если в тест состоит из единственного числа, то выводите его как cout << rnd.next(1, n) << endl; — с переводом строки в конце.
• Если выводимый тест может быть довольно большим, то предпочитайте printf (а не cout) — это улучшит производительность.
• Лучше выводите long long через cout, но если хотите printf, то используйте константу I64 (например, printf(I64, x);).
• Необходимо не забывать о различных случаях неопределенного поведения языка C++. Например, в приведенном выше примере генератора нельзя объединять две команды cout в одну, т.к. тогда порядок вызовов функций rnd.next не определен.

Еще примеры

Примеры генераторов можно найти в дистрибутиве или непосредственно в репозитории.

Раздел о testlib является временным, он будет влит в общий раздел документации, когда таковой появится.

Если вы разрабатываете задачу по программированию и делаете это на C++, то testlib.h — это правильный выбор для того, чтобы написать вспомогательные программы. Эта библиотека является фактически стандартом де-факто в профессиональном сообществе авторов задач по всему миру. С помощью testlib.h подготовлены всероссийские и международные олимпиады школьников, этапы ICPC, все раунды Codeforces и многие другие соревнования.

Библиотека testlib.h доступна на GitHub.

Библиотека testlib.h имеет очень простое распространение — она размещена в одном заголовочном файле. Для ее использования достаточно положить testlib.h рядом с разрабатываемой программой (чекером, генератором, валидатором или интерактором) и просто добавить в исходный код #include "testlib.h".

Вот когда вам поможет testlib.h:

• при написании генераторов — специальных программ, которые генерируют (выводят) тесты к вашей задаче, ведь далеко не всегда все тесты возможно набрать на клавиатуре (как минимум из-за их возможного большого размера);
• при написании валидатора — специальной программы, которая считывает тест и убеждается в его корректности; валидаторы должны быть максимально строги к формату (пробелам, переводам строк, лидирующим нулям и проч.);
• при написании интерактора — он нужен только для интерактивных задач, если у вас задача не такая, то пока не забивайте голову;
• при написании чекера — если в вашей задаче допустим неоднозначный ответ, то обычно не обойтись без специальной программы, которая, анализируя вывод участника, возвращает вердикт о правильности этого вывода.

Библиотека testlib.h имеет полную поддержку в системе подготовке задач Polygon.

Первые версии testlib.h появились в 2005-м году, как результат портирования testlib.pas на C++. С тех пор testlib.h сильно развился, расширив функциональность и улучшив производительность. Последние версии testlib.h совместимы с компиляторами Visual Studio (разных версий) и GCC g++ (для разных ОС), совместимы с C++20.

Добрый день.

Конечно, пакетные менеджеры в Linux делают проще жизнь и пользователям и администраторам. В мире Windows с этим значительно хуже, хотя некоторые наработки имеются (в Windows 10 обещают прогресс): nuget, chocolatey, wpkg и другие.

Занимаясь поддержкой тестирующих машин для Codeforces, компьютеров Центра олимпиадной подготовки программистов СГУ, подготовкой рабочих станций участников под разные олимпиады я окончательно утомился писать разнообразные bat-файлы и решил упорядочить этот процесс. Хорошим подспорьем оказался Сhocolatey, но в деталях оказалось, что он не всегда мне подходит: в большинстве случаев нельзя указать директорию установки, нет поддержки своих репозиториев, нет многих нужных для Codeforces пакетов, репозиторий Сhocolatey хранит не установщики программ, а только ссылки на них — несколько раз было, что сайт программы лежал, и установить пакет было не возможно.

По этой причине в декабре 2014 я выделил несколько вечеров поработать над удобным для наших целей менеджером (назвал PBOX, читается как пи-бокс). Я предполагаю использовать PBOX для установки специфичного для меня софта (конкретных версий компиляторов), а для программ общего назначения подойдет и Сhocolatey.

В ближайший месяц все тестирующие сервера Codeforces (и многие другие компьютеры факультета КНиИТ Саратовского ГУ) я планирую переустановить, используя в частности и PBOX.

Я немного уже использовал его для личных целей, мне кажется, PBOX может быть полезен и кому-то из пользователей Codeforces. На сайте http://pbox.me есть примеры использования. Ниже немного пояснений.

Установка

Зайдите на http://pbox.me и в административной консоли Windows (найдите в cmd.exe и в контекстном меню по правой кнопке мыши выберите Run as administrator) выполните код с главной страницы. PBOX написан на Java, если у вас она не стоит, то он сам выкачает JRE и положит рядом с собой. Кстати, при каждом запуске PBOX будет самообновляться, так что думать о накатывании обновлений на него не придется.

Я обычно выключаю UAC, если не хотите, то и в будущем его придется всегда запускать в админ. консольке, а отключить uac при установленном PBOX можно просто набрав pbox -uac.

Использование

Хотите себе именно тот g++, что используется на Codeforces? Просто наберите pbox install mingw-tdm-gcc. По-умолчанию установит в %HOMEDRIVE%\Programs\mingw-tdm-gcc, пропишет в PATH несколько директорий (включая MSYS), добавит MINGW_HOME на директорию установки. Вообще, чтобы увидеть что конкретно произойдет достаточно просто на сайте найти пакет и кликнуть Show pbox.xml.

Пакетов в PBOX пока совсем не много (но и не мало, 73). Заходите на http://pbox.me/packages и смотрите. Из полезного консольного рекомендую pbox install tools — это сборка полезных утилит sysinternals, windows resource kit, support tools, а также разных curl, wget, imdisk и других, которые сразу добавятся в PATH. Кстати, будет добавлена и полезная утилита runexe.exe, которой можно запускать процессы и смотреть используемое время/память.

Кстати, большинство утилит и компиляторов по-умолчанию будут установлены в C:\Programs (на самом деле в %HOMEDRIVE%\Programs). Довольно удобно иметь путь к ним покороче и без пробелов как у "Program Files".

Можно устанавливать с доп. ключами, например так: pbox install far --homedir=C:\Far --arch=32 --version=3.0.4040. Чтобы удалить пакет, достаточно выполнить pbox uninstall far.

Вот еще примеры доступных команд и их использования:

Выкачать пакет и посмотреть что внутри

Да, это просто. Вот пример ссылки: http://repo.pbox.me/1.0/jdk8/1.8.0_45/jdk8$1.8.0_45.pbox.7z

Код

Код есть здесь: https://github.com/MikeMirzayanov/pbox

Общая информация

Саратовский государственный университет в первой половине августа проводит международную летнюю студенческую школу по программированию. Продолжительность школы — десять дней, школа пройдет с 3-го по 13-е августа 2015 года.

К участию приглашаются как команды из двух-трех человек, так и индивидуальные участники.

Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки.

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

Привет!

Совсем скоро будет дан старт Финалу чемпионата мира по программированию ACM-ICPC.

Напомним, что своими корнями чемпионат уходит в 1970-й год, когда в США в штате Техас было проведено соревнование силами Alpha Chapter организации UPE (которая до сих пор участвует в проведении финалов). С 1977 соревнования имеют многоуровневую систему отбора и заканчиваются финалом. С 1989-го года организацию и координирование ICPC взял на себя Бэйлорский университет, а соревнование стало включать многочисленные региональные отборы, проводимые другими университетами.

В прошлом сезоне в чемпионате приняли участие 38160 студентов из 2534 университетов 101 страны 6 континентов земного шара!

В этом году в финале в Марракеше встретятся 128 лучших команд мира. Следите за финалом этого года с 12:00. Непосредственно соревнование начнется в 13:00.

• текущие результаты (пока там пробный тур), альтернативный вариант от Ахмеда Али
• видео-трансляция на youtube
• текстовая трансляцию на tumblr
• официальные фотографии
• канал 1 на twitch, канал 2 на twitch
• блог Петра Митричева

Удачи командам!

UPD: добавлена ссылка на текстовую трансляцию на tumblr.

Нет ничего лучше, чем провести праздник с пользой. И в эти праздничные дни я успел не только сходить в Парк Победы с семьей, поздравить близких мне людей и посмотреть салют, но и начать избавление от codeforces.ru.

Да, это не ошибка. В самом деле домен codeforces.ru теперь практически не будет использоваться. Вместо пары доменов codeforces.ru/codeforces.com будет использоваться один: codeforces.com

Этот шаг упростит некоторые аспекты навигации, упростит учет статистики, улучшит pagerank и другие метрики домена.

Конечно, все ссылки на codeforces.ru теперь редиректятся на соответствующие на codeforces.com. Кроме того, пока это касается только GET-запросов, чтобы поменьше разламывать какие-нибудь автоматизации.

Внимательные пользователи заметили, что недавно изменилась и работа с картинками. Теперь, если вы вставляете картинку в текст поста/комментария, то при сохранении она выкачивается и сохраняется на Codeforces, а ссылка подменяется на использующую наш домен. Это решает сразу несколько проблем: исчезнувшие или подмененные картинки в старых постах/комментариях, ограничение на кол-во просмотров у отдающего оригинальную картинку сервера, слишком большие картинки пережимаются в поменьше, теперь картинки можно будет всегда отдавать по https, а значит мы стали ближе к внедрению https.

Сегодня, 18-го апреля в 21:00, начнется VK Cup 2015 - Уайлд-кард раунд 2.

Участникам раунда будет предложено максимально продвинуться в решении одной сложной и необычной задачи. Официально в этом раунде смогут принять участие команды чемпионата VK Cup 2015, которые прошли в Раунд 2, но не оказались среди тех топ-100 лучших по его результатам, кто проходит в Раунд 3. Кроме того, этот раунд будет открыт для всех желающих для неофициального участия вне чемпионата. Зарегистрироваться на раунд можно будет в любое время пока он идет.

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

Удачи!

UPD: Закончено системное тестирование. Тесты системного тестирования доступны по ссылке: http://assets.codeforces.com/files/vkcup-2015-wildcard-2-tests.2.zip

Вы можете присылать апелляции по содержанию тестов и ответов на них до 23:59:59 28-го апреля. После этого будут подведены официальные результаты и даже найденные потом проблемы в тестах не будут влиять на финальное положение участников

Добрый день, Codeforces.

Для нас этот день в самом деле добрый и приятный. Мы рады сообщить, что кампания по сбору средств на развитие Codeforces успешно завершена и ее результаты даже превзошли наши ожидания. Спасибо вам за поддержку, доверие и теплые слова.

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

Всем тем, кто теперь ждет от нас по почте подарка, следует обновить адрес в профиле Codeforces или убедиться, что он уже полный и актуальный.

Спасибо!
Михаил Мирзаянов

Привет!

Остались всего сутки до окончания кампании по сбору средств по случаю 5-летия Codeforces. Мы рады вашей поддержке и помощи. Очень стараемся оправдывать ваши и собственные ожидания.

Для тех кто долго запрягает, напоминаем, что у вас еще есть немного времени присоединиться к замечательному списку друзей Codeforces — помочь нам и получить подарок от команды Codeforces!

В момент подведения итогов, конечно, хочется не столько считать деньги, а оценивать прогресс и проделанную работу. Я просмотрел все наши коммиты в Codeforces и Polygon и составил дайджест улучшений/нововведений. Я не стал включать в дайджест малозаметные вам изменения в глубинах бэкенда (хотя улучшения стабильности должны быть видны), инфраструктурные работы, орг. работу по чемпионатам — но, поверьте, и такой работы было не мало :-)

А вот и список достижений за примерно два месяца от нашего юбилея.

В субботу, 21-го марта, в 17:00 будет дан старт Раунду 1 чемпионата по программированию VK Cup 2015! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.

В этом раунде могут принять все те команды, которые прошли квалификацию. Напомним, что из первой квалификации допущены все те команды, что набрали не менее 1500 баллов. Таких оказалось 789. Вторую квалификацию прошли 504 команды, все те, что набрали не менее 1850 баллов. Таким образом, принять участие в Раунде 1 могут 1293 команды!

Участников ждет соренование по правилам классических раундов Codeforces с некоторыми адаптациями:

• задачи будут исключительно на русском языке (в отличие от интернет-трансляции, где будут и на английском);
• в Раунде 1 будут участвовать команды по 1 или 2 человека, разрешается любая коммуникация внутри команды, но какое-либо общение с другими лицами по прежнему, конечно, запрещено;
• каждая команда может использовать один или более компьютеров по своему усмотрению (напомним, что в Финале команде будет дана возможность использовать только один компьютер);
• для членов команды рейтинг будет пересчитан одинаково, исходя из рейтинга команды (учитываются зарегистрированные на раунд члены команды), о подсчете рейтинга команды можно почитать здесь.

Участников ждет обновленная динамическая стоимость задач (смотрите пост), теперь более плавная, с шагом в 250 баллов.

Отметим, что сразу после окончания Раунда 1 будет проведена интернет-трансляция, поэтому просим участников воздержаться до ее окончания от публичных обсуждений, распространения информации о задачах, идеях и даже ходе соренования.

Напомним, что в Раунд 2 пройдут все те команды, которые наберут положительный балл не меньший, чем у команды на 400-м месте.

Желаем удачи и интересной борьбы!

UPD.: Раунд закончен, спасибо за проявленный интерес. Раунд получился динамичным, жюри с интересом следили за ходом соревнования. Поздравляем победителей и напоминаем, что лучшие 400 команд (т.е. те, кто набрал не менее 796 баллов) получают приглашение в Раунд 2. Остальным еще рано расстраиваться, ведь через неделю вас ждет Вайлд-кард 1, по результатам которого будут разыграны еще 50 приглашений в Раунд 2.

Добрый день!

VK Cup 2015 — Раунд 1 (неофиц. интернет-трансляция, только Div. 1) — это неофициальный повтор Раунда 1, открытый для всех участников из первого дивизиона. Это означает, что если вы не принимали участие в VK Cup 2015 (например, вы старше 23 лет), решили прекратить участие в нем или не прошли квалификацию, то вы можете зарегистрироваться на VK Cup 2015 — Раунд 1 (неофиц. интернет-трансляция, только Div. 1) и принять в нем участие.

В интернет-трансляция — соревнование с индивидуальным (не командным) участием, по результатам трансляции будет пересчитан рейтинг всем ее участникам. Задачи будут предложены как на русском, там и английском языках.

На соревновании будет использована плавная динамическая система (с шагом 250). Подробнее о ней можно прочесть здесь.

Не забудьте зарегистрироваться заранее на раунд. Желаем удачи!

В этом месте напрашивается эпиграф про удава и попугаев. Тем не менее, ниже вы найдете мою версию ответа на интригующий вопрос из заглавия теста.

Занимаясь подготовкой VK Cup 2015, мы столкнулись с интересной задачей подсчета изменений рейтингов участников в командных контестах. Сразу скажу, что таковых будет немного, и значительного вклада они не должны внести.

Коротко напомню, что рейтинги Codeforces считаются примерно так:

• у каждого участника есть какой-то рейтинг r_i на начало раунда,
• так как рейтинг Codeforces наследует идеологию рейтинга Эло, то мы стремимся к оценке, что участник b побеждает участника a с вероятностью:

• зная вероятности микроматчей выиграть/проиграть для каждой пары участников, можно посчитать ожидаемое место участника i (как сумму вероятностей его проигрыша по всем остальным участникам),
• если участник i занимает место лучше ожидаемого, то надо увеличить его рейтинг, иначе — уменьшить.

Это совсем общий принцип, который покрыт противо-инфляционными поправками и некоторыми эвристиками. Кстати, у меня есть большое желание пересмотреть точные формулы с помощью сообщества, попутно сделав рейтинг публичным. Но речь сейчас не об этом, а о том как посчитать рейтинг команды.

Кажется естественной идея распространить текущий подход на командное участие. Одна из проблем — отсутствие правила для вычисления рейтинга команды, если известны рейтинги ее членов. Если бы такое правило было, скажем какая-то функция teamRatings(r₁, r₂), то довольно логично использовать именно это значение для вычисления ожидаемого места, а потом одинаково изменить рейтинги участников команды в зависимости от того удачным было выступление (лучше ожидаемого места) или нет (хуже ожидаемого места).

Вот такая идея пришла в голову во время обеда команды Codeforces.

Во-первых, искомая функция teamRatings(r₁, r₂) от рейтингов членов команды должна быть такой, что teamRatings(r₁, r₂) ≥ max(r₁, r₂). Кроме того, понятно, что если к tourist-у добавить кого-то не очень сильного (скажем, зеленого участника), то рейтинг команды не должен сильно отличаться от рейтинга tourist-а.

Мной была предложена такая забавная модель. Пусть есть команда AB из двух участников A и B. Попробуем хоть как-то сравнить ее с одиноким участником C. В моей модели вместо командного контеста A + B против C проведем пару встреч A против C и B против C. Если хотя бы в одной из таких встреч победил член команды AB, то засчитаем победу команде, иначе — участнику C.

Конечно, такой подход не учитывает какой-то совместной работы A и B, но хотя бы честно пытается учесть шансы обоих победить C. Если все три рейтинга известны, то легко посчитать вероятность победы C — это произведение вероятностей победить A и победить B. Просто дважды применим формулу Эло и перемножим результаты.

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

Есть тонкость, что при таком подсчете рейтинг команды зависит от рейтинга противника C. Как же его выбрать? Можно показать, что при изменении C, результат меняется монотонно. Кажется красивой идея выбрать такое C, чтобы рейтинг команды в конце концов оказался ему и равен. То есть, в качестве противника команде подобрать такого, который играет с командой на равных. Это можно сделать бинпоиском, хотя, наверное, можно и вывести точную формулу (кто поможет?).

В результате получается примерно такой код:

long double getWinProbability(long double ra, long double rb) {
    return 1.0 / (1.0 + pow((long double) 10.0, (rb - ra) / 400.0));
}

long double aggregateRatings(vector<long double> teamRatings)
{
    long double left = 1;
    long double right = 1E4;

    for (int tt = 0; tt < 100; tt++) {
        long double r = (left + right) / 2.0;

        long double rWinsProbability = 1.0;
        forn(i, teamRatings.size())
            rWinsProbability *= getWinProbability(r, teamRatings[i]);

        long double rating = log10(1 / (rWinsProbability) - 1) * 400 + r;

        if (rating > r)
            left = r;
        else
            right = r;
    }

    return (left + right) / 2.0;
}

Полный код можно посмотреть найти по ссылке http://pastebin.com/HnteNGuN

Еще раз отмечу, что какой-то абсолютно справедливой модели посчитать рейтинг команды по рейтингам ее членов мне кажется нет. У меня есть мнение, что это неплохой вариант. Что скажете?

Вот интересные примеры:

Или вот еще интересное следствие: команда из 3350-ти Бредоров будет решать как tourist.

Заметно, что такой подход, видимо, как-то занижает рейтинг команды (или нет?). Наверное, это не очень страшно — ведь рейтинги команд будут сравниваться почти всегда с рейтингами команд (а команды из одного члена будут, возможно, получать некоторый буст).

Буду рад альтернативным моделям агрегирования рейтингов.

523A - Rotate, Flip and Zoom

Это была несложная задача на технику работы с двумерными массивами. Для решения задачи можно было честно последовательно проделать все три операции или заметить, что первые две (поворот + отражение) совместно дают простую транспозицию (отражение относительно главной диагонали, когда клетка с координатами (i, j) отображается на клетку с координатами (j, i)). Поэтому для вывода ответа было достаточно сделать два цикла (используется 0-индексация и псевдоязык):

for i = [0...2*a-1] begin
  for j = [0...2*b-1] begin
    print(a[i / 2][j / 2])
  end
  вывести перевод строки
end

Пример решения: 10286345.

523B - Mean Requests

Подсчет приближенного среднего подробно описан в условии задачи (даже приведен псевдокод). В самом деле при его подсчете надо было просто следовать описанным правилам подсчета.

Для подсчета среднего на отрезках длины T достаточно знать значение суммы элементов на отрезках длины T (для получения среднего надо просто значение суммы делить на T). Если это делать наивным способом, подсчитывая сумму каждый раз в цикле заново, то получается неэффективный медленный алгоритм. В самом деле, при T = n / 2 и наборе из m = n запросов n / 2 + 1, n / 2 + 2, ..., n такой алгоритм суммарно выполнит около n² / 4 действий. Для заданного максимального значения n эта величина будет слишком большой для вычисления в 4 секунды.

Для ускорения подсчета суммы на отрезках длины T можно либо поддерживать эту сумму, тогда при перемещении старта такого отрезка с индекса i на индекс i + 1 сумма изменяется следующим образом: sum:  = sum - a[i] + a[i + T]. Таким образом, пересчет суммы от предыдущего положения старта отрезка до нового будет работать за одну формулу (ограниченное сверху некоторой константой количество действий).

Второй вариант как быстро находить суммы на отрезках состоит в подсчете вспомогательного массива частичных сумм. Пусть b[i] — сумма первых i элементов массива a. Тогда сумма элементов массива a на отрезке от l до r равна b[r + 1] - b[l] (если массив a 0-индексирован). Подсчет массива b можно осуществить за один проход слева направо по формуле b[i] = b[i - 1] + a[i - 1].

Пример решения: 10291184.

523C - Name Quest

Наивный способ решения задачи (перебрать разрез и проверить "хорошесть" каждого из них) работает за квадратичное время и недостаточно эффективен, чтобы решение прошло.

Посчитаем две позиции:

• такую минимальную позицию l, что подстрока t[1..l] хорошая, тогда очевидно, что любой разрез за позицией l будет таким, что левая часть "хорошая",
• такую максимальную позицию r, что подстрока t[r..|t|] хорошая, тогда очевидно, что любой разрез перед позицией r будет таким, что правая часть "хорошая".

Каждую из величин l и r можно найти жадным образом просто итерируясь до вхождения очередной буквы и продолжая поиск следующей. Вот пример возможного кода для поиска l:

j := 1
for i := 1 to |t|
    if j <= |s| && s[j] == t[i]
        j = j + 1
        if j = |s| + 1
            l := i

Для того, чтобы после разреза обе части содержали s необходимо и достаточно, чтобы разрез проходил между l и r. Таким образом, ответ равен r - l или 0, если l или r не нашлось или r < l.

523D - Statistics of Recompressing Videos

Для эффективной реализации алгоритма моделирования процесса необходимо хранить в какой-то структуре h отсортированные моменты освобождения каждого из серверов. Сначала h состоит k единиц.

Будем обрабатывать ролики последовательно в хронологическом порядке. Для того, чтобы начать обрабатывать очередной i-й надо дождаться освобождения какого-либо сервера. Пусть ролик приходит в момент s_i и имеет длительность t_i.

Очевидно, что можно ждать освобождения до первого из моментов из h (так как первый — минимальный). Возможно, что дожидаться в явном виде и не надо, так как сервер уже освобождается к моменту s_i, в любом случае можно считать, что ролик надо отправить на первый из серверов, который освободиться. Пусть минимальный элемент из h равен h₀, тогда ролик начнется обрабатываться в момент max(h₀, s_i), а закончит к моменту max(h₀, s_i) + t_i. Для поддержания структуры h надо исключить из нее h₀ и добавить max(h₀, s_i) + t_i. Таким образом, в h по прежнему будут все моменты освобождения серверов.

Для того, чтобы решения быстро работали, h надо хранить в подходящей структуре данных. Это может быть очередь с приоритетами (тогда минимум будет в голове), либо в упорядоченном множестве. Так как в h могут быть равные элементы, то эта структура либо должна работать с одинаковыми элементами (как очередь с приоритетами или мультимножество по типу std::multiset в C++) или надо в структуре хранить пары (момент освобождения, номер сервера).

Кроме того в качестве h можно использовать классическую бинарную кучу или упорядоченный ассоциативный массив (TreeMap в Java).

Такое решение будет работать за .

Пример решения: 10290987. В этом решении в очереди с приоритетами q моменты хранятся со знаком минус, чтобы сортировка по-умолчанию ставящая максимум вперед, ставила вперед минимум.

14 марта в 18:00 начнется второй квалификационный раунд чемпионата VK Cup 2015!

Правила этого раунда будут совпадать с Квалификацией 1. К участию приглашаются те команды, кто не участвовал в Квалификации 1 или набрал менее 1500 баллов в ней.

Раунд продлится 24 часа, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Квалификационный раунд, как и все предстоящие раунды, требует отдельной регистрации, она будет открыта на протяжении всего раунда.

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

В Раунд 1 пройдут все те команды, которые набрали положительный балл и одновременно не меньший, чем у 500-го места.

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

Категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них до окончания раунда. Запрещено обсуждать задачи с кем-либо кроме вашего сокомандника. Будьте честны, пусть в Раунд 1 пройдут сильнейшие!

Результаты раунда не будут влиять на рейтинг. Уже прошедшие в Раунд 1 команды, могут участвовать в Квалификации 2 вне конкурса. Они никак не влияют на отбор участников в Раунд 1, они могут участвовать только just for fun. Внеконкурсное участие тоже требует соблюдение всех правил, в случае нарушения команда может быть дисквалифицирована с Чемпионата.

После окончания раунд станет доступен всем для дорешивания, а его задачи попадут в архив в том числе и на английском языке.

522A - Reposts

Для решения этой задачи надо было проитерироваться по записям о репостах и поддерживать для каждого пользователя длину цепочки, которая заканчивается в нем. Здесь удобно воспользоваться ассоциативным массивом из строки (имени пользователя) в целое число (длину цепочки). Например, для С++ такой структурой данных будет просто map<string,int>. Назовем такую структуру chainLengths, тогда при обработки строки вида <<a reposted b>> надо просто выполнить присвоение chainLengths[a] = chainLengths[b] + 1. В качестве ответа надо вывести максимальное из значений chainLengths, что можно подсчитывать на лету.

Пара тонкостей: в начале надо занести chainLengths["polycarp"] = 1;, а всюду при работе со строками приводить их к нижнему регистру (или верхнему), чтобы сделать сравнение строк нечувствительным к регистру букв.

Пример такого решения: 10209456.

522B - Photo to Remember

В этой задаче для каждого i фактически надо было найти:

• W_i, равное сумме всех заданных w_j без w_i,
• и H_i, равное максимуму всех h_j без h_i.

Для подсчета первой величины достаточно найти сумму s всех значений w_j, тогда W_i = s - w_i.

Для подсчета второй величины достаточно заметить, что либо искомое значение есть просто максимум по h, либо (если h_i совпало с максимумом) это второй максимум (т.е. предпоследний элемент при сортировке по неубыванию). Второй максимум, как и максимум ищется за один проход по массиву.

В таком случае, для нахождения как W_i, так и H_i требуется O(1) действий, то есть O(n) суммарно на всё решение.

Пример решения: 10193758.

522C - Chicken or Fish?

Для решения задачи необходимо заметить, что при наличии недовольных пассажиров (т.е. тех, для кого r_i = 1), существенную роль играет только первый из них, так как остальные вполне могут быть недовольными именно тем блюдом, которое не хватило первому из таковых.

Пусть массив b — это массив максимальных возможных количеств порций каждого из блюда на момент старта обслуживания Поликарпа. То есть просто массив b надо заинициализировать массивом a, а каждый раз, когда t_i отлично от 0, то делать b[t_i] = b[t_i] - 1 (уменьшать количество порций блюда). Кроме того, пусть unknown — это количество пассажиров, про которых неизвестно какие точно блюда им достались (то есть для них t_i = 0). Пусть величина unknownBeforeUpset — это такое же количество, но до первого недовольного.

Таким образом, есть два основных случая:

• недовольных пассажиров нет вообще, тогда блюдо i могло закончится тогда и только тогда, когда b[i] ≤ unknown (жадно отдаем это блюдо всем пассажирам, для кого их точное блюдо неизвестно),
• недовольный пассажир есть, этот случай разберем подробнее.

Каким блюдом мог быть недоволен первый из таких пассажиров? Очевидно из списка кандидатов надо выкинуть все такие блюда, которые упоминаются не раньше него (значит, что они закончится до него не могли). Из оставшегося набора блюд достаточно перебрать все блюда и проверить могли ли они закончиться до этого пассажира. То есть блюдо i могло быть тем блюдом, что привело в недовольство первого недовольного, если одновременно верно:

• это блюдо i не упоминается на этом пассажире или позже,
• это блюдо i такое, что b[i] ≤ unknownBeforeUpset.

Для всех таких блюд, очевидно, в ответе должно стоять Y (они могли закончится к Поликарпу). Кроме того, из всех таких блюд наибольшую степень свободы дает блюдо с наименьшим расходом (количеством порций b[i]). Выберем именно такое блюдо и в остаток пассажиров с неизвестным блюдом restUnknown = unknown - b[minFirstFinished] попробуем поместить все вхождения каждого из других блюд. То есть блюдо j могло закончится до Поликарпа тогда и только тогда, если для него b[j] ≤ restUnknown (то есть закончилось то блюдо, что расстроило первого из недовольных, а следом — j-е).

Такое решение работает за O(m + k).

Пример решения: 10212686.

522D - Closest Equals

Воспользуемся тем, что задача задана в офлайн-формулировке, то есть все запросы можно считать до нахождения ответов на них.

Пройдем слева направо по массиву и составим новый массив b, записав в b[j] расстояние до ближайшего слева парного j-му элементу значения, то есть a[j - b[j]] = a[j]. Если такового нет, то запишем в ячейку бесконечность.

Эти значения соответствуют расстояниям между парными элементами и записаны они в позициях правых элементов в этих парах.

При рассмотрении запроса на отрезке [l, r] нам не нужны вообще такие пары, что начинаются левее l, а минимум надо искать среди пар, что заканчиваются не правее r.

Отсортируем все запросы по l слева направо. Тогда при прохождении по запросам можно поддерживать, что для запроса [l, r] в массиве b установлены бесконечности для всех пар, в которых левый элемент левее l. Для этого просто предподсчитаем для каждого элемента ближайший справа парный next[i] (то есть верно, что b[next[i]] = next[i] - i), и при покидании ячейки i будем записывать в b[next[i]] значение бесконечность.

В таком случае, для ответа на запрос [l, r] надо просто найти минимум на префиксе до индекса r включительно по массиву b. Это можно делать быстро разными способами (дерево отрезков, дерево Фенвика).

Асимптотическая временная сложность такого решения составляет .

Пример решения: 10192075.

Всем привет!

7 марта в 18:00 начнется первый квалификационный раунд чемпионата VK Cup 2015!

Раунд продлится 24 часа, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Квалификационный раунд, как и все предстоящие раунды, требует отдельной регистрации. Регистрация станет доступна 7 марта в 00:00, она будет открыта на протяжении всего раунда.

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

Если вы пока не уверены в текущем составе команды, то не регистрируйтесь на предстоящий раунд. Если вы не будете участвовать в первой квалификации или не пройдете по ее результатам в Раунд 1, то вы сможете попробовать свои силы во второй квалификации.

Чтобы пройти в Раунд 1, вам надо принять участие хотя бы в одной из квалификаций. Из каждой квалификации в Раунд 1 проходят все команды с положительным числом баллов, которые набрали не меньше баллов, чем команда на 500-ом месте.

Пользуясь случаем поздравляем всех девушек-участниц с праздником. Спасибо вам за весну!

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

Категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них до окончания раунда. Запрещено обсуждать задачи с кем-либо кроме вашего сокомандника. Будьте честны, пусть в Раунд 1 пройдут сильнейшие!

Результаты раунда не будут влиять на рейтинг, внеконкурсное участие в раунде не разрешается. Однако, после окончания раунд станет доступен всем для дорешивания, а его задачи попадут в архив в том числе и на английском языке.

Добрый день, Codeforces!

Мы рады сообщить вам, что в этом году компания ВКонтакте совместно с площадкой Codeforces проведет обновленный VK Cup. Во многих IT-компаниях, в том числе и ВКонтакте, широко применяется практика парного программирования. VK Cup 2015 предлагает участникам попробовать именно такой формат, допуская к участию команды до двух человек. За призы и звание победителя приглашается побороться русскоязычным молодым специалистам, студентам, школьникам и просто любителям алгоритмов и программирования.

Лучшие 20 команд по результатам отборочных интернет-этапов будут приглашены в финал соревнования, который состоится в июле 2015-го года в Санкт-Петербурге. Компания ВКонтакте покроет расходы на проезд и проживание финалистов, которые будут бороться не только за звание лучших из лучших, но и призовой фонд чемпионата. В этом году мы сделали призы соревнования круглыми числами в двоичной системе счисления:

• 1 место — 1048576 рублей
• 2 местo — 524288 рублей
• 3 местo — 262144 рубля
• 4-8 места — 131072 рубля

Добрый день, Codeforces!

Я с радостью сообщаю, что озвученную поддержку в $10000 удалось собрать чуть более чем за трое суток! Спасибо большое, друзья!

Эта хорошая новость означает, что теперь у нас есть возможность сделать рывок следом за курсом доллара и выплачивать в рублях эквивалентные суммы авторам раундов!

Рублевые выплаты мы привязываем к курсу ЦБ РФ на день раунда, округленный к ближайшему кратному 5 числу рублей по правилам математического округления. В таблице указаны значения, актуальные для даты публикации поста. Звездочкой отмечен бонус, который выдается в случае образцовой подготовки раунда.

И это еще не все! Как и было заявлено теперь у нас есть возможность в достаточной степени поддерживать координатора задач Codeforces Максима Zlobober Ахмедова. К этой роли он приступил осенью 2014-го и под его руководством уже поведены более двух десятков раундов. Подготовка раундов — большая работа, и он отлично с ней справляется. Я надеюсь на нашу продолжительную и эффективную работу вместе.

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

Привет!

Обо мне — закончил СУНЦ МГУ им. А. Н. Колмогорова, съездил школьником на IOI 2012, взял золотую медаль и абсолютное седьмое место в составе сборной России. Из самых крупных последних достижений — 5 место Russian Code Cup 2014, 10-е место в 2013-м и 3-е в 2014-м году на NEERC в составе команды Moscow SU Trinity. Победитель всесибирской олимпиады Поттосина 2013 года и кубка ICL 2014 года в составе той же команды.

Люблю музыку, слушаю разный тяжёлый и не очень рок, хожу на концерты. Сам играю на разных музыкальных инструментах. Член жюри многих школьных олимпиад по программированию. Последняя прочитанная книга — Пелевин, "Чапаев и Пустота". Любимый фильм назвать трудно — люблю фильмы Квентина Тарантино, Роберта Родригеса и Кристофера Нолана.

Как-то так.
Макс.

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

До окончания сбора средств еще далеко, и я искренне верю, что еще есть участники, кто нас поддержит за эти дни. Мы продолжаем сбор средств (что обычная практика краудфандинга) и будем рады выполнить все обязательства по вознаграждениям поддержавшим. Так, совсем недавно в профилях поддержавших нас и выбравших награду "значок в профиле" появился почетный бейдж — символ вашего участия и вовлеченности в развитие Codeforces. Сертификаты и футболки будут разосланы после окончания срока сбора средств. Пожалуйста, немного терпения.

Все собранные дополнительные средства пойдут на развитие и поддержку Codeforces, а именно (при условии достаточного собранного бюджета):

• нарастим гонорары по Div1+Div2 раундам — пусть их будет больше!
• в команде появится специалист по контенту: будет регулярно добавлять и систематизировать тренировки, возможно, статьи;
• нам скоро обязательно понадобится и мы сможем расширить железо;
• усилим команду разработчиков, чтобы больше вас радовать нововведениями!

Спасибо за поддержку, Михаил Мирзаянов

Hi Codeforces!

The VK company (vk.com), the largest social network in Europe and the most popular site in Russia and Ukraine, announces the competition for russian-speaking programmers VK Cup 2015.

As you can see, the reborn VK Cup is focused on Russian-speaking programming lovers. Indeed, the whole VK developer team speaks Russian, most social network users communicate in Russian and the head office of the company is located in St. Petersburg. Those are the reasons we decided to concentrate on the competition for russian-speaking participants — most of the social network code is written by medal winners and ACM-ICPC finals champions. We believe that when we support the enthusiasm of young people towards solving problems and studying algorithms, that we make the world better and invest for the future of our company.

That is not the only innovation of the championship: unlike many other championships conducted by companies, VK Cup 2015 will have two-man teams competing with each other, the participants’ age ranges from 14 to 23 years.

Though we focus on the Russian-speaking participants, we are happy to share our problems and rounds with the participants from the whole world. For that reason, all problems of the championship will be translated into English and will be available to solve after the official championship rounds are over. Besides, in some rounds the participants from around the world can take part unofficially, side by side with the official championship contestants. We will be happy to give out 50 brand T-shirts of the Championship to the best out of competition unofficial participants of Round 3. We will be happy to see interest towards the problems of our championship!

VK Team

Привет, друзья!

Да-да, именно к друзьям Codeforces я хочу сейчас обратиться. Совсем недавно Codeforces исполнилось 5 лет, и по этому случаю мы открываем кампанию по сбору средств на работу и развитие Codeforces.

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

Приглашаем вас рассмотреть возможность поддержать Codeforces. Подробности кампании можно найти по ее прямой ссылке.

Михаил Мирзаянов

UPD: У нас отличные новости!

Привет, Codeforces!

Рад представить вам PyPy на Codeforces. Прошу любить и жаловать.

Хорошие новости состоят в том, что JIT в самом деле работает — PyPy зачастую оказывается существенно быстрее классического Python. Похоже, что обычно PyPy быстрее в 2-60 раз. Например, PyPy 2 показывает 60 кратный прирост производительности на binary-heap-benchmark, а PyPy 3 — 85-ти кратный.

Кроме того у PyPy хорошая совместимость с Python, то есть в большинстве случаев вы можете просто отправить программу на PyPy.

Не уходите далеко — скоро вас ждут еще хорошие новости :)

Добрый день.

В конце декабря-начале января я писал прототип отдельного сервиса на C++, чтобы вынести из Java-кода Codeforces тяжелые данные в С++. Давненько я не писал на C++, испытал забавные ощущения погружения в другой мир.

С удивлением обнаружил отсутствие в C++ хэш-мэпа с открытой адресацией в стандартной библиотеке, как впрочем и в boost-e, как впрочем и других нормальных библиотеках. Даже странно как-то, ведь правда же довольно часто открытая адресация будет делать разрешение коллизий цепочками как по времени, так и по памяти. А так как я предполагаю хранить мелкие объекты, то и наверняка.

Я быстренько набросал прототип, который в самом деле показывает, что открытая адресация в раза 2-3 работает быстрее стандартного unordered_map, так что такой контейнер, наверняка, имеет смысл. Вот вывод бенчмарка на моём ноуте:

std::map takes 15779 ms
std::unordered_map takes 4698 ms
oaht::hash_map takes 1473 ms

Мне кажется, что нормальной реализации в stl-стиле с поддержкой С++11 (move semantics) нет. Может кто-то покажет, но я не нашел.

Вот мой прототип на github: https://github.com/MikeMirzayanov/open_addressing_hash_table К сожалению, я не крутой эксперт C++, и со временем у меня совсем не круто, так что довести до ума такой контейнер в обозримом будущем не получится.

С другой стороны, на Codeforces регулярно поднимается обсуждение C++ и, кажется, есть много участников, понимающих современный С++. Алгоритмы же — это вообще вода и воздух Codeforces.