Добрый день.

Теперь Codeforces станет удобнее просматривать с мобильных платформ. Для большинства из них теперь доступен мобильный вид, при котором меню уходит в левую выдвижную панель, а сайдбар — в правую. Обе панели доступны либо по специальным иконкам вверху страницы, либо по свайпу влево/вправо. Скрывать их можно либо тычком в основную область страницы, либо обратным свайпом. В мобильном виде основные шрифты чуток увеличены, что на большинстве экранов можно читать сайт уже без увеличения.

Вот так, например, сайдбар выглядит на моем телефоне:

Отказаться от мобильного вида (или, наоборот, включить его) можно внизу страницы в футере.

P.S. На старых браузерах, да и вообще на не-webkit могут быть сложности. Не уверен, что их легко исправить :-(

Добрый день!

Вот вам немного статистики в виде графиков и чартов за 2015-й год. Я очень доволен их бодрым ростом. На самом деле, каждый год я боюсь обнаружить Codeforces в состоянии плато и каждый год я радуюсь, видя ваш интерес и энтузиазм. Так держать! Вот и опять по разным метрикам мы видим в этом году 20-50% рост!

Кроме того, я уже писал раннее о прогрессе в разработке и чемпионатах и раундах с компаниями-партнерами в 2015-м году. Если не читали, пожалуйста, ознакомьтесь.

А вот и веселые картинки со статистикой:

Рост количество зарегистрированных пользователей. Перевалили 300 тысяч в этом году!

Привет!

Поздравляю всю аудиторию Codeforces с Новым Годом! Конечно, этот год опять не будет простым (ведь 2016 делится на 2, 3 и 7). Желаю вам интересных задач, красивых решений и успешных попыток на последних секундах! Желаю не терять интерес к такого замечательному делу как программирование, верить в свои силы и регулярно находить подтверждение этой вере. А еще не болейте и побольше улыбайтесь (даже если слив). Ура!

В настройках профиля появился волшебный раздел. С Новым годом!

В Новый год мечты сбываются: вы можете сменить хэндл до 10-го января

Открыта традиционная новогодняя акция. Спешите! Только до 10-го января вы можете изменить свой хэндл абсолютно безвозмездно, то есть даром! Сменить хэндл можно лишь единожды. Обратите внимание, что откатить изменения или изменить хэндл еще раз вы сможете только через год. Будьте внимательны и осторожны со своими желаниями! :)

Хэндл можно сменить либо на совсем новый (ранее никем никогда не используемый), либо на тот, который у вас был когда-то ранее. Кстати, ссылки на ваш профиль с прошлым хэндлом работать не перестанут — будет автоматический редирект со старого хэндла на новый. У нас все ходы записаны!

Для смены хэндла нажимайте в профиле "Настройки", затем "Хэндл", а потом внимательно читайте всё то, что написано.

Касательно необдуманных хэндлов я всегда вспоминаю такую историю. Мне как-то написал пользователь с просьбой: "Прошу сменить мой хэндл с I_love_Valya на I_love_Sveta, так как Валю я больше не люблю..."

С новым годом!

Добрый день.

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

Я собрал в список всех тех нововведений, которые в той или иной степени коснулись кого-то (или всех) из пользователей. В этом безликом списке нашли свое место результаты многодневной работы каждого члена (иногда c приставкой ex-) технической команды Codeforces: MikeMirzayanov, MaximShipko, kuviman, fcspartakm, Avalanche. Есть и ценные помощники Edvard (помог с внедрением образовательных раундов), stingray (постоянная помощь с администрированием и настройкой серверов бесценна), demlit и lthirteenthl (помощь с администрированием и железками). И это я только перечислил тех, кто помогает в техническом плане — есть еще важный список всех тех, кто способствует развитию и жизни Codeforces в других аспектах. Спасибо!

А вот и обещанный список завершенных (иногда частично) наших дел в 2015-м году.

Всем привет!

Надеюсь у вас уже праздничное настроение?

Чуть позже я опубликую статистику за год и расскажу про наши достижения за год, а пока речь пойдет о чемпионатах и соревнованиях, которые мы сделали с партнерами в 2015-м году. Сюда не вошли какие-то мероприятия, которые мы делали совсем далеко от площадки Codeforces (например, Russian AI Cup).

Этот год запомнился большим количеством интересных соревнований, которые мы сделали не сами по себе, а вместе с партнерами. Особенно приятно, что все компании, кто хотел пополнить ряды своих сотрудников — все они нашли себе достойных кандидатов среди наших участников. А еще кто-то говорит, что олимпиады не нужны — врут! Вот список мероприятий:

Добрый день.

Теперь для поиска по постам вам вовсе не обязательно уходить в Google, а можно это делать прямо на Codeforces. Мы поддержали поиск по текстам постов на базе Apache Lucene. В индексе содержатся все открытые публичные посты, которых уже более 15000 штук.

Временно поиск по тегам теперь недоступен (но и по тегам заиндексируем), но вместо него вы обнаружите возможность найти посты и даже отсортировать выдачу по нужному критерию. Кстати, язык запросов к поисковику — это все возможности Lucene, так что можете найти полное описание и писать неочевидные запросы.

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

Вот примеры запросов:

• 305 — ищет все посты, содержащие 305, найдет посты про Раунд 305
• andrew stankevich contests — можно писать сразу много слов, будут искаться все
• user:mikemirzayanov title:сазанка — ищет все посты в названии со словом "сазанка" авторства MikeMirzayanov
• "vk cup" — можно использовать кавычку, чтобы искать точные совпадения
• title:educational — искать в названии

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

Добрый день.

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

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

У списка есть название и два относительно секретных ключа — один для его просмотра/использования, а второй для редактирования. Например, вот ключ для просмотра на список со студентами ЦОПП-СГУ на осень 2015-го года: 15c68c2cf878267d59373d1e56be8c9a

Это означает, что на некоторых страницах вы можете использовать дополнительный параметр ?list=ключ, чтобы применить список. Вот пример кусочка экрана по ссылке http://codeforces.com/problemset/page/3?list=15c68c2cf878267d59373d1e56be8c9a:

Ага, на ближайшую тренировку я могу дать задачи 538H - Летняя дихотомия и 538G - Осатаневший робот. Первое число обозначает количество решивших задачу, а второе — количество попытавшихся ее решить. Поиск в таких случаях производится не только по конкретно этой задаче, но по всем возможностям ее использования (сдал задачу в другом дивизионе или мэшапе — информация не потеряется!).

Появились дополнительные элементы управления, чтобы было поудобней выбирать списки:

В настоящий момент списки можно применить:

• для просмотра архива (показывается дополнительно сколько решили/попробовали)
• для просмотра списка раундов/тренировок (показывается дополнительно сколько решили/попробовали)
• для просмотра результатов раунда (фильтруется списком)

Напоминаю, что функциональность пока в режиме ранней беты — возможны какие-то накладки. Исправим (но после полуфинала).

А в какие еще применения спискам пользователей можете предложить вы?

Задачи учебные — постараемся сделать разбор подробным.

598A - Хитрая сумма

Если бы в этой задаче не было бы "хитрости" и надо бы было просто найти сумму 1 + 2 + ... + n, то, воспользовавшись формулами суммирования арифметической прогрессии, можно было прийти к результату s = n·(n + 1) / 2 (числа такого вида называются треугольными).

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

long long pow2 = 1;
while (pow2 <= n)
    s -= pow2 * 2, pow2 *= 2;

Значение s после такого цикла и будет ответом. Количество итераций этого цикла не превосходит двоичного логарифма числа n (точнее — еще плюс единица), что является числом около 30 для максимального возможного теста.

Асимптотика: (на один тест в наборе).

598B - Запросы на строке

Так как значения k_i довольно велики (до миллиарда), то попробуем найти решение, которое не моделирует все k_i вращений. Очевидно, что если рассматривать k-й циклический сдвиг строки длины t, то все сдвиги, кратные t, не меняют строку. Более того, k-й циклический сдвиг строки длины t неотличим от сдвига на величину k mod t (остаток от деления k на длину t).

Таким образом, сразу после чтения очередного запроса можно заменить k_i на k_i mod (r_i - l_i + 1). Далее определим результат после запроса i. Части строки до l_i и после r_i останутся без изменения. А вот подотрезок l_i... r_i провернётся на k_i. Это значит, что вперед встанут заключительные k_i символов этой подстроки, а потом — часть подстроки без заключительных k_i. В итоге обработанный подотрезок будет записан так: s.substr(r - k + 1, k) + s.substr(l, r - l + 1 - k) (участок длины k от позиции на k - 1 левее r + участок длины "длина подотрезка минус k" от позиции l). Следовательно, весь запрос обрабатывается фрагментом кода:

s = s.substr(0, l)
    + s.substr(r - k + 1, k) + s.substr(l, r - l + 1 - k)
    + s.substr(r + 1);

Конечно, в данной задаче удобнее было бы воспользоваться функцией std::rotate, от этого код стал бы только короче. Однако такой подход более С++-специфичный. Эквивалентная строка с использованием std::rotate выглядит так: rotate(s+l,s+r+1-k,s+r+1);.

Асимптотика: O(|s|·m).

598C - Ближайшие вектора

На этой задаче споткнулись очень многие участники. Некоторые даже очень опытные участники соревнований допустили ошибки. Видимо, эта задача проходит с использованием atan2 в long double на g++ (но не на Visual Studio, так как в ней long double имеет такой же размер как и double — 8 байт).

Я опишу здесь решение в целых числах, которое, безусловно, неплохо понимать и знать.

В своих решениях с несложной геометрией я люблю использовать typedef pair<T,T> pt (где T — основной тип данных для точки/вектора), одновременно с дефайнами X на first и Y на second.

Грубо говоря, план решения такой: отсортируем все вектора по полярному углу, затем переберем все пары соседних векторов и выберем такую, угол между векторами в которой минимален.

Для того, чтобы отсортировать что-либо, надо определить функцию порядка "меньше" (возвращает true тогда и только тогда, когда первый аргумент строго меньше второго).

Ниже будем использовать псевдоскалярное произведение векторов (cross(a, b) = a.X * b.Y - a.Y * b.X), которое для простоты будем называть просто векторным. Напомним, что оно равно |a|·|b|·sin(a, b), где sin(a, b) — синус ориентированного угла от первого вектора ко второму. Поэтому знак векторного произведения указывает "верно ли, что угол от первого до второго вектора меньше 180 градусов?" или (что тоже самое) "верно ли, что кратчайший способ совместить (сонаправить) первый вектор со вторым будет двигать первый вектор против часовой стрелки?". Когда величина равна 0 — это значит, что всё равно, как: то есть вектора либо сонаправлены, либо противонаправлены.

Поэтому, чтобы понять, верно ли, что при сортировке первый вектор должен предшествовать второму, почти всегда достаточно посмотреть на знак векторного произведения (больше нуля — значит, "да"). Однако это не будет работать на стыке при переходе через цикл (например, вектор (1, -1) будет определен как стоящий до вектора (1, 1)). Для этого сначала сравним полуплоскости, в которых они расположены (при Y = 0 в верхнюю полуплоскость отдадим положительное направление луча Ox). Функция top определяет "верно ли, что p лежит в верхней полуплоскости?".

bool top(pt p) {
    return p.Y < 0 || p.Y == 0 && p.X < 0;
}

Следовательно, полностью функция "меньше" для сортировки векторов по полярному углу в целых числах выглядит так:

bool polarLess(const pt& a, const pt& b) {
    bool ta = top(a);
    bool tb = top(b);
    if (ta != tb)
        return ta;
    return cross(a, b) > 0;
}

Теперь решим вторую подзадачу — для четырех векторов a₁, b₁, a₂ и b₂ проверить, верно ли, что угол между a₁ и b₁ строго меньше угла между a₂ и b₂.

Напомним, что неориентированный угол между векторами a и b можно получить так: представим, что мы расположили оба вектора так, что вектор a встал по направлению Ox (т.е. просто вправо). Тогда будет достаточно найти полярный угол для b (координату b.Y надо взять по модулю, так как угол неориентированный). Но вектор a не направлен вдоль Ox. Давайте найдем длину проекции b на a (это на самом деле x в системе координат, что направлена так, как нам хочется) и длину проекции b на вектор, повернутый от a на 90 градусов (перпендикулярный) влево. Длину первой проекции найти легко — это |b|·cos(a, b), а длина второй проекции — это |b|·sin(a, b). Однако, если мы возьмем просто скалярное произведение, то получим |a|·|b|·cos(a, b), а векторное — |a|·|b|·sin(a, b).

То есть вектор p = (dot(a, b), cross(a, b)) (где dot(a, b) — скалярное произведение) — это вектор, сонаправленный вектору b' (где b' — результат поворота вектора b, если одновременно вращать и b и a так, что a совпадет с Ox). Здесь хорошо бы сделать рисунок, но уже не до этого.

Таким образом, например, чтобы найти ориентированный угол между векторами (от  - π до π), достаточно взять направление вектора p; иными словами, atan2(cross(a, b), dot(a, b)). Если нужен угол неориентированный, то от векторного произведения (а это фактически координата y у вектора p) надо взять модуль.

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

Таким образом, полный код функции "меньше" для величины угла между векторами a₁ и b₁ против величины угла между векторами a₂ и b₂ выглядит так:

bool angleLess(const pt& a1, const pt& b1, const pt& a2, const pt& b2) {
    pt p1(dot(a1, b1), abs(cross(a1, b1)));
    pt p2(dot(a2, b2), abs(cross(a2, b2)));
    return cross(p1, p2) > 0;
}

Асимптотика: (на сортировку).

598D - Игорь в музее

Здесь надо подробнее описать, что нужно обходить поиском в глубину компоненту связности лабиринта, причем каждую не более одного раза. Во время обхода подсчитывать количество картин и хранить это прямо по индексу компоненты. Если запрос пришел про клетку, для которой уже обработали ее компоненту, то забираем ответ по номеру компоненты. Вот пример простого короткого решения 14257172.

Асимптотика: O(n·m + k) (каждая клетка обходится не более одного раза).

598E - Плитка шоколада

Здесь надо подробнее описать динамическое программирование, которое используется в решении. В решении ниже dp[a][b][k] — ответ на задачу, если есть плитка размера a × b и надо наотламывать k долек из нее. В приведенном решении используется ленивое программирование (каждое состояние анализируется фактически не более раза с помощью поиска в глубину по состояниям) для подсчета таких значений: 14258732.

Асимптотика: (K — оценка на k, то есть 50).

598F - Длина разреза

Эту задачу я когда-то давно подготовил на тренировку СГУ. Ее сдали несколько наших сильных участников (возможно, в дорешку): Nerevar, e-maxx, RAD, stan, NALP. По результатам взломов — все их решения оказались неверными! Участники Educational Codeforces Round 1 добавили отличные тесты!

Вот короткое решение одного из участников раунда (и эффективного взломщика): 14258627.

Асимптотика: (для обработки одной прямой нужна сортировка всех точек пересечения её и многоугольника).

Заключение

Я буду рад дать права на пост тому, кто поможет перевести разборы или улучшит наброски разборов по задачам D-F. Спасибо!

Закончен Educational Codeforces Round 1. 24 часа после окончания фазы основного участия многие из вас пытались взломать соперников, и у многих это получилось!

Всего было сделано 573 успешных взлома, а общее число "взломщиков" — 101. Вот самые результативные из них:

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

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

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

Всем привет!

Во-первых, приглашаю вас принять участие в неофициальном тестовом раунде Testing Round 12. Дело в том, что команда Codeforces внесла множественные изменения в платформу (о чем чуть позже), и все мы хотим быть уверенными, что основная функциональность осталась без изменений. Этот раунд будет иметь сокращенную длительность 1.5 часа, состоять из 3 (может, и 4) задач, которые вы могли уже где-то и видеть ранее. Цель его — с одной стороны, протестировать систему, а с другой — скрасить вечер среды. Конечно, раунд будет нерейтинговым.

Теперь самое главное. В ближайшую пятницу (да, 13-го ноября) Codeforces стартует еще одну линейку раундов. Мы назвали их учебными раундами (Educational Rounds). На примере моих студентов в Центре олимпиадной подготовки программистов Саратовского государственного университета (ЦОПП-СГУ) я регулярно замечаю, что даже те из них, кто имеет заметный прогресс в результатах на раундах, зачастую имеют неширокий кругозор в плане стандартных тем и идей, не знакомы с многими методами. Дело в том, что раунды обычно избегают каких-то фольклорных или классических тем, в результате страдает кругозор очередного поколения участников.

Мы рады объявить о старте серии учебных раундов! Они будут проходить с регулярностью 2-4 раунда в месяц.

Вот их характерные черты:

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

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

Пока подготовка задач к этим раундам будет сосредоточена в Центре олимпиадной подготовке программистов СГУ, основную работу по задачам будет выполнять Эдвард Edvard Давтян. Пожелаем ему удачи, энтузиазма и сил!

До встречи на Testing Round 12, а чуть позже и на Educational Codeforces Round 1.

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

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

Каждый участник характеризуется величиной рейтинга r_i — целое число (возможно отрицательное). Грубо говоря, чем это значение выше, тем лучше участник выступает в соревнованиях. Рейтинг это подсчитывается/пересчитывается таким образом, чтобы выполнялось равенство:

где P_i, j вероятность того, что i-й участник победит на соревновании j-го. Таким образом вероятность победы одного участника над другим определяется только разностью их рейтингов. Например, если разница рейтингов двух участников равна 200, то побеждает сильнейший с вероятностью примерно 0.75. При разнице рейтинга 400 вероятность возрастает до 0.9.

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

Рассмотрим момент до начала раунда и посчитаем для каждого участника его ожидаемое место (его называют seed_i). Ожидаемое место равно сумме вероятностей по всем другим участникам обойти данного плюс один (плюс один берется из-за 1-индексации):

Например, перед Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1) при рейтинге 3503 ожидаемое место у tourist было примерно 1.7, а у Petr при рейтинге 3029 ожидаемое место было примерно 10.7.

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

Посчитаем для участника среднее геометрическое его текущего места и ожидаемого, пусть эта величина равна m_i. В самом деле, это какое-то среднее значение между ними, оптимистично сдвинутое в сторону меньшего из мест. Найдем (с помощью бинарного поиска) такой рейтинг R, которым должен бы был иметь этот участник, чтобы всё-таки ожидаемо занимать место m_i (среди того же набора участников). Текущий рейтинг участника должен быть изменен так, чтобы стремиться к R. Поэтому, изменение рейтинга участника в раунде вычисляется как d_i = (R - r_i) / 2.

Это почти всё, кроме фазы борьбы с инфляцией. Заметим, что при инфляции богатые становятся еще богаче, поэтому будем бороться именно с этим. Если предположить, что рейтинг был уже посчитан справедливо (то есть каждый участник имеет свой статистически обоснованный рейтинг), то математическое ожидание изменения рейтинга по любому участнику должно быть равно 0. Выберем группу наиболее высокорейтинговых участников раунда (по рейтингу r_i — до начала раунда) и скажем, что сумма их рейтингов должна остаться неизменной. В качестве размера такой группы выбирается эвристическая величина . Если d_i таковы, что их сумма для этой группы не равна 0, то ко всем им (по всем n участникам) прибавляется некоторое значение (вычитается) так, чтобы их сумма по s наиболее высокорейтинговым участникам стала равна 0.

После раунда 327 ограничили этот эффект: сначала к каждому изменению прибавляется величина inc =  - sum(d_i) / n - 1 (то есть d_i меняются), затем прибавляется inc = min(max( - sum(d_i) / s,  - 10), 0). Таким образом, эффект изменения рейтингов из абзаца выше ограничен падением каждого рейтинга не более чем на 10.

Кстати, для любого логически непротиворечивого рейтинга должны выполняться несколько инвариантов:

• если участник A имел рейтинг хуже участника B и выступил хуже него на текущем раунде, то и его рейтинг после пересчета должен быть не лучше чем у B;
• если A выступил лучше B, но имел до раунда хуже рейтинг, то ему должны прибавить не меньше единиц рейтинга чем участнику B.

В частности, для обновленного рейтинга Codeforces эти инварианты проверяются на выполнение при любом пересчете рейтинга.

Ознакомиться с используемым кодом можно по ссылке: 13861109.

Вы можете распечатать PDF-версию условий: http://assets.codeforces.com/statements/589.pdf

Пару дней назад был завершен четвертьфинал ACM-ICPC в Саратове. От лица жюри и организаторов еще раз поздравляю победителей, призеров и прошедших в полуфинал. Призовые места завоевали (ура!):

• 1 место: Нижегородский государственный университет #1 (Владислав vepifanov Епифанов, Николай KAN Калинин, Михаил mike_live Кривоносов)
• 2 место: Университет Иннополис (Евгений savinov Савинов, Сергей sokian Киян, Александр map Машрабов)
• 3 место: Саратовский государственный университет #1 (Эдвард Edvard Давтян, Виталий kuviman Кудасов, Данил danilka.pro Сагунов)

В субботу (17-го октября) в 11:00 здесь состоится неофициальная трансляция прошедшего соревнования. Вас ждут интересные задачи, которые жюри постаралось сделать интересными как для начинающих, так и опытных участников. К участию приглашаются как команды из 1-3 человек, так и индивидуальные участники. Контест не будет влиять на рейтинг Codeforces.

Конечно, контест будет нерейтинговым. Рекомендуется командное участие. Скорее всего, позже он будет перенесен в Тренировки.

Желаю участникам!

Председатель жюри MikeMirzayanov.

P.S. Мы сожалеем, что наша трансляция пересекается с другими онлайн-турнирами, но поскольку запланированное изначально время в воскресенье оказалось занято трансляцией московского четвертьфинала NEERC, то подвинуть наше соревнования не представляется возможным. Если вы являетесь школьной командой, то рекомендуем обратить внимание на Интернет-версию Уральской региональной командной олимпиады.

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

Со временем это привело к значительным перекосам в цветах и званиях. Например, стать красным в 2015-м году стало значительно проще, чем в 2013-м.

Проведя опрос о том как именно следует внедрить смену цветовой шкалы, мы решили не затягивать нововведения и рады анонсировать обновленные цвета и звания!

Коротко основные изменения: новый цвет: сине-зеленый или циан — как и ожидается из названия этот цвет займет своё место между зеленым и синим, теперь участники второго дивизиона будут лучше дифференцированны; сдвиг всех цветов вверх по шкале рейтинга — смотрите таблицу ниже, достигать вершин станет сложнее; легендарный гроссмейстер — новое звание и раскраска для тех, кто достиг заоблачного рейтинга 2900.

Холодные цвета серый, зеленый, сине-зеленый и синий всё еще соответствуют второму дивизиону, а остальные — первому.

Требования к тренерскому доступу остались неизменными — вам необходимо иметь 2200 или 1900 и богатую историю участий, чтобы стать тренером. Теги к задачам и создавать группы могут ставить участники из первого дивизиона.

Таблица ниже иллюстрирует новые значения границ цветов и званий

По состоянию на 1-е октября 2015-го года, учитываются только активные пользователи (кто принимал участие в последние полгода).

О том как изменятся формулы рейтинга (да, они будут открытыми!) я напишу в ближайшее время.

Да! Совсем скоро на Codeforces будет внедрена пачка улучшений касательно рейтинга и цветов. Вторая революция цветов и званий уже близка!

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

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

В связи с планируемой сменой границ цветов у нас возникла неопределенность, как именно внедрить нововведение. Здесь есть две опции.

Опция первая: только вперед, не оглядываемся назад

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

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

Опция вторая: сохраним историю

При введении новых границ цветов оставим цвета как есть в старых ранклистах, постах и комментариях. Это не сломает комментарии в стиле "поздравляю с красным цветом!" (но так ли они ценны?) Такой подход сохранит достижение "стал красным", то есть такой пунктик в вашей биографии никуда не денется и останется подкреплен документально.

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

Итого

Как вы видите, оба варианта имеют свои плюсы и минусы. Честно говоря, даже у меня нет уверенного мнения как лучше поступить. По этой причине предлагаю проголосовать и совместно взвесить за и против. Если один из вариантов победит со значительным отрывом, то реализуем его. Иначе сделаю на своё усмотрение.

Пожалуйста, голосуйте только внимательно ознакомившись с опциями. Первые два комментария к посту будут соответствовать возможным опциям. Негативные голоса учитываться не будут, а положительные будут иметь веса 1-2-4-8-16-32 в зависимости от цвета (серый-зеленый-синий-фиолетовый-оранжевый-красный). Голосование секретное, результаты будут 1-го октября вечером.

UPD: Голосование завершено. Мы поздравляем первую опцию с убедительной победой! Она набрала 6394 баллов против 2320 баллов у второй опции. Комментарии для голосования удалены, чтобы не влиять на статистику голосов по комментариям. Ждите нововведений в ближайшее время!

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

Итак, вы прочли задачу и не знаете как ее решать. Попробуйте следующие приемы, зачастую какой-то из них может помочь.

Прием 1: "Вспомнить всё"

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

Прием 2: "От частного к общему"

Представьте, что вы нашли решение задачи (ура!) Рассмотрите какой-то частный случай задачи. К нему, конечно, может быть применен алгоритм решения задачи. Поэтому, чтобы решить общую задачу вам необходимо решить все ее частные случаи. Попробуйте решить какой-либо частный случай (или несколько) и потом попытайтесь обобщить их до решения основной задачи. Такие частные случаи можно рассматривать как упрощения задачи, то есть рассуждать по принципу: "если я не знаю как решать сложную задачу, попробую-ка я ее упростить и найти решения упрощенной версии".

Популярные примеры упрощений (частных случаев):

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

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

Прием 3: "Смелая гипотеза"

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

Примеры частых гипотез:

• ответ всегда существует;
• количество состояний небольшое.

Прием 4: "Чтобы решать задачу, ты должен думать как задача"

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

Прием 5: "Думаем вместе"

Этот прием применим только в командных контестах. Вдвоем или втроем начинайте по очереди озвучивать какие-то понятные факты про задачу. Например: "если n четное, то ответ всегда 0", "если n простое, то решать надо так" и так далее. Иногда ваши коллеги будут подхватывать идеи и развивать их, так можно и дожать идею решения задачи до конца.

Прием 6: "Подбери метод"

Попробуйте перебрать популярные алгоритмы или методы, которые хоть как-то могут оказаться применимы для задачи. Полезно посмотреть на ограничения по задаче. Зафиксировав метод, попробуйте подумать над решением предположив, что задача решается с применением этого метода. Надо рассуждать как-то так: "Пусть задача решается с помощью разделяй-и-властвуй. Тогда пусть мы рекурсивно решили задачу для левой и правой половине, осталось как-то объединить эти ответы, как бы это сделать..."

Прием 7: "Распечатать-посмотреть"

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

Иногда полезно выводить не только сам ответ, но и какую-то дополнительную информацию, например, способ получения ответа.

Прием 8: "Гуглим"

Этот прием можно применять, только если правила раунда/контеста это разрешают. Если задача на последовательности, то можно поискать ответы (см. прием 7) на сайте https://oeis.org/. Полезно понять формальную модель задачи и гуглить по правильным математическим терминам.

Вопрос к знатокам

А какие общеприменимые приемы используете вы?

Добрый день!

Уже совсем скоро состоится финал RCC этого года. 19-го сентября финалисты сразятся за звание чемпиона Russian Code Cup и призовой фонд от Mail.Ru. К моему сожалению, финал опять будет не совсем онсайт. Как я понимаю будут организованы две крупные площадки: одна в офисе Mail.Ru, а другая в ИТМО. Те, кто не приедут участвовать с этих площадок, примут участие через интернет независимо.

В этом году меня вновь пригласили поучаствовать в трансляции RCC (я уже пробовал себя в этой непривычной роли пару лет назад). Надеюсь, зрителям будет интересно.

Обычно, подобные трансляции проходят по какому-то такому сценарию:

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

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

Вопросы к вам:

• какие из активностей во время трансляции наиболее интересны?
• что не интересно?
• что можно добавить?
• как бы сделать так, чтобы было интересно и профессионалам и просто заинтересовавшимся?
• нужны ли, вообще, эти трансляции?

Короче, буду рад мнениям и идеям.

Добрый день.

Закончилась летняя школа "Сазанка-2015", 13-го августа разъехались последние участники. Я надеюсь, что всем им понравились эти 10 дней на берегу Волги близ Саратова. Многие подходили, жали руку и говорили, что это так. Спасибо )

Пусть завидуют все те, кто не был с нами: за эти дни мы ударно и очень подробно прошлись по основным строковым алгоритмам, устроили чемпионат мира по ЧГК, ходили в сауну с уже классическими для этих сборов арбузами и мороженным, приняли участие в безумном Дне Нептуна. Еще были настолки, забеги в Волгу, песни под гитару и традиционные 20 килограмм шашлыка под занавес.

Но, конечно, главное — это была учебная программа. Мной были прочитаны четыре лекции, каждый день мы осчастливливали участников 5-ти часовыми контестами как тематическими, так и нет (один был 4-х часовым), а на разборах никто не засыпал. Спасибо моему напарнику по организации сборов Илье IlyaLos Лосю за подготовку контестов и проведение разборов.

Закончен 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.com/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 рабочих дней, включающих ежедневные пятичасовые тренировки, разборы задач, дорешивания. Будет прочитана серия лекций. Учебная программа рассчитана на студентов младших и средних курсов, которые хотят достичь значительных успехов на соревнованиях по программированию.