278B - Новая задача

Количество различных строк длины 2: 26² = 676, а суммарная длина всех строк не превосходит 600. Это значит, что длина ответа не превосходит 2. Поэтому можно просто проверить все строки длины 1 и 2.

277A - Изучение языков

Построим двудольный граф с n вершинами (для сотрудников) в одной доле, и m вершинами (для языков) в другой. Если сотрудник знает язык, значит должно быть ребро между соответствующими вершинами. Теперь задача выглядит понятнее: нужно добавить в граф минимальное количество ребер, чтобы появилась компонента связности, содержащая всех n сотрудников. Очевидно, что это число равно количеству компонент связности, включающих хотя бы одного сотрудника, минус 1. Но есть одно исключение (претест #4): если изначально вообще никто не знает ни один язык, то ответ равен n, так как мы не можем добавлять ребра напрямую между людьми.

277B - Множество точек

Для m = 3, n = 5 и m = 3, n = 6 решения не существует.

Научимся строить ответ для n = 2m, где m ≥ 5 и нечетное. Расставим m точек на окружности достаточно большого радиуса — это будет внутренний многоугольник. Чтобы получить внешний многоугольник, умножим все координаты внутреннего на 2. Более точно (1 ≤ i ≤ m):

Если m четное, построим решение для m + 1 и удалим по одной точке из каждого многоугольника. Если n < 2m, удалим 2m - n точек из внутреннего многоугольника.

К сожалению, такое решение не работает для m = 4, n = 7 и m = 4, n = 8.

Альтернативное решение — поставить m точек на выпуклой функции (например, y = x² + 10⁷), и n - m точек на вогнутой функции (например, y =  - x² - 10⁷). Так решал rng_58 — 3210150.

277C - Игра

Заметим, что горизонтальные и вертикальные разрезы независимы. Рассмотрим любую горизонтальную линию: она содержит m единичных отрезков, и в любой ситуации всегда возможно уменьшить длину неразрезанной части так, как этого хочет игрок. Представим, что игрок наращивает отрезок от края поля, увеличивая его длину на 1 за раз. Каждый раз суммарная длина неразрезанной части уменьшается либо на 0, либо на 1. В конце, понятно, достигает 0.

То же самое верно и для вертикальных линий. Значит, если бы не было начальных разрезов, игра превратилась бы в ним с n - 1 кучками по m камней и m - 1 кучками по n камней. Решается простой формулой.

Начальные k разрезов добавляют только техническую сложность. Для каждой вертикальной/горизонтальной линии, содержащей хотя бы один разрез, размер соответствующей кучки нужно уменьшить на суммарную длину всех разрезов на этой линии.

Как делать первый ход в ниме: пусть res — результат игры, а a_i — размер i-ой кучки. Тогда результат игры без i-ой кучки — . Мы хотим заменить a_i на какое-то x, чтобы . Понятно, что единственное подходящее значение . Итоговое решение: находим такую кучку, что , и уменьшаем a_i до .

277D - Google Code Jam

Пусть зафиксирован набор подзадач, которые мы будем решать. Давайте определим, в каком порядке их нужно решать. Понятно, что легкие подзадачи (и сложные подзадачи с probFail = 0) в любом случае не упадут. То есть наше штрафное время не меньше времени отправки последней такой <<надежной>> подзадачи. Значит, в первую очередь нужно решить все такие подзадачи. Подзадачи с probFail = 1 вообще не имеет смысла решать. Рассмотрим подзадачи с 0 < probFail < 1. Пусть есть две подзадачи i и j, которые мы решаем подряд. Посмотрим, в каком случае выгодно их решать в порядке i, j, а не наоборот. Мы не учитываем остальные задачи, так как они ни на что не влияют.

(timeLarge_i + timeLarge_j)(1 - probFail_j) + timeLarge_i(1 - probFail_i)probFail_j < (timeLarge_i + timeLarge_j)(1 - probFail_i) + timeLarge_j(1 - probFail_j)probFail_i

 - probFail_j·timeLarge_j - timeLarge_i·probFail_j·probFail_i <  - probFail_i·timeLarge_i - timeLarge_j·probFail_i·probFail_j

timeLarge_i·probFail_i(1 - probFail_j) < timeLarge_j·probFail_j(1 - probFail_i)

timeLarge_i·probFail_i / (1 - probFail_i) < timeLarge_j·probFail_j / (1 - probFail_j)

Получается, что если отсортировать подзадачи по данному компаратору, будет оптимальный порядок решения. Заметим, что подзадачи probFail = 0, 1 тоже отсортируются правильно, то есть не являются частными случаями.

Вернемся к исходной задаче. Первым делом отсортируем все задачи полученным компаратором — ясно, что в другом порядке решать никогда не выгодно по времени, а количество очков от порядка не зависит. Посчитаем такую динамику: z[i][j] = пара из максимального матожидания суммы очков и минимального штрафного времени при данной сумме очков, если мы рассмотрели первые i задач, и прошло j реальных минут контеста. Возможно 3 перехода:

1. либо мы не трогаем i-ую задачу: переходим в z[i + 1][j] с такими же матожиданиями

2. либо мы решаем только легкую подзадачу: переходим в z[i + 1][j + timeSmall_i], при этом очки увеличиваются на scoreSmall_i, и штрафное время — на timeSmall_i (мы как бы считаем, что будем решать i-ую задачу в самом начале контеста)

3. либо мы решаем обе подзадачи: переходим в z[i + 1][j + timeSmall_i + timeLarge_i], при этом очки увеличиваются на scoreSmall_i + (1 - probFail_i)scoreLarge_i, и штрафное время становится равным timeSmall_i + (1 - probFail_i)(j + timeLarge_i) + probFail_i·penaltyTime(z[i][j]), где penaltyTime(z[i][j]) — значение матожидания штрафного времени из динамики

Итоговый ответ — наилучшее из значений z[n][i], (0 ≤ i ≤ t).

Матожидание очков может быть числом порядка 10¹² с 6 знаками после точки, то есть его нельзя хранить в типе double абсолютно точно, а любая погрешность в вычислении матожидания очков может привести к ошибке в матожидании времени (претест #7). Чтобы этого избежать, можно, например, домножить все вероятности на 10⁶, и считать первое матожидание в целых числах.

277E - Бинарное дерево на плоскости

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

Назначим каждой вершине i (исключая корень) в качестве предка такую вершину p_i, что y_pi > y_i и при этом p_i — ближайшая к i. Перенумеруем все вершина в порядке невозрастания y. Очевидно, что p_i < i (2 ≤ i ≤ n). То есть мы таким образом задали корневое дерево, в котором все дуги идут вниз, и оно минимально по длине.

Теперь вспомним про "бинарность". Но она на самом деле мало чего меняет: жадность превращается в min-cost-max-flow на той же матрице расстояний, но только теперь в каждую вершину должно приходить не более 2 единиц потока.

Всем привет!

Скоро начнется Codeforces Round #170, и его автором буду я. Надеюсь, многие будут рады решить все задачи.

UPD: Разбалловка задач динамическая, задачи расположены в порядке возрастания предполагаемой сложности.

И стандартная часть: спасибо Gerald за помощь в подготовке задач, Seyaua и sdya за тестирование, Delinur за переводы, MikeMirzayanov за создание платформы Codeforces.

Удачи!

UPD: Разбор

271A - Красивый год

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

271B - Простая матрица

Предпосчитаем для каждого числа от 1 до 10⁵ следующее простое. Это можно сделать абсолютно любым способом. Главное — не забыть при проверке числа на простоту перебирать делители до корня из числа.

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

271C - Секрет

Если 3k > n, решения нет (потому что каждое множество должно содержать хотя бы 3 элемента). Иначе подходит, например, любое разбиение, в котором первые 3k чисел розданы следующим образом:

1 1 2 2 3 3 ... k k 1 2 3 ... k

Для каждого из k множеств, разность между вторым и первым элементами будет 1. При этом ясно, что разность между третьим и вторым элементами будет не 1 (более точно: 2k - i - 1 для i-го множества). Поэтому каждое множество точно не образует арифметическую прогрессию.

При этом не важно, как раздавать оставшиеся n - 3k чисел.

271D - Хорошие подстрочки

Построим из всех суффиксов строки бор (он же — несжатое суффиксное дерево). Давайте перебирать подстроки в порядке возрастания индексов, то есть сначала [1...1],  затем [1...2], [1...3], ..., [1...n], [2...2], [2...3], ..., [2...n], ... Заметим, что переход от одной строки к следующей по сути означает добавление одного символа в конец. Поэтому несложно поддерживать количество плохих букв и "текущую" вершину в боре. Если количество плохих букв не превосходит k, то строка — хорошая. И соответствующую вершину в боре нужно пометить, если она не была помечена ранее. Итоговый ответ — количество помеченных вершин в боре.

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

271E - Три коня

Утверждается, что любую пару вида (x, y) (x < y) можно привести к виду (1, 1 + k·d), где d — максимальный нечетный делитель числа y - x, а k — любое положительное целое число. Значит, каждое из (a_i - 1) должно делится на d, то есть d является делителем gcd(a₁ - 1, ..., a_n - 1), и его можно перебрать. Давайте посмотрим, для каких исходных пар d является максимальным нечетным делителем разности — это все пары с разностью ровно d, 2d, 4d, 8d, 16d и так далее. Вспомним, что числа в исходной паре не должны превышать m, а значит количество пар с фиксированной разностью t — ровно m - t.

Итоговое решение: просуммировать (m - 2^ld) по всем d — нечетным делителям gcd(a₁ - 1, ..., a_n - 1), при условии, что 2^ld ≤ m.

263A - Красивая матрица

Если единственная единица стоит на пересечении r-ой строки и c-го столбца (в 1-индексации), то ответ: |3 - r| + |3 - c|.

263B - Квадраты

Если k > n, решения нет. Иначе отсортируем квадраты по убыванию размеров. Теперь нам подходит любая точка, которая принадлежит k-ому квадрату, и не принадлежит k + 1-ому. Например, можно вывести координаты (a_k, 0).

263C - Круг чисел

Первым делом проверим, что каждое число встречается во входных данных 4 раза. Если это не так, то решения точно нет. Иначе попытаемся восстановить круг. Так как циклический сдвиг не имеет значения, пусть 1 будет первым числом. Второе и третье число должны быть соединены с 1 и между собой, поэтому вариантов мало, их все можно перебрать. Зная эти 3 первых числа, оставшаяся часть круга однозначно восстанавливается за линейное время. Возьмем последние 2 числа из круга, далее найдем число, которое соединено с ними, но еще не входит в ответ, и добавим его в конец. Если такое число нашлось, то продолжим процесс. Если в результате получилось добавить все числа в круг, то это и есть ответ.

263D - Цикл в графе

Рассмотрим такой простой путь v₁, v₂, ..., v_r, что его нельзя продолжить добавлением вершины в конец, к v_r. Это значит, что все соседи v_r уже содержатся в пути. Найдем первую вершину в пути (v_l), которая соединена с v_r. Понятно, что v_l, v_l + 1, ..., v_r — цикл, и он содержит всех соседей v_r. По условию задачи, каждая вершина имеет хотя бы k соседей. Значит длина цикла не менее k + 1 ( + 1 получается за счет самой вершины v_r).

263E - Ромб

Разделим ромб на 4 прямоугольных треугольника, как показано на рисунке ниже. В результате получится 1 треугольник размера k, 2 — размера k - 1, 1 — размера k - 2.

Разобьем задачу на 4 подзадачи. Самый удобный способ сделать это — 4 раза повернуть исходный массив на 90 градусов, и каждый раз запускать одну и ту же функцию, которая решает для одного треугольника. Функция будет возвращать 2-мерный массив, каждая ячейка которого будет содержать ответ для треугольника с вершиной в этой ячейке. Несложно понять, как совместить 4 таких массива, чтобы получить ответ для исходного ромба.

Основная идея решения для треугольника в том, что, зная ответ для одной клетки, мы можем "подвинуть" треугольник на единицу в любую сторону (вправо, вниз, влево или вверх) и пересчитать ответ за константное время. Вообще говоря, важны только 2 направления: вправо и вниз. А ответ для верхней левой клетки можно посчитать за O(k²) двумя вложенными циклами.

Определим следующие 5 функций:

1. Сумма на диагональном отрезке из k элементов:

2. Сумма на вертикальном отрезке из k элементов:

3. Взвешенная сумма на вертикальном отрезке из k элементов:

4. Сумма на треугольнике:

5. Взвешенная сумма на треугольнике:

Посчитать первые 3 функции за O(nm) в сумме совсем просто. Остальные функции можно быстро считать так:

triangle(x, y + 1) = triangle(x, y) - diagonal(x, y - k + 1) + vertical(x, y + 1)

triangleWeighted(x, y + 1) = triangleWeighted(x, y) - triangle(x, y) + verticalWeighted(x, y + 1)

Формулы для перемещения треугольника в другие стороны почти ничем не отличаются.

Изначально мы хотели расположить задачи по сложности так: A-C-E-D-B. Насчет порядка последних двух мнения разделились. Посмотрим, что покажут результаты.

166A - Ранклист

В этой задаче нужно сделать то, что написано в условии — отсортировать команды по заданному компаратору: (p₁ > p₂) или (p₁ = p₂ и t₁ < t₂). После этого надо разбить команды на группы одинаковых, и найти размер группы, команды из которой делят k-ое место. Многие почему-то при равенстве числа задач сортировали команды по убыванию времени, а не по возрастанию. Такие решения случайно проходят претесты и получают WA #13.

166B - Многоугольники

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

Второе решение – разрежем A на треугольники (по номерам вершин): (1, 2, 3), (1, 3, 4), (1, 4, 5), …, (1, n - 1, n). Последовательность углов 2 - 1 - 3, 2 - 1 - 4, 2 - 1 - 5, …, 2 - 1 - n монотонно возрастает. Значит, для каждой точки многоугольника B можно за log(n) бинпоиском найти, какому треугольнику она может принадлежать по углу относительно вершины 1.

Аналогично можно разрезать многоугольник A вертикальными линиями на O(n) трапеций. В таком случае бинпоиск будет просто по x-координате.

166C - Медиана

Если в исходном массиве нет числа x, то, очевидно, нужно его добавить, +1 к ответу. Далее делаем следующим образом. Пока медиана массива строго меньше x, нужно ее увеличивать. Очевидно, самый надежный способ увеличить медиану – добавить в массив максимальное число (10⁵). Аналогично, пока медиана строго больше x, добавляем в массив числа 1. Ограничения позволяют добавлять числа по одному и пересчитывать медиану “в лоб”.

Также есть решение вообще без случаев: пока медиана не стала равна x, добавляем в массив число x.

166D - Обувной магазин

Будем рассматривать всех людей в порядке убывания их размера обуви. Заметим, что при рассмотрении i-го человека нам важны максимум две пары обуви: размера l_i и l_i + 1. Это позволяет написать динамику с состоянием: (номер первого нерассмотренного человека i, доступна ли для покупки обувь размера l_i, доступна ли для покупки обувь размера l_i + 1). Переходы: оставить i-ого человека без обуви, или продать ему обувь одного из двух подходящих размеров.

166E - Тетраэдр

Очевидное решение динамикой: нам важно только сколько ходов осталось сделать муравью, и в какой из четырех вершин он стоит. Получается 4n состояний, из каждого по 3 перехода – при аккуратной реализации такое может пройти. Можно заметить, что вершины A, B, C эквивалентны между собой. Это позволяет написать такое решение:

int zD = 1;
int zABC = 0;
for (int i = 1; i <= n; i++) {
	int nzD = zABC * 3LL % MOD;
	int nzABC = (zABC * 2LL + zD) % MOD;
	zD = nzD;
	zABC = nzABC;
}
cout << zD;

Также задачу можно решать за log(n) бинарным возведением в степень n некоторой матрицы 2 × 2.

Пока все мировое сообщество спортивных программистов затаив дыхание ждет новостей о времени и месте проведения финала, мы решили не затягивать с раундом и в поезде по дороге из Петрозаводска в Саратов придумали задачи. В купе присутствовали – Михаил Мирзаянов, Артем Рахов, Максим Иванов. Задачи перевела Мария Белова.

Удачи!

Артем Рахов и команда Codeforces

Всем привет!

Недавний тестовый раунд прошел хорошо. Ожидается, что теперь все будет работать быстрее. В подготовке задач сегодняшнего раунда принимали участие: Михаил Мирзаянов, Николай Кузнецов, Иван Фефер и Мария Белова.

Удачи!

Артем Рахов и команда Codeforces

• Задачи
• Результаты
• Победитель: JKeeJ1e30

Добрый вечер!

Скоро у многих начинается сессия, а у кого-то она уже в самом разгаре. Хочу пожелать всем отличных оценок и побольше халяв!

Раунд помогали готовить: Николай Кузнецов, Геральд Агапов, Иван Фефер.

Удачи!

Артем Рахов и команда Codeforces

UPD: 

• Результаты
  
• Задачи
• Победитель: ghostof2007

Внимание участникам Дивизиона 1! В Codeforces Beta Round #32 в качестве тестовой возможности будет доступно участие «Вне конкурса».

Как вы все прекрасно знаете, 2-ое октября – День рожденья Махатмы Ганди. Мы посвящаем сегодняшний раунд ему, и многим другим замечательным людям, родившимся 2-го октября :)

Раунд помогали готовить Михаил Мирзаянов, Матов Дмитрий и Макс Иванов.

Отдельное спасибо Юлии Сатушиной за перевод большей части условий.

Всем удачи!

Артем Рахов и команда Codeforces

Доброго времени суток.

Авторы задач сегодняшнего раунда – Михаил Мирзаянов и я. Хочу сказать спасибо Дмитрию Левшунову за техническую помощь в организации контеста, а так же Геральду Агапову и Николаю Кузнецову за написание альтернативных решений.

Желаю всем удачи!

UPD: Контест закончился, всем спасибо за участие.

• Задачи
  
• Результаты
  
• Победитель: marek.cygan
  

• Задачи
• Результаты
  
• Победитель: saeedreza.seddighin

Приветствую всех на Codeforces Beta Round #22

Обратите внимание, что на этот раз регистрация возможна в течение всего раунда. Сам раунд начнется в 19:00 по Москве.

Автором задач этого контеста буду я. Большое спасибо Михаилу Мирзаянову за помощь в подготовке контеста, Эдварду Давтяну и Николаю Кузнецову за написание проверочных решений, и Юлии Сатушиной за перевод условий на английский.

Удачи на раунде!

UPD: Контест окончен. Всем спасибо за участие!
Задачи
Результаты
Победитель Kasparyanm_Mihail получает за контест +203 к рейтингу!

Добро пожаловать на Codeforces Beta Round #18

Авторы задач сегодняшнего контеста: Михаил Мирзаянов, Эдвард Давтян и я. Спасибо Дмитрию Матову за помощь в подготовке условий и Юлии Сатушиной за перевод задач на английский язык.

Всем удачи!

• Задачи
• Результаты
  
• Победитель: I_am_Feeling_Lucky

Добрый день.

Сегодня автором задач выступаю я. Хочу сказать спасибо создателю Codeforces Михаилу Мирзаянову и Эдварду Давтяну за помощь в подготовке задач и Юлии Сатушиной за отличный перевод на английский.

Желаю всем выйти в первый дивизион!
Артем Рахов

UPD: Контест закончился, всем спасибо за участие!

• Задачи
• Результаты
  
• Победитель: krijgertje