Язык этого раунда — Picat, во многом похожий на Prolog. Мы постарались подобрать задачи так, чтобы большинство из них было удобно решать с использованием декларативного подхода.

Традиционная программа A+B (числа A и B разделены пробелом) выглядит следущим образом:

main =>
  A = read_int(),
  B = read_int(),
  C = A + B,
  println(C).

Основной источник информации о языке — сайт http://picat-lang.org/. Используется версия 0.9.

Привет, Codeforces!

26 марта 2015 года в 19:30 MSK состоится очередной раунд Codeforces #297 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Это мой уже третий Codeforces раунд, надеюсь, я вам еще не сильно надоел.

Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon и за идеи некоторых задач, а также моим старинным друзьям Павлу Холкину (HolkinPV), Илье Лось (IlyaLos), Виталию Кудасову (kuviman) и Артуру Свечникову (ikar) за прорешивание задач и вычитывание условий.

Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD Стоимость задач будет плавной динамической с шагом в 250 баллов. Подробнее об этом вы можете прочитать здесь. Задачи будут расположены в порядке предполагаемого возрастания сложности.

UPD2 Соревнование завершено! Спасибо всем кто участвовал!

UPD3 Разбор уже ждет вас здесь.

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

1. cikofte
2. fcspartakm_2
3. stealife
4. GITLER228
5. alpq654321

Всем привет! Может быть, эта тема уже обсуждалась, но по запросу "random" ничего похожего на Codeforces не нашел.

Предыстория. Хотели с Сашей (demon1999) изучить декартово дерево. Для инициализации приоритетов рекомендуется использовать случайные числа, чтобы высота дерева не была очень большой. Соответственно, надо эти числа как-то получить. Я совсем не разбираюсь в структурах данных, поэтому не задумывался, насколько плохо будет дереву (и будет ли), если приоритеты нескольких вершин будут одинаковыми. Поэтому на всякий случай хотелось сделать их попарно различными (чего не гарантирует простое использование rand() при создании очередной вершины). Предложил следующий, "надежный" и "проверенный" метод — создать массив из N чисел, инициализировать его числами от 0 до (N-1) соответственно, применить к нему random_shuffle — и мы получим N различных ключей в случайном порядке.

История. Саша стала сдавать задачи и на практике оказалось, что в нескольких задачах такой подход достаточно стабильно приводит к вердикту Time Limit Exceeded, в то время как простейшая инициализация pr=rand() получала Accepted. Стало очень интересно, почему так происходит, да и вообще STL не склонен быть причиной каких-либо ошибок. После несложных исследований оказалось, что (возможно, не это причина TLE, но тем не менее) random_shuffle перемешивает массив не совсем случайным образом.

Всем привет!

Уже в эту субботу, 28 марта в 18:00 состоится первый квалификационный раунд Russian Code Cup 2015. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Те, кому удача в субботу не улыбнется, а также те, кто по тем или иным причинам не смогут принять участие в раунде, смогут попробовать свои силы во втором отборочном раунде 25 апреля в 12:00, а при необходимости и в третьем – 31 мая в 13:00. В отборочный тур, назначенный на 13:00 14 июня, пройдут 200 лучших участников из каждого квалификационного раунда.

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

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

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

В субботу, 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). Подробнее о ней можно прочесть здесь.

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

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

Алгоритм Куна ищет паросочетание в двудольном графе за O(VE). Реализация, данная на emaxx, укладывается в такой шаблон:

forn(i, n) {
  fill(used, 0);
  dfs(i);
}

Я обычно пишу так:

fill(used, 0);
forn(i, n) 
  if (dfs(i))
    fill(used, 0);

То есть, обнуляю пометки только если нашёл дополняющую цепь. Теперь Кун работает за O(|M|·E), где |M| — размер максимального паросочетания.

Решение можно ускорить ещё как минимум в 2 раза, используя жадную инициализацию паросочетания. Идея: применяем Куна не к пустому паросочетанию, а к паросочетанию размера хотя бы |M| / 2. Кстати, |M| / 2 — оценка снизу, если перед жадной инициализацией сделать random_shuffle, жадность найдёт паросочетание чуть побольше, и Кун будет работать чуть быстрее.

Новое для меня

Оказалось, можно заставить Куна работать ещё в несколько раз быстрее...

fill(pair, -1);
for (int run = 1; run; ) {
  run = 0, fill(used, 0);
  forn(i, n)
    if (pair[i] == -1 && dfs(i))
      run = 1;
}

То есть, теперь я не обнуляю пометки даже если нашёл дополняющую цепь.

Я успел потестить на нескольких задачах, например, на задаче про доминошки. Эффект: новая идея без жадной инициализации в 3 раза быстрее старой идеи с жадной инициализацией. Можно скачать тесты и решения и поиграться самостоятельно. Думаете, в доминошках специфический граф? Потестил на произвольном двудольном графе, эффект "на макс тесте в 10 раз быстрее".

Мне эта модификация Куна чем-то напоминает Хопкрофта-Карпа, т.к. получается, что мы за O(E) находим не один путь, а несколько. Непонятно, что стало с асимптотикой алгоритма. Может быть, она тоже улучшилась?)

Спасибо за внимание.

Всем привет!

Идет регистрация на крупнейшую в России открытую ежегодную олимпиаду по спортивному программированию Russian Code Cup 2015. Первый квалификационный тур состоится уже в субботу, 28 марта, в 18-00 и продлится 2 часа.

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

Квалификационные и отборочный раунды пройдут на сайте Russian Code Cup. Первый квалификационный раунд состоится 28 марта в 18:00, второй – 25 апреля в 12:00, третий – 31 мая в 13:00. Причем программисты, не прошедшие квалификацию с первого или второго раза, могут попробовать свои силы в следующих раундах. В отборочный тур, назначенный на 13:00 14 июня, пройдут 200 лучших участников из каждого квалификационного раунда. А 50 программистов, преодолевших «сито» отбора, померятся силами в финале, который состоится в 19 сентября 2015 года. Форма и время проведения финала будут объявлены после 1 июня. Победитель Russian Code Cup получит главный приз – 300 тысяч рублей; участник, занявший второе место, — 150 тысяч рублей; приз за третье место – 90 тысяч рублей, обладатели 4-10 места получат по 30 тысяч рублей. Кроме того, призы достанутся всем участникам, дошедшим до финала.

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

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

Приглашаем всех русскоязычных участников сообщества Codeforces принять участие в Russian Code Cup 2015 и хотим со своей стороны поздравить Codeforces с 5-летием! Мы воспользовались возможностью поддержать Codeforces переводом в $1000. Нам приятно внести свой вклад в будущее платформы. Желаем Codeforces новых рекордов и достижений!

Всем привет! Сегодня вечером в обычное время состоится Codeforces Round #296 для обоих дивизионов, автором которого являюсь я.

Готовить задачи мне помогали мои сокомандники, члены команды Moscow SU Trinity sankear и malcolm, а также множество ценных советов дал MikeMirzayanov, за что им всем большое спасибо. Переводом условий мы обязаны нашей бессменной переводчице Delinur.

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

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

UPD: разбалловка — стандартная.

UPD2: в связи с техническими трудностями раунд перенесён на 15 минут вперёд. Приносим извинения за непредвиденную задержку.

UPD3: Приносим свои извинения за проблему с задачей Div1-D. Претест #16 не удовлетворял ограничениям n, m, k <= 200000. Системное тестирование для первого дивизиона будет отложено. Если вы считаете, что этот тест серьёзно повлиял на ваши результаты, вы можете написать мне сообщение, и мы сделаем раунд для вас нерейтинговым.

Системное тестирование во втором дивизионе произойдёт в ближайшее время в обычном порядке.

UPD4: Тестирование завершено. Поздравляем победителей!

Div1:

1. piob

2. PavelKunyavskiy

3. dreamoon_love_AA

4. mnbvmar

5. aid

Div2:

1. happyBirthDayBeni

2. ExfJoe

3. _0029

4. tudort

5. kill-z

UPD5: Был добавлен разбор на английском языке.

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

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

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

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

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

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

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

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

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