Добрый день!

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. Внеконкурсное участие тоже требует соблюдение всех правил, в случае нарушения команда может быть дисквалифицирована с Чемпионата.

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

Hi everyone!

If you still remember, 5 months ago I added the ACM ICPC Vietnam National 1st Round into Gym.

This weekend, we're going to add the 2nd round from our National contest. We hope that this will help ease your hunger for contests :)

• The contest was designed to be harder than last time
• It consists of around 10 problems, and lasts for 5 hours.
• Teams are welcomed.
• Normal ACM rules is used.
• To those who's going to ask if it is rate): No contest from gym is rated.

The gym contest is prepared by laoriu, khuebeo, ngfam_kongu and me, I_love_Hoang_Yen. The problem setters are Vietnamese professors and some ex-ACM ICPC competitors.

We hope that there's going to be at least one interesting problem for everyone. Please join & have fun with us! May luck be with you :)

UPD: Contest is over. This is scoreboard of real contest: link

UPD2: Solution to some problems: link

UPD3: It turns out that the author's solution for problem F is wrong. I'm very sorry for that and I'm trying to fix it. I hope that it didn't make too much impact for any team. The bug was found by team Orz xyz111 (apia, PoPoQQQ1, alpq654323). You are really awesome, not only solve the problem, but solved it despite the fact that the test might be wrong.

UPD4: Solutions of F has been rejudged. It looks like the mentioned team was the only team who was affected. I am very sorry for that.

Всем привет!

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

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

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

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

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

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

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

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

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

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

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

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

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

Привет, Codeforces!

2 марта в 10:00 MSK состоится раунд #295 для участников из обоих дивизионов.

Раунд состоится практически одновременно с олимпиадой Зимней Компьютерной Школы на схожем комплекте задач. Авторы задач — я (Endagorion) и Евгений Савинов (savinov). В подготовке задач принимали участие члены технического комитета Зимней Компьютерной школы: Георгий Чебанов (gchebanov), Филипп Рухович (DPR-pavlin), Александр Машрабов (map), Сергей Киян (sokian), Константин Семенов (zemen), Кинан Альсармини (Sarkin).

Спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский язык, Михаилу Мирзаянову (MikeMirzayanov) за вклад в развитие программирования путем создания систем Codeforces и Polygon.

Разбалловка в обоих дивизионах стандартная: 500-1000-1500-2000-2500.

Обратите внимание, что поскольку олимпиада ЗКШ на похожих задачах заканчивается позже раунда Codeforces, мы просим вас не обсуждать в комментариях задачи и решения до 14:10 MSK сегодняшнего дня. Также до этого времени будет закрыт просмотр кода других участников. Разбор также появится после этого времени.

UPD: все, можно обсуждать. =)

UPD2: наконец появился разбор ( теперь и на русском!).

Также поздравляем победителей в Div.1:

1. Petr
2. hos.lyric
3. Syloviaely
4. andrew.volchek
5. xyz111

Отдельно поздравляем Petr и rng_58, решивших самую сложную задачу E!

Привет, Codeforces!

Меня зовут Адилет Жаксыбай, и вместе с Бекжаном Касеновым (BekzhanKassenov) мы являемся авторами раунда Codeforces #294, который состоится 28 февраля в 16:00 MSK. Это наш первый раунд Codeforces, и мы рады пригласить всех поучаствовать в нем. Раунд будет рейтинговым для участников второго дивизиона, участники первого дивизиона могут, как обычно, поучаствовать в нем вне конкурса.

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

Хочется выразить благодарность всем тем, кто помог нам с подготовкой раунда: Максиму Ахмедову (Zlobober), который помог нам с подготовкой задач, Нурлану Канапину (kt-9) и Мансуру Кутыбаеву (mexmans), протестировавшим контест, и Марии Беловой (Delinur), которая перевела условия на английский язык.

Отдельное огромное спасибо Михаилу Мирзаянову (MikeMirzayanov) за создание платформ Codeforces и Polygon. Мы бы хотели поздравить Codeforces с недавно прошедшим пятилетием. Нам, авторам раунда, невероятно повезло начать заниматься олимпиадами по программированию, когда сайт Codeforces уже существовал, и он внес невероятный вклад в наше развитие!

Нам очень нравится, когда авторы задач пишут в анонсе немного о себе (призываем всех авторов поступать также) — это дает лучше почувствовать, что за задачами стоят реальные люди. Поэтому напишем немного о нас. Мы являемся студентами Назарбаев Университета (nu.edu.kz) — нового университета с английским языком обучения в столице Казахстана, Астане. В ACM-ICPC наш университет участвует лишь с 2012 года, но тем не менее команда с NU уже два раза проходила в финал в 2014 и 2015 году. Мы надеемся и в будущем держать планку спортивного программирования на высоком уровне.

Всем удачи!

UPD Разбалловка будет стандартной (500 — 1000 — 1500 — 2000 — 2500)

UPD2 Разбор можно найти тут

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

1. AkashiSeijuro

2. fmzbtf937

3. mxh3777

4. IGandWFin2019

5. ruozha2 & i_hate_t0nzuk

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