ACM ICPC World Finals 2016. Phuket, Thailand.

Harvard University team: Johnny Ho (random.johnnyh), Scott Wu (scott_wu), Calvin Deng (dnkywin), Jelani Nelson (coach) (Robert L. Walton, Coach). Team got 3rd place (gold medal) and became North America region Champions.

Main contest.

What is it? Scott Wu communicates with an outside adviser? Team has more than three participants?

8 октября в 15:05 Мск состоится второй (финальный) раунд Intel Code Challenge.

Все пользователи Codeforces смогут принять в нём участие, как в обычном раунде. Обратите внимание на время начала раунда.

Для участников Intel Code Challenge.
В официальном зачете соревнования принимают участие финалисты (http://codechallenge.ipdnn.com/offsite), пишущие раунд на официальных площадках в Москве, Санкт-Петербурге, Нижнем Новгороде, Архангельске, Волгограде и Казани (http://codechallenge.ipdnn.com/onsite2).

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

Для участников раунда на Codeforces.
Для всех остальных пользователей Codeforces это будет обычный рейтинговый раунд. Раунд будет общим для обоих дивизионов.

Будут предложены 7 задач на русском и английском языках. Продолжительность раунда составит 3 часа. Разбалловка будет объявлена ближе к началу раунда.

Автор задач этого раунда я – Владислав Епифанов (vepifanov). Благодарю Алексея Шмелева (ashmelev), Александра Фетисова (AlexFetisov) и Владислава Исенбаева (winger) за прорешивание задач, координатора Codeforces Глеба Евстропова (GlebsHP) за помощь в подготовке раунда и Михаила Мирзаянова (MikeMirzayanov) за системы Codeforces и Polygon.

UPD. Разбалловка: 500-1000-1500-1500-2500-2500-2500. Поскольку раунд будет длиться 3 часа, то стоимости задач будут падать чуть медленнее чем в обычных раундах.

UPD. 2 Из-за возникших проблем в одном из мест проведения очного тура соревнования, старт раунда перенесён на 10 минут вперёд. Приносим извинения за доставленные неудобства.

Результаты Intel Code Challenge:

• Все участники
• Москва
• Санкт-Петербург
• Нижний Новгород
• Казань
• Волгоград
• Архангельск

UPD. 3

Финальное обновление рейтинга произойдет после удаления из таблицы нечестных участников.

Разбор будет выложен в воскресенье, 9 октября.

UPD. 4

Позравляем победителей Intel Code Challenge во всех городах!

Надеемся, что все участники остались довольны нашим соревнованием.

UPD. 5

Абсолютный победитель Intel Code Challenge, набравший наибольшее количество баллов среди всех участников соревнования — Евгений Капун (eatmore)!

Разбор задач

UPD. 6

Фотографии с очного тура соревнования.

1 октября в 17:05 Мск состоится отборочный раунд Intel Code Challenge. Официально в соревновании смогут принять участие ТОЛЬКО граждане РФ в возрасте от 18 до 27 лет. Все остальные пользователи Codeforces смогут принять в нём участие, как в обычном раунде.

Для участников Intel Code Challenge.
Для того, чтобы принять участие в Intel Code Challenge, необходимо ознакомиться с условиями проведения соревнования здесь http://codechallenge.ipdnn.com/ и здесь http://codeforces.net/blog/entry/47238 и зарегистрироваться в ДВУХ местах: здесь http://codechallenge.ipdnn.com/register и здесь http://codeforces.net/contests.

Для участников раунда на Codeforces.
Для всех остальных пользователей Codeforces это будет обычный рейтинговый раунд. Раунд будет общим для обоих дивизионов. Для участия в нем необходимо зарегистрироваться только в одном месте — во вкладке “Соревнования”.

Будут предложены 6 задач на русском и английском языках. Продолжительность раунда составит 2 часа. Традиционно, разбалловка будет объявлена ближе к началу раунда.

Автор задач этого раунда я – Владислав Епифанов (vepifanov). Благодарю Алексея Шмелева (ashmelev), Александра Фетисова (AlexFetisov) и Владислава Исенбаева (winger) за прорешивание задач, координатора Codeforces Глеба Евстропова (GlebsHP) за помощь в подготовке раунда и Михаила Мирзаянова (MikeMirzayanov) за системы Codeforces и Polygon.

UPD. Разабалловка: 500-500-1000-1500-2000-2500.

UPD 2.

Ниже, вы можете посмотреть текущие результаты Intel Code Challenge:

• Все участники
• Москва
• Санкт-Петербург
• Нижний Новгород
• Казань
• Волгорад
• Архангельск

Если вы не нашли себя в таблице вашего города, хотя регистрировались по этой ссылке http://codechallenge.ipdnn.com/register, то после окончания контеста, пожалуйста отправьте ваши данные на эту почту — [email protected].

UPD 3.

Приношу свои извинения за задачу С. Мы решили несколько упростить эту задачу в последний момент, и так оказалось, что в такой формулировке она уже встречалась ранее.

В любом случае, надеюсь, что второй раунд пройдет лучше чем первый!

UPD 4. Разбор задач

По этой ссылке можно посмотреть места проведения очного раунда — http://codechallenge.ipdnn.com/onsite2.

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

Ниже приведены списки участников, прошедших в очный тур соревнования:

Москва

Cанкт-Петербург

Нижний Новгород

Волгоград

Казань

Архангельск

Независимо от того, официально вы будете участвовать в Intel Code Challenge или нет, участие в раундах на Codeforces будет открыто для всех. У всех участников будет пересчитан рейтинг.

Корпорация Intel проводит соревнование по программированию Intel Code Challenge (http://codechallenge.ipdnn.com/), приуроченное к крупной технологической партнерской конференции Intel Partners Day.

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

В соревновании могут принять участие граждане РФ в возрасте от 18 до 27 лет.

Соревнование будет проводиться на Codeforces в два раунда: заочный и очный.
Для того, чтобы принять участие в Intel Code Challenge, необходимо ознакомиться с условиями проведения соревнования и зарегистрироваться по ссылке http://codechallenge.ipdnn.com/register. Город, в котором вы реально сможете принять участие во втором (очном) раунде, нужно выбрать при регистрации. Участники, зарегистрировавшиеся на Intel Code Challenge, будут разделены на группы по выбранному городу. В каждой группе 25 лучших участников первого раунда пройдут во второй этап.

Список городов, где будет проходить очный этап (тревел-грант не предусмотрен):

• Москва
• Санкт-Петербург
• Нижний Новгород
• Архангельск
• Волгоград
• Казань

Для участия в очном этапе конкурса необходимо будет иметь с собой ноутбук с возможностью доступа в Интернет. Длительность раундов составит 2 часа в отборочном и 3 часа в основном туре.

Раунды будут проведены по обычным правилам Codeforces.

График проведения соревнования:

• Окончание приема заявок: 1 октября 2016 г. в 17:00 по московскому времени
• 1-й этап (заочный) – 1 октября 2016 г.
• 2-й этап (очный) – 8 октября 2016 г.

По итогам очного этапа соревнований в каждом из городов проведения конкурса победители получат:

• 1 место: Микрокомпьютер Intel® Compute Stick и тревел-грант на посещение конференции «Intel Partners Day» 9-го ноября 2016 г. в Нижнем Новгороде
• 2 место: Фитнес-браслет
• 3 место: Внешний аккумулятор

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

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

UPD

Как указано на главной странице, заявка должна содержать следующую информацию:

• Фамилия, Имя и Отчество заявителя
• E-Mail
• ВУЗ или место работы
• Курс или должность
• Город проживания или учебы
• Город, в котором вы планируете проходить очный этап, если пройдете в финал
• Логин на Codeforces

Финал Facebook Hacker Cup 2012. В основном виды прилегающей местности.

Фото здесь.

Финал TopCoder Open в Голливуде (Флорида, США) 25 - 29 сентября 2011 года.

Финал Russian Code Cup в Москве 17-18 сентября 2011 года.

Фото здесь.

Поездка сборной команды Поволжья на финал Google Code Jam 2011 в Токио.

A. Башни
Общее количество башен равно количество различных чисел в данном наборе. Чтобы получить высоту наибольшей башни, можно было подсчитать для каждой длины количество брусков с такой длинной, и из этих чисел выбрать максимальное.

B. Компьютерная игра
Ограничения в задаче позволяли решать её следующим образом: будем хранить текущее количество здоровья у босса, и суммарный наносимый урон по нему. На очередном шаге выберем из еще не использованных свитков такой, который можно использовать на текущей секунде. Из всех таких, найдем свиток, который наносит больше всего урона, и применим его. Если в какой-то момент мы не смогли использовать ни один из свитков, и суммарный урон не превышает регенерацию, то выводим, что ответа не существует. Иначе продолжаем итерировать алгоритм, пока количество жизни босса не станет неотрицательным.

C. Древнеберляндский язык
Одно из самых простых для понимания решений в данной задаче выглядит так: отсортируем строки по возрастанию длины, при этом запомнив их номер в исходном списке. Будем последовательно строить наш набор, начиная с самых коротких строк: строками длины один могут быть только строки “0” и “1”. Если количество строк длины один в наборе больше двух, следовательно, ответа не существует. Добавим нужное количество строк длины один в ответ на свои места (для этого мы запомнили их номера), и удалим из текущего списка. Затем посмотрим на строки длины два: каждую из оставшихся строк длины 1 можно продолжить двумя способами (дописав к каждому из них символы 0 и 1). Добавим нужное количество строк длины два в наш набор, и снова увеличим длину оставшихся строк на единицу. Будем продолжать этот процесс до тех пор, пока не составим набор целиком. Можно заметить, что если в какой-то момент число допустимых строк превысило количество оставшихся, то лишние строки можно проигнорировать и таким образом время работы составит O(N * максимальную длину из входного набора).

D. Расписание занятий

Эта задача решается методом динамического программирования:

состоянием динамики будет пара чисел – номер аудитории и количество групп, занимавшихся на первой паре в аудитории с номером не превосходящем текущего, для которых вторая аудитория еще не определена. Для каждого состояния будем перебирать количество групп, у которых вторая пара будет проходить в текущей аудитории. При добавлении ответа из нового состояния, нужно домножить его на соответствующие биномиальные коэффициенты (количество способов выбрать группы, у которых первая пара будет в следующей аудитории - X_i + 1, и количество способов выбрать группы, у которых вторая пара будет в текущей аудитории).

E. Испытание для вождя

Сперва по данной раскраске построим следующий граф: каждой клетке сопоставим вершину того же цвета, что и сама клетка. Между соседними клетками проведем ребро веса 0, если клетки одного цвета, и веса 1, если разного. Теперь для каждой клетки посчитаем кратчайшее расстояния из нее, до самой удаленной черной клетки (обозначим его D). Нетрудно видеть, что можно построить последовательность из D + 1 перекрашивания приводящую к искомой раскраске:

• на первом шаге покрасим все клетки на расстоянии меньше либо равном D в черный цвет

• на втором шаге покрасим все клетки на расстоянии меньше либо равном D - 1 в белый цвет

• и т. д.

Из всех клеток, выберем ту, для которой это расстояние минимально, и это расстояние увеличенное на единицу будет ответом на задачу.

• Русская версия
• Английская версия