Кажется, Google Code Jam ко мне не ровно дышит, и может даже немножко выделяет :)

400A — Инна и право выбора

Не сложная задача на перебор. Переберем параметр a. Если 12 не кратно a, пропустим. Вычислим b = 12 / a. Переберем столбец (от 1 до b) и для всех его клеточек (i, j) проверим, стоит ли там X. Клеточка (i, j) — это ((i–1) * a + j) -ый элемент строки.

400B — Инна и новая матрица конфет

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

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

400C — Инна и гигантская матрица конфет

Заметим, что повороты по часовой можно брать по модулю 4. Горизонтальный — по модулю 2, а против часовой — по модулю 4, причем 1 такой поворот — это 3 поворота по часовой.

Поворот по часовой: newi = j; newj = n–i + 1 не забываем swap(n, m).

Поворот горизонтальный: newj = m–j + 1

400D — Дима и бактерии

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

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

400E — Инна и бинарная логика

Будем решать задачу побитово. Зафиксируем какой-то бит. Поставим числу 1, если бит имеется, и 0, если нет. Получили последовательность, к примеру, 11100111101.

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

Осталось научится поддерживать модификацию. Для каждого бита будем держать сет кучек из единиц. При «выпадении» бита, одна кучка либо распадается на две, либо уменьшается на 1. При добавлении, одна кучка появляется, либо вырастает на 1, либо две соседние кучки срастаются.

Всем привет! Хотите вы, или нет, но скоро состоится Codeforces Round #234 (Div. 2) автором которого являюсь я :)

Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод задач, Михаилу Мирзаянову (MikeMirzayanov) за превосходную систему, и Сереже Нагину (Sereja) за то, что любезно (поделился со мной картошкой и беконом, было очень вкусно) согласился помочь в тестировании.

Разбалловку оглашу сразу, как найду. Нашел! Стандартная :)

Всем удачи :)

374A — Инна и розовое пони

Рассмотрим задачу о перемещении конфеты из позиции (x₁, y₁) в позицию (x₂, y₂). Очевидно, что каждым движением мы увеличиваем или уменьшаем x₁ на a и y₁ на b.

Тогда несложно догадаться, что если |x₂ - x₁| не делится нацело на a или |y₂ - x₁| не делится нацело на a, то добраться не возможно.

Стоит также заметить, что числа |x₂ - x₁| / a и |y₂ - y₁| / b должны быть одинаковы по парности, так как увеличение или уменьшение происходит одновременно для обоих значений.

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

Теперь мы можем определить сложность пути позиции (x₁, y₁) в позицию (x₂, y₂) как max(|x₁ - x₂| / a, |y₁ - y₂| / b).

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

374B — Инна и девять

Очевидно, что мы можем разбить задачу на подзадачи, так как если рядом не стоят цифры с суммой 9, то число будет независимо изменяться, относительно позиции между этими числами. Это значит, что мы разделим задачу на подзадачи вида x либо xyxyxyx...xyxy причем x + y = 9. Ответ для таких отрезков нужно будет перемножить, так как мы ищем общее количество вариантов.

Для x ответ 1. Что же делать с xyxyxy? Пусть длинна ее s. Тогда, если s парное, мы однозначно получаем s / 2 девяток. Если же s не парное, одна цифра (причем любая) останется. Таким образом каждая последовательность xyxyxyxyx...xyxyxy непарной длинны s увеличивает ответ в s / 2 + 1 раз.

374C — Инна и Дима

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

Запустим обход в глубину из каждой буквы D, запоминая уже обработанные позиции. Если мы попали в позицию, в которой уже были раньше (зашли в нее обходом из других D) тогда можем просто прибавить длину текущего пути к длине максимального пути из этой позиции. Длина пути, заметьте, растет нe с каждый переходом, а только с переходом в букву A. Если же мы попали в позицию, помеченную номером нашей буквы D (из которой мы начали), значит, имеет место цикл, и поиски можно заканчивать. Не забудьте также менять цвет позиции при выходе из рекурсии, иначе будет "ложный цикл", таким образом, помеченными "нашим" цветом должны быть только позиции, в которые мы зашли рекурсивно, но еще не вышли.

374D — Инна и последовательность

Заметим, что всего будет добавлено не более n чисел, а следовательно вылетов тоже будет не более n. Будем имитировать процесс с помощью структур данных, к примеру, деревом отрезков (можно и другими). Будем поддерживать количество чисел, которое есть на подотрезке. Соответственно добавление — спускаемся от корня до листа, увеличивая на единичку значения. Удаление — с точностью до наоборот. Если в левом поддереве не достаточно элементов, спускаемся в правое, иначе — в левой. Не забудьте также смещать позицию дырки на ее номер (так как вылеты у нас моментальные из всех дырок) и останавливать цикл при достижении первой дырки, позиция которой больше текущего количества элементов.

374E — Инна и пупсики

Будем делать бинпоиск по ответу (очевидно, что функция монотонная). Для каждого времени генерируем наши отрезки, и повернем их на 45 градусов так, чтобы они стали вертикальными и горизонтальными. Это можно сделать заменой (x, y) — (x + y, x - y). Не забудьте слить отрезки, стоящие на одной диагонали и имеющие пересечения в один. Для этого нужно отсортировать все отрезки, и пройтись подряд, обновляя правую или нижнюю границу соответственного отрезка. Теперь осталось проверить, можно ли из текущих отрезков сложить прямоугольник. К примеру, можно перебирать левый вертикальный отрезок, поддерживая множество всех горизонтальных, которые начинаются не позже него, затем, для каждого левого вертикального перебирать правый вертикальный, поддерживая уже множество горизонтальных, которые начинаются не позже левого, но и заканчиваются не раньше правого. Теперь осталось только убедится, что есть хотя бы два горизонтальных отрезка из множества, которые, к тому же удовлетворяют еще и неравенство по y-кам.

Всем привет! Скоро состоится Codeforces Round #220 (Div. 2), автором которого являюсь я, Дмитрий Березин. Это мой третий раунд, и Сережа все еще верит, что последний :)

Со времен прошлого раунда многое изменилось, Дима и Инна подумали над своим поведением, извинились перед Сережей, и все теперь живут дружно. Вам предстоит еще больше укрепить семейное счастье!

Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод задач, Михаилу Мирзаянову (MikeMirzayanov) за превосходную систему, и Сереже Нагину (Sereja) за то, что любезно (не выложил тут очередное фото) согласился помочь в тестировании.

Разбалловка будет. 500-1000-1500-2000-2500. Я же сказал, что будет :) Прошу прощения за задержку.

По всей видимости задача B имеет ошибки в авторском решении, приношу свои глубочайшие извинения. Сейчас мы исправляем ошибку и тесты. Раунд будет не рейтинговый. Большая часть решений, которые прошли претесты — неправильные. Вы можете исправить ваше решение и послать его в систему, как только все будет исправлено, все решения будут перетестированы.

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

Разбор задач

366A — Дима и вахта

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

Найдем самый дешевый способ. Очевидно, что каждой вахтерше лучше покупать то угощение, минимальная цена которого меньше. То есть, если есть вахта с параметрами a b c d, то стоимость минимального подкупа будет min(a, b) + min(c, d). Выберем вахту с наименьшей минимальной стоимость подкупа. Если она больше n, ответ -1. Иначе, ответом может быть, к примеру: Номер вахты, min(a, b), n–min(a, b).

366B — Дима и дела

Дима успевает сделать спокойно k–1 дело, то есть Инна всегда ругает его за k-ое дело, начиная с выбранного Димой первого дела. Таким образом, ответ для дел с одинаковым остатком от деления на k будет одинаковым, вывести нужно ответ с минимальным номером первого дела, поэтому достаточно посчитать суммы “руганий” для дел 0, 1... k–1. Это можно сделать к примеру так: Завести массив int sum[k]. И при считывании числа сразу определять его в соответствующую ячейку:

sum[I mod k] +  = a[i]. Теперь осталось выбрать первое i такое, что sum[i] минимальное.

Сложность решения O(N).

366C — Дима и салат

Будем поддерживать динамику d[num][balance] где num – последний рассмотренный фрукт, balance – разница между суммами выбранных калорийностей и вкусностей. Умножим все b на k. Тогда ответом будет d[n][0].

d[num][balance] = максимально возможной сумме вкусностей.

Переход: из d[num][balance] можно осуществить так:

d[num + 1][balance] = max(d[num + 1][balance], d[num][balance]) – если мы не берем фрукт.

d[num + 1][balance + a[i] - b[i]·k] = max(d[num + 1][balance + a[i] - b[i]·k], d[num][balance] + a[i]) – если берем.

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

366D — Дима и граф-ловушка

Очевидно, что лояльность пути – это ширина диапазона, с которым его можно пройти, а диапазон этот – пересечение диапазонов ребер пути. Это выплывает из того, что числа является валидным для пути, если с ним можно пройти через все ребра. Переберем все ребра графа, пусть левая граница диапазона на ребре – это левая граница пересечения. Это значит, что мы не можем использовать ребра, у которых левая граница не больше нашей. Переберем все правые границы, считая ответом диапазон с зафиксированной ранее левой границей и выбранной нами правой. Такой ответ существует, если можно пройти из первой вершины в последнюю с выбранными ограничениями. Проверим граф на связность выбирая только ребра с левой границей не больше нашей, и правой границей не меньше нашей. Если граф связный, обновляем ответ. Заметим, что правую границу можно перебирать с помощью бин поиска, таким образом итоговая сложность решения O(M²·logM).

366E — Дима и волшебная гитара

Задача имеет несколько решений. Опишу авторское, с остальными вы можете ознакомиться, посмотрев решения участников. Очевидно, что для нахождения ответа нужно посчитать матрицу maxDis[k][k], где maxDis[i][j] – максимальная сложность перехода между нотами i и j.

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

Для каждого места (x₁, y₁) на гитаре переберем все места (x₂, y₂) такие, что y₂ ≤ y₁.

Если (x₂ ≤ x₁) расстояние будет x₁–x₂ + y₁–y₂. И значит, нас интересует минимальное значение x₂ + y₂ в подматрице от (0, 0) до (x, y).

Если (x₂ ≥ x₁) расстояние будет x₂–x₁ + y₁–y₂. И значит, нас интересует максимальное значение x₂–y₂ в подматрице от (n–1, 0) до (x, y).

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

Сложность O(N·M·K)

Доброго времени суток! Скоро состоится мероприятие под названием Codeforces Round #214 (Div. 2), автором которого являюсь я, Дмитрий Березин. Это мой второй раунд, и Сережа надеется, что последний :)

Личная жизнь — такое дело, в котором много счастья не бывает, поэтому вам снова нужно будет помочь Диме и Инне. И да, Сережа вовсе не выступает в роли негативного персонажа, скорее, в роли обстоятельств, с которыми вам придется порой бороться...

Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод задач, и Сереже Нагину (Sereja) за то, что любезно (покидает комнату) согласился помочь в тестировании.

Сережа передает привет, и настоятельно рекомендует прочитать условия ВСЕХ задач.

Разбалловку скажу, честно. А разбалловка 500-1000-1500-2000-2500.

Спасибо за внимание, хорошего раунда!

Всем привет!

Увидев мой ник, Вы, должно быть, подумали: "Наконец-то! Хоть этот раунд не дает Sereja! И Вы правы! Этот раунд даю Я, Дмитрий Березин(Berezin) и мой сосед по общежитию Сергей Нагин(Sereja)

Состоится сие мероприятие в пятницу 25-го октября в 19:30.

Спасибо Геральду Агапову(Gerald) и Марии Беловой(Delinur) за помощь в подготовке и перевод задач соответственно.

Спасибо Ярославу Твердохлебу(KADR) за помощь в тестировании.

Вам предстоит помочь Диме обустроить его личную жизнь :)

Разбалловка за это дело — 500 1000 1500 2000 3000. Сережа настоятельно рекомендует прочитать условия ВСЕХ задач.

Я не менее настоятельно рекомендую попытаться их еще и решить.

Спасибо за внимание, удачного раунда!

Разбор полетов (после пинков) — http://codeforces.net/blog/entry/9334

Вчера мой друг и “сокамерник” по общежитию Сергей Нагин, более известный, как Sereja, так сказать, повел в бой украинскую команду (Sereja,Furko,Rubanenko,witua). Болеем и ждем драг металла =) Ребята, если вы это читаете — мы за вас(вся общага), надеюсь к пожеланиям присоединится и вся страна. Также хотелось бы пожелать удачи всем участникам, представляющим другие страны. Пусть битва будет честной, а переживания не уступают ЕВРО 2012 =)

Сборная Украины на первом фото)

Это что же это такое?)

Добрый день кодфорсес!

Я абитуриент 2012 и прошу вашей помощи с выбором вуза.

Благо, тесты написал неплохо, плюс диплом со всеукра и хороший аттестат обеспечили высокий бал (803) так что, надеюсь, пройти смогу в много вузов. Приоритетными являются КПИ (киевский политехнический) и КНУ (имени Шевченка).

Очень интересует мнение людей, которые учились ( учатся ) в одном из этих вузов. По специальности, скорее всего буду подавать на программную инженерию...

Увы, информацию о вузах, так сказать, "изнутри" очень мало.

Заранее благодарю всех, кто поможет и расскажет =)

Настало время, и я решил перейти из братства паскалистов (читать — синих) в братство сишников.

Посоветуйте пожалуйста, какой компилятор качать и по возможности литературу по си...

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

Буду благодарен за любые советы ...

Спасибо всем, кто отписался =) Очень признателен.

Регистрация на Див 2 № 117 идет НЕ вне конкурса.

P.s. А я уже три дня говорю, что все, что твориться с рейтингом (в том числе и пересчет для лидеров Див 2) не спроста, и не к добру =)

Я бы не сказал, что это конструктивная критика, да и критика вообще. Скорее немного о наболевшем, да и чужое мнение узнать интересно.

Итак, название темы как бы намекает на задачу D (div 2) она же B (div 1) а именно о случае k>n.

Возможно, я, в силу своей неопытности, проиграл законно, но все же поменять приятное место в десятке на билет эконом-классов в позицию 83. И все из-за действительно несуществующей подстроки.

Возможно, это всего лишь мое дилетантское мнение, но впредь хотелось бы, что бы авторы старались избегать подобных случаев, действительно, зачем искать несуществующую подстроку, да и пустое множество читать слева направо и справа налево не доставляет много удовольствия, особенно в 2-часовой стрессовой ситуации. Задача и без этого интересная, и содержательная. Но вот такая мелочь из хорошего тура с удовлетворительным результатом делает неприятный осадок на день (да, эмоциональный через край), что поделаешь, действительно обидно. Хотелось бы услышать мнение более опытных и авторитетных членов сообщества.

Тем не менее, в целом тур удовлетворяет, как и всегда. Спасибо авторам, и тем, кто, возможно, оставит здесь комментарий по делу. Спасибо.