Разбор задач Educational Codeforces Round 12

Revision ru3, by Edvard, 2016-04-20 19:12:54

665A - Buses Between Cities

Задачу предложил Сергей Эрлих unprost.

Рассмотрим интервал времени, когда Симион будет находиться на трассе строго между городами (x1, y1), (x1 = 60h + m, y1 = x1 + ta). Переберём встречный автобус. Пусть (x2, y2) — это интервал времени, когда встречный автобус будет находиться строго между городами. Если пересечение этих интервалов (x = max(x1, x2), y = min(y1, y2)) не пусто, то Симион посчитает этот автобус.

Решение на С++

Сложность: O(1).

665B - Shopping

Задачу предложил Ayush Anand JeanValjean01.

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

Решение на C++

Сложность: O(nmk).

665C - Simple Strings

Задачу предложил Zi Song Yeoh zscoder.

Для решения этой задачи есть два подхода: жадность и динамическое программирование.

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

Жадность на C++

Второй подход: Пусть zka — наименьшее количество изменений, чтобы на префиксе длины k не было двух подряд идущих одинаковых букв и при этом символ s'k был равен букве a. Переберём букву, которую поставим на k + 1-й позиции и если она не равна a сделаем переход. Цена перехода равна 0, если мы поставили ту же букву, что стояла в исходной строке s на k + 1-й позиции. В противном случае цена равна 1.

Динамика на C++

Сложность: O(n).

665D - Simple Subset

Задачу предложил Zi Song Yeoh zscoder.

Рассмотрим подмножество A, являющееся ответом на задачу. Пусть a, b, c — три произвольных элемента из A и пусть не более чем один из них равен 1. По принципу Дирихле среди этих трёх чисел обязательно найдется пара чисел с одинаковой чётностью. Поскольку в этой паре только одно может быть равно 1, то их сумма чётна и больше 2. Значит подмножество A не является простым. Таким образом, A состоит либо из двух чисел больших единицы (с простой суммой), либо из некоторого количества единиц и возможно одной не единицы (если она равна простому минус один). Первый случай легко обработать за O(n2). Второй случай легко обрабатывается за линейное время. Среди двух ответов, конечно, нужно просто выбрать лучший.

Проверять на простоту числа порядка 2·106 за O(1) можно с помощью обычного или линейного решета Эратосфена.

Решение на C++

Сложность: O(n2 + X), где X — максимальное среди заданных чисел.

Tags учебный раунд 12, разбор задач

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru9 Russian Edvard 2016-04-21 01:56:30 7297
en13 English Edvard 2016-04-21 00:46:44 2897
en12 English Edvard 2016-04-21 00:24:45 2294
en11 English Edvard 2016-04-21 00:12:52 2378
en10 English Edvard 2016-04-21 00:02:42 818
en9 English Edvard 2016-04-21 00:00:58 1001
en8 English Edvard 2016-04-20 23:03:30 65
ru8 Russian Edvard 2016-04-20 23:03:12 112
ru7 Russian Edvard 2016-04-20 22:56:00 68
en7 English Edvard 2016-04-20 22:55:17 16
en6 English Edvard 2016-04-20 22:54:41 13
ru6 Russian Edvard 2016-04-20 20:48:13 6203
en5 English Edvard 2016-04-20 20:20:15 9 Tiny change: 'the number of the fo' -> 'the numbers of the fo'
en4 English Edvard 2016-04-20 20:14:31 2
en3 English Edvard 2016-04-20 20:13:49 156
en2 English Edvard 2016-04-20 20:00:29 8 (published)
en1 English Edvard 2016-04-20 19:58:31 6278 Initial revision for English translation
ru5 Russian Edvard 2016-04-20 19:38:18 133
ru4 Russian Edvard 2016-04-20 19:36:17 2945
ru3 Russian Edvard 2016-04-20 19:12:54 68
ru2 Russian Edvard 2016-04-20 17:48:16 117
ru1 Russian Edvard 2016-04-20 17:39:47 6525 Первая редакция (сохранено в черновиках)