VK Cup 2015

Социальная сеть ВКонтакте анонсировала чемпионат по программированию VK Cup ^[1] в обновленном формате. Соревнование ориентировано на любителей алгоритмов, структур данных и просто фанатов problem-solving. К участию в чемпионате приглашаются те, кому уже исполнилось 14 лет, но не исполнилось 24 на момент регистрации. Кроме того, рабочий язык чемпионата — русский. В отличие от других подобных соревнований, участникам предлагается работать в командах по двое. Соревнование будет проходить на платформе Codeforces при содействии Саратовского ГУ.

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

• 1 место — 1048576 рублей
• 2 местo — 524288 рублей
• 3 местo — 262144 рубля
• 4-8 места — 131072 рубля
• все участники Раунда 3 — фирменные футболки.

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

Регистрация на VK Cup 2015 уже открыта и продлится до окончания Квалификации 2. Даты и квоты прохождений указаны на картинке:

Детали Уайлд-кард раунд 1 и Уайлд-кард раунд 2 раундов пока держатся в секрете, но, напомним, в первом VK Cup 2012-го года:

• в Уайлд-кард раунде 1 ^[2] участникам предлагалось на скорость решать задачи на не особо популярном стековом функциональном языке Factor — то есть задачей участников за время раунда было освоить новый язык и написать на нем решения задач,
• а в Уайлд-кард раунде 2 ^[3] участникам предлагалась за неделю максимально продвинуться в решении исследовательской задачи на оптимальное расположение прямоугольников.

Если ваш возраст от 14 до 23 и вы любите программировать и решать задачи, то регистрируйте в разделе VK Cup 2015 на Codeforces ^[1]. Обещаем интересные задачи!

Вот примеры нескольких задач из VK Cup 2012:

• Такси

  После окончания уроков n групп школьников вышли на улицу и собрались ехать домой к Поликарпу на празднование его дня рождения. Известно, что i-ая группа состоит из si друзей (1 ≤ si ≤ 4), которые не хотят расставаться по пути к Поликарпу. Решено ехать на такси. Каждая машина может вместить не более четырех пассажиров. Какое минимальное количество машин потребуется школьникам, если каждая группа должна целиком находиться в одной из машин такси (но одна машина может вмещать более чем одну группу)?

  Отправить решение в тестирующую систему можно со страницы раунда в Codeforces ^[4].

• Скидки

  Как-то раз Поликарп по пути домой заглянул в супермаркет. Оказалось, что в супермаркете проходит акция по продаже табуреток. Условия акции таковы: если в корзинке с купленными товарами есть хотя бы одна табуретка, то на минимальный по стоимости товар из корзинки предоставляется скидка 50% (то есть он становится дешевле в два раза). Если товаров минимальной стоимости несколько, скидка предоставляется только на один из них!

  У Поликарпа есть k корзинок, и он хочет скупить все табуретки и карандаши из супермаркета. Помогите ему распределить табуретки и карандаши по корзинкам так, чтобы суммарная стоимость товаров (с учетом скидок) была как можно меньше.

  Поликарп обязан использовать все k корзинок для покупки товаров, ни одна корзинка не должна остаться пустой. В каждой корзинке может быть произвольное количество табуреток и/или карандашей.

  Ограничения: k и n от 1 до 1000. Работа программы должна уложиться в пару секунд.

  Отправить решение в тестирующую систему можно со страницы раунда в Codeforces ^[5].

• Электронное правительство

  В рамках проекта «Электронное правительство» лучшим программистам страны Распиляндии поручили создание системы автоматизации сбора статистики и анализа прессы.

  Известно, что членами правительства Распиляндии может стать любой из k граждан. Их фамилии — a1, a2, ..., ak. Все фамилии различны. Изначально в правительство входят все k граждан из этого списка. Система должна поддерживать следующие возможности:

  • Включить гражданина ai в состав правительства.
  • Исключить гражданина ai из состава правительства.

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

  Ограничения: n и k от 1 до 10⁵. Работа программы должна уложиться в пару секунд. Отправить решение в тестирующую систему можно со страницы раунда в Codeforces ^[6].

Для решения задач могут быть использованы любые из поддерживаемых на Codeforces языков: C/C++, Pascal, Java, C#, Python, Ruby, Perl, PHP, Haskell, Scala, OCaml, Go, D или JavaScript.

В 2012-м году VK Cup был проведен первый раз. Мои воспоминания о чемпионате можно прочесть в посте на здесь ^[7].

Ссылки:

• страница VK Cup 2015 на Codeforces, ^[1]
• страница VK Cup 2012 на Codeforces, ^[8]
• задачи первого ^[4] и второго ^[9] квалификационных раундов VK Cup 2012,
• группа ВКонтакте ^[10].

Основатель и руководитель Codeforces,
Михаил Мирзаянов

Автор: MikeMirzayanov

Источник ^[11]