Всем привет!

Компания AIM Fund поздравляет Codeforces с 5-летием! Поскольку многие наши сотрудники занимаются олимпиадным программированием, мы поддержали краудфандинг-кампанию Codeforces. Мы ценим то, чему мы здесь научились и благодарны за те приятные минуты, что мы провели решая интересные задачи. В течение месяца мы планируем провести свой раунд и постараемся порадовать вас хорошими задачами.

Наша компания занимается проп-трейдингом, ключевыми понятиями в нашей работе являются big data, low latency и high frequency. Команда состоит в основном из выпускников мехмата МГУ и МФТИ. Более подробную информацию можно прочитать на сайте aimfund.ru

Привет, Codeforces!

Мы рады возможности поздравить вас с пятилетием! Codeforces — замечательная соревновательная и учебная площадка для всех тех, кто интересуется алгоритмами и структурами данных. Нам приятно поддержать Codeforces. Желаем процветать, радовать нас раундами и с нетерпением ждем интересных нововведений. Ура!

Пользуясь, обещанной возможностью рассказать о себе в посте, мы обращаемся к вам.

Недалеко от Казани появился новый российский город — Иннополис. Это проект международного уровня с ключевой специализацией на высокие технологии. Здесь идет создание экосистемы для привлечения лучших специалистов из области высоких технологий для рождения и реализации смелых инновационных идей, которые в дальнейшем станут основой инновационного развития России. Перспективная численность города — 150 000 человек.

Интеллектуальным ядром города стал IT-университет, который специализируется на подготовке высококвалифицированных кадров в области современных информационных технологий. Международный статус университета позволяет привлекать преподавателей из TOP-100 университетов мира для обучения студентов, а программы обмена дают возможность получать знания в ведущих IT-университетах мира:

• Carnegie Mellon University (№3, QS World University Rankings by Subject 2014 — Computer Science & Information Systems)
• ETH Zurich
• Национальный университет Сингапура (National University of Singapore)
• Университет Амстердама (University of Amsterdam, Нидерланды)
• KAIST (Korea Advanced Institute of Science and Technology, Республика Корея)
• Миланский политехнический университет (Polytechnic University of Milan, Италия)
• Институт EURECOM (Франция)

В этом году Университет Иннополис проводит отбор талантливых студентов IT-специальностей на учебные программы бакалавриата (3-4 курс) и магистратуры. Всё обучение проходит на английском языке и по окончании Университет гарантирует выпускникам трудоустройство в компаниях-партнерах. При успешном прохождении отбора студент получает грант, который покрывает до 100% стоимости обучения. Студенты Университета живут на территории современного кампуса и получают стипендию от 12 до 36 тысяч рублей в месяц.

UPD Приём заявок завершён. С момента публикации статьи к проекту присоединились более 150 участников. Если кто-то подавал заявку по почте и не получил ответ — свяжитесь со мной через личные сообщения codeforces.

Вы всё ещё в div2, но мечтаете попасть в div1? Учёба занимает много времени, и олимпиадные задачи получается решать редко? Чувствуете, что постоянно решаете простые задачи, но никак не продвигаетесь к решению сложных?

Если Вы ответили “Да” на любой из этих вопросов, и хотите изменить текущую ситуацию, тогда эта статья для Вас!

Прочитав её, Вы узнаете

• какие особенности человеческой психики можно использовать для оптимизации процесса тренировок;

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

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

Знакомая ситуация сразу после олимпиады: эх, опять готовился к олимпиаде только последние 3 дня, а вот если бы весь год перед этим готовился — точно бы прошёл на Всерос.

Как же осуществить мечту о тренировках круглый год?

Можно использовать следующие особенности человеческой психологии:

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

Язык этого раунда — 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) находим не один путь, а несколько. Непонятно, что стало с асимптотикой алгоритма. Может быть, она тоже улучшилась?)

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