Привет!

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

Testlib

• testlib переехал на GitHub, выпущена новая версия 0.9.9 с поддержкой C++11. Добавлены генераторы двудольных графов, корневых и простых деревьев.

Polygon

• Добавлена базовая поддержка групп тестов. Теперь вы можете для каждого теста указать его группу, запускать invocations по группам, добавлены строки с summary по группам на странице просмотра invocation'а. Если для теста указана группа, она появится в дескрипторе задачи (например <test cmd="gen 1 2" group="testGroup" method="generated"/>). Эта функциональность может оказаться полезной при подготовке задач для школьных олимпиад.
• Добавлена возможность просмотра условий и валидатора задачи/контеста на одной странице. Это значительно упрощает нахождение ошибок в переводах и валидаторе (раньше для этого нужно было открывать их в разных вкладках и постоянно переключаться между ними, что не очень удобно). На странице просмотра условий добавлена ссылка "Review":
  
  На странице контеста соответствующая ссылка находится на боковой панели:
  

Codeforces

• Теперь пропустить важное сообщение во время раунда стало еще сложнее — сообщения дополнительно показываются с использованием Notification API.
• Исправлен баг в API: в методе contest.hacks были перепутаны defender и hacker.
• Исправлен баг со сбрасыванием фильтра статуса. Такое иногда возникало когда запрос уходил на другой сервер Codeforces.
• Исправлен баг с переполнением local storage. Если у вас вдруг переполнялся local storage, нужно было выполнить localStorage.clear(); в консоли браузера. Теперь Codeforces использует local storage аккуратнее.
• При взломе задачи теперь подсвечивается синтаксис:
  
• При просмотре посылки теперь показываются невидимые символы, так как раньше иногда было непонятно почему приходит WA:

Было	Стало

• Вам больше не требуется загружать изображения на сторонние сайты, теперь вы можете сделать это сразу при редактировании поста. Сразу под содержимым поста вы можете выбрать несколько изображений, для каждого из них сгенерируется ссылка, которую нужно будет использовать для вставки в текст:
  
• Улучшена возможность категоризации постов, в частности важные материалы (документация, правила и проч.) Codeforces скоро не нужно будет искать в блогах, они будут структурировано доступны на специальной странице.
• Добавлена возможность дать права на редактирование поста списку пользователей, пока такая возможность будет доступна списку авторитетных пользователей, которые смогут самостоятельно вносить правки в посты с документацией, туториалами и подобными материалами.
• Улучшена проверка генераторов на устойчивость: напоминаем, что генераторы при взломах нужно писать таким образом, чтобы при каждом запуске они выдавали один и тот же input, теперь это проверяется более надежно. Не инициализируйте генераторы случайных чисел в генераторах текущим временем!
• Добавлена возможность просмотра истории правок у поста. Историю можно сделать доступной либо для всех пользователей, либо только для редакторов. По умолчанию для новых постов она будет доступна всем. Если вы разрешаете просмотр истории, то при изменении текста вы сможете опубликовать автокомментарий со ссылками на старую версию, новую версию, а также на просмотр изменений.
• Теперь те участники, кто не участвовал в рейтинговых раундах более 6 месяцев удаляются из рейтинга. На них всё еще можно посмотреть по ссылке РЕЙТИНГ (ВСЕ). При подсчете рейтингов стран/городов/организаций они тоже теперь не учитываются.

И это еще не все! В скором времени ожидайте еще больше улучшений, к примеру ведется работа по данному вопросу и не только.

Привет, Codeforces!

Мы рады сообщить, что 4 июня в 19:30 MSK состоится раунд Codeforces #306, авторами которого являюсь я (Адилет Жаксыбай), и Тимур Сытдыков (Timur_Sitdikov). Раунд будет рейтинговым для участников второго дивизиона, участники первого дивизиона могут, как обычно, поучаствовать в нем вне конкурса.

Хочется выразить благодарность всем тем, кто помог нам с подготовкой раунда: Максиму Ахмедову (Zlobober), который помог нам с подготовкой задач, Бекжану Касенову (BekzhanKassenov) и Сергею Лазареву (SergeyLazarev), протестировавшим контест, и Марии Беловой (Delinur), которая перевела условия на английский язык. Отдельное спасибо Михаилу Мирзаянову (MikeMirzayanov) за создание платформ Codeforces и Polygon.

Кстати, насколько нам известно, Timur_Sitdikov — первый участник с Узбекистана, принявший участие в подготовке Codeforces раунда. Мы надеемся, что все пройдет хорошо :)

Всем удачи!

UPD Разбалловка будет динамической.

UPD2 Разбор можно найти здесь.

UPD3 Поздравляем победителей:

1. mff

2. I_Love_Nodir.Daminov

3. tun

4. I_love_Ngoc_cmn_Thuy

5. goodhope

Раунд закончен, спасибо всем, кто принял участие!

Пару месяцев назад мы провели очередную межвузовскую командную олимпиаду. Тренировка по задачам этого контеста состоится в воскресенье, 7 июня, в 13.00 по Московскому времени.

Авторами задач данного соревнования являлись Sinner, dalex, Slamur, также неоценимую помощь в подготовке оказали craus, Shlakoblock и I_love_natalia.

Зайти в контест вы сможете на этой странице: Тренировки Codeforces

Список предыдущих наших контестов:

• 2012, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2013, VI Самарская областная межвузовская олимпиада по программированию
• 2013, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2014, VII Самарская областная межвузовская олимпиада по программированию
• 2014, Отборочный контест СГАУ на четвертьфинал ACM ICPC

Rules

The draft for this year's rules is available on the competition website.

As it is highlighted, there are two important changes. First of all, it is officially confirmed that Java is among the languages that can be used at IOI 2015. Secondly, since the JVM uses threads "under the hood", threads are now allowed for submissions in any programming language, but the runtime of a solution is counted as the sum of the runtime of all threads.

I don't think that these changes are really significant to any participants not using Java, because there is no point in using threads if the runtime for each thread is counted separately.

The rules promise "generous time limits", which is interesting, because experience shows that Java solutions tend to be slower even when simple wall time is considered, but counting all the JVM threads separately could result in an even more significant slowdown (compared to other languages).

I'm a little bit concerned that this might mean that we're going to see 20s time limits again (and, consequently, long testing queues, just like during IOI 2013). This happened at the Baltic Olympiad in Informatics this year, where the jury had "optimal" Java solutions working for ~10-15s on maxtests, while C/Pascal solutions spent less than 0.5s, and the TLs were nevertheless set at around 20s (which did make feedback unavailable for a short period of time during the contest, but the jury dealt with it quickly).

Another change in rules which surprised me a bit is that the graders are not guaranteed to use the same hardware as contestants' machines. But then again, with full feedback on 100 submissions per task, perhaps this is not a very serious issue.

Syllabus

The IOI syllabus is a document describing topics (most importantly, algorithms) which IOI participants are expected to know, as well as those that must not be necessary to solve an IOI task.

The new version of the IOI syllabus is already available, and a list of changes should be available soon on misof's IOI Syllabus page.

Meanwhile, most of the changes in the syllabus appear to consist of moving stuff from "Explicitly excluded" to other parts of it, most often "Excluded, but open to discussion". I understand this new category as "these are still excluded, but we should consider including them in IOI 2016 or later", although one should be cautious with this, since the syllabus is not binding for the task authors anyway, so, if someone comes up with a really cool task concerning an excluded topic, it could theoretically be allowed, especially if the topic is "open for discussion".

Another interesting change is that planar graphs were moved from "explicitly excluded" to "included, not for task description", although planarity testing is still excluded. Bipartite matching was also moved from "explicitly excluded" to "included, not for task description", and maxflows and strongly connected components are now "excluded, open for discussion". Balanced binary search trees are now included, and string hashing is "excluded, but considering inclusion".

I hope that this overview of the changes will be useful to other IOI participants (or teachers, or spectators), and I'm looking forward to hearing more information from the organizers.

The changes in the syllabus seem to reflect the fact that with every year, more and more algorithms are becoming "widely known", and the olympiad organizers are trying to reflect this, which means that the olympiad is getting harder over time. Perhaps the organizers have decided that now is the right time to formalise this by including more advanced algorithms in the syllabus (as hinted by the results of the participant surveys in 2013 and 2014). However, at this particular moment, most of the changes seem to be in the "excluded, but open for the discussion" category, and it is certain that many discussions will be held on this topic, both at IOI and outside. Perhaps a part of this discussion might happen right here, on Codeforces.

Привет! Меня зовут Николай, я евангелист Stack Overflow на русском.

С радостью спешу сообщить, что совсем недавно был запущен Stack Overflow на русском по адресу http://ru.stackoverflow.com/. Stack Overflow на русском — это инициатива команды Stack Exchange, автора англоязычного Stack Overflow.

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

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

Буду рад услышать ваши отзывы и предложения!
—
С уважением,
Николай

Добрый день.

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

Всем привет!

В это воскресенье 31 мая в 13:00 по Москве состоится третий квалификационный раунд Russian Code Cup. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Третий раунд — последний шанс для тех, кто еще не успел пройти квалификацию, так что не пропустите! Отборочный раунд состоится в 13:00 14 июня, в него проходят 200 лучших участников из каждого квалификационного раунда.

Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте http://russiancodecup.ru/ (регистрация будет открыта до начала третьего квалификационного раунда).

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на [email protected]

Приглашаем всех принять участие в квалификационном раунде Russian Code Cup и желаем всем удачи!

Codeforces round #305 is gonna take place soon and I'm the writer.

After my previous contest that many people think it was a hard contest, I prepared an easy contest to cheer you up!

I want to thank Haghani for testing this round, Zlobober for help me prepare this round and his great advises, Delinur for translating problem statements into Russian, mruxim and Yasser Ahmadi Phoulady (Rasta) for their advises and ideas, HosseinYousefi for helping me choose legends and graphics and MikeMirzayanov for great Codeforces and Polygon platform and guys from Physics Olympiad that kept disturbing me while preparing this round.

This is my second official round and I hope you enjoy it.

The main character of this round is gonna be Mike (I didn't say MikeMirzayanov :D).

Also you'll meet Xaniar and Abol.

I wish you all Successful hacks and Accepted solutions and high ratings.

Scoring will be posted soon.

GL & HF!

UPD: Scoring is:

• Div.2: 500-1000-1750-2000-2750
• Div.1: 750-1000-1750-1750-2500

UPD2: Due to technical reasons we moved the round by 5 minutes.

UPD3: Contest has just ended. You can find the editorial here.

UPD4: System testing is done.

Congratulations to the winners, specially dreamoon_love_AA that got to his goal !

Div.1 winners:

1. dreamoon_love_AA
2. HYPERHYPERHYPERCUBELOVER
3. EvenImage
4. YuukaKazami
5. subscriber

Div.2 winners:

1. fromWork
2. IloveGoodness
3. norge
4. metal_knight
5. williamzpf

See you in the next rounds.

This is my first attempt at writing something useful, so your suggestions are welcome.

Most participants of programming contests are familiar with segment trees to some degree, especially having read this articles http://codeforces.me/blog/entry/15890, http://e-maxx.ru/algo/segment_tree (Russian only). If you're not — don't go there yet. I advise to read them after this article for the sake of examples, and to compare implementations and choose the one you like more (will be kinda obvious).

Segment tree with single element modifications

Let's start with a brief explanation of segment trees. They are used when we have an array, perform some changes and queries on continuous segments. In the first example we'll consider 2 operations:

1. modify one element in the array;
2. find the sum of elements on some segment.