XXI Всероссийская олимпиада школьников по информатике Разбор задач 7 апреля 2009 года Новосибирск

2 2 Задача 1. Компьютерная сеть Автор задачи – Сергей Копелиович Разбор задачи – Федор Царев

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

4 4 Нет циклов – 40 баллов

5 5 Как реализовать? Модификация алгоритма обхода в глубину Хранить максимальную X-координату уже поставленной вершины

6 6 Один цикл – 60 баллов

7 7 Как реализовать? Найти цикл с помощью поиска в глубину Расположить одну из его вершин в начале координат Обработать остальные вершины цикла с их поддеревьями Расположить вершины поддеревьев первой вершины

8 8 Полное решение – 100 баллов

9 9 Как реализовать? Для каждой вершины найти список циклов, в которые она входит Это можно сделать с помощью обхода в глубину

10 80 баллов За прохождение всех тестов, в которых каждая вершина лежит не более чем на одном простом цикле Не нужно использовать список для хранения всех циклов, на которых лежит вершина

11 Система тестов N 10N 10 3 N 10 5 Всего баллов Без циклов Один цикл Вершинный кактус Реберный кактус Всего баллов

12 Спасибо за внимание! Вопросы?

13 Задача 2. НГУ-стройка Автор задачи – Сергей Копелиович Разбор задачи – Сергей Назаров

14 Медленное решение «Нарисовать» блоки в трехмерном массиве логического типа и проверить каждый из горизонтальных слоев Время работы – O(W·H·L), так как блоки попарно не пересекаются 40 баллов

15 Идея более быстрых решений – 1 Спроецировать все блоки на ось Oz

16 Идея более быстрых решений – 2 Горизонтальный уровень отрезок длиной 1 с целыми координатами концов Уровень заполнен сумма чисел, соответствующих отрезкам, равна W·L

17 К чему сводится задача? Задан набор помеченных числами отрезков на прямой с концами в точках с целыми координатами Необходимо найти отрезок длиной 1, который покрыт наименьшим числом заданных отрезков, сумма чисел на которых равна W·L

18 К чему сводится задача?

19 Более быстрое решение Попробовать в качестве ответа каждую целочисленную координату z Для каждой координаты z считать сумму площадей блоков и их количество Время работы – O(N·H) 50 баллов

20 Еще более быстрое решение Можно перебирать только координаты z, в которых начинается какой либо отрезок Для каждой координаты z считать сумму площадей блоков и их количество Время работы – O(N 2 ) 60 баллов

21 Техника «обработки событий» Движемся вдоль оси Oz снизу вверх События двух типов: отрезок начался отрезок закончился Поддерживаются значения двух величин: K – число отрезков, которые уже начались, но еще не закончились S – сумма чисел, соответствующих этим отрезкам

22 Техника «обработки событий»

23 Техника «обработки событий»

24 Техника «обработки событий»

25 Техника «обработки событий»

26 Техника «обработки событий»

27 Сортировка событий Событие e характеризуется двумя числами: e.z и e.type (+1 – начало отрезка, -1 – конец отрезка) e1 < e2, если: либо e1.z < e2.z либо (e1.z=e2.z) и (e1.type < e2.type) За O(n 2 ) – 60 баллов За O(n·logn) – 100 баллов

28 Еще одно решение Для каждой координаты хранить список событий, которые в ней происходят Время работы – O(N + H) 80 баллов

29 Пример теста – 1

30 Пример теста – 2

31 Пример теста – 3

32 Пример теста – 4

33 Система тестов 1 – 20 тесты: W·H·L – 25 тесты: N·H – 30 тесты: N – 40 тесты: N 10 5, H 2· – 50 тесты: N 10 5, H 10 9

Спасибо за внимание! Вопросы?

35 Задача 3. Цифры и числа Автор задачи – В. А. Кузнецов Разбор задачи – Илья Разенштейн

36 Простейший подход Перебираем числа от 1 до n и для числа i вычеркиваем число i + S(i) Оптимизации: битовый массив ускоренный подсчет функции S S(k) = O(log k) предварительные вычисления Диапазон баллов: 40 – 60

37 Полиномиальное решение – 1 Поймем, какие биты могут измениться, если вычитать числа от 0 до log n Разбиваем числа на классы (i, j, k), где k – количество единиц в первой части числа. Возникают подзадачи: понять, является ли класс «некрасивым», и найти его мощность

38 Полиномиальное решение – 1 Количество классов – O(log 3 n) Проверка класса – O(log 2 n) Время подсчета ответа для каждого класса – O(log n) Итого: O(log 5 n). Кажется, что можно уменьшить время работы, но зачем?

39 Полиномиальное решение – 2 Техника «разделяй и властвуй» Подсчет количества «некрасивых» чисел на интервале [0, 2 k ) Разбиваем наш интервал на две половины. Идея: структура «некрасивых» чисел на второй половине не сильно отличается от структуры на первой Пример: k =

40 Полиномиальное решение – 2 На краях сказывается влияние первой половины. Чтобы это учесть, явно пересчитываем края. В середине сдвиг объясняется тем, что сумма цифр увеличивается на 1 Обобщение данного метода для произвольных n – классическая конструкция в духе «получить номер по объекту» Итог: более простой алгоритм, который работает за O(log 3 n)

41 Система тестов 50 тестов – за прохождение каждого из них по два балла 1 – 20 тесты: 1 n – 30 тесты: 10 8 n – 40 тесты: n – 50 тесты: n 10 18

42 Спасибо за внимание! Вопросы?

43 Задача 4. Легкоатлетический манеж НГУ Автор задачи – В. А. Кузнецов Разбор задачи – Андрей Станкевич

44 Наблюдение – 1 Если n(n+1)/(2m) не является целым числом, то решения не существует Если n(n+1)/(2m) < n, то самая большая полоса тартана не помещается на дорожку, поэтому решения не существует. Оказывается, эти два условия – необходимый и достаточный критерий отсутствия решения

45 Жадный алгоритм Пытаемся покрыть дорожку, покрывая остаток самой большой из оставшихся полос тартана, которая помещается Тест n = 23, m = 6 23 * 24 / (2 * 6) = ?

46 Превращение жадного алгоритма в перебор Тест n = 23, m = 6 23 * 24 / (2 * 6) = Если не получилось, попробуем другой вариант

47 Перебор Заполняем дорожки по очереди На каждом шаге пытаемся положить на текущую дорожку еще одну полосу, начиная с самой большой полосы, которая туда помещается и еще не использована Если не получилось – выполняется возврат

48 Наблюдение 2 Если задача имеет решение для чисел m и n, то она имеет решение и для чисел m и (n+2m) Удлиним каждую дорожку на 2n+2m+1, используя для покрытия новой части пары (n+1,n+2m), (n+2,n+2m-1),…,(n+m,n+m+1) Таким образом, достаточно найти решение для минимального n 0, имеющего такой же остаток по модулю 2m, что и число n

49 Решение Перебираем в порядке возрастания такие числа n 0, что n 0 2m-1 и n 0 имеет тот же остаток по модулю 2m, что и n Для каждой пары (m, n 0 ) пытаемся распределить полосы тартана по дорожкам с помощью перебора Как только нашли решение – останавливаемся Дополняем решение для (m, n 0 ) до решения для (m, n)

50 Полное решение? Набирает 90 баллов Не проходит тесты: m = 957, n = 3740 m = 979, n = 3827 получающиеся из этих прибавлением 2m к n

51 Что делать? Запустить решение на всех тестах – их 6832 Заметить, что решение работает долго (порядка 10 секунд) только на этих тестах Предподсчитать ответы на эти тесты

52 Что можно еще сделать? Добавить в перебор элементы случайного поиска Если решение на задачу есть, то решений достаточно много Можно найти ветку перебора, в которой решение будет найдено быстро

53 Если вы не сделали наблюдение 2 Если задача имеет решение для чисел m и n, то она имеет решение и для чисел m и (n+2m) Ничего страшного – такое решение проходит тесты (m = 957, n = 5654) и (m = 979, n = 5785), которые не проходит решение с использованием этого наблюдения 90 баллов

54 «Жадные» решения Различные варианты жадного алгоритма – около 30 баллов Заполнять дорожку, где остался максимум Добавлять в текущую дорожку максимальную возможную полосу тартана … Добавлять одну полоску в ту дорожку, которую она либо полностью заполнит, либо (если таких нет) в самую свободную – 88 баллов (если две – то 100 баллов )

55 Математическое решение за O(n+m) Рассмотрим S=n(n+1)/(2m), S < 2n Рассмотрим пары (n, S-n), (n-1, S-n+1),… Если S нечетно, то последняя пара ((S-1)/2, (S+1)/2) Остаются числа {1,2,…,S-n-1} Их можно разбить по индукции Если S четно, то последняя пара (S/2-1,S/2+1) Остаются числа {1,2,…,S-n-1,S/2} Разобьем по индукции {1,2,…,S-n-1} на части размера S/2 Их получится нечетное число, вместе с S/2 можно составить оставшиеся части

56 Система тестов Содержит тесты против: жадных решений (35 тестов) неоптимальных реализаций перебора (10 тестов) против «правильных» переборов (по 5 тестов)

Спасибо за внимание! Вопросы?

58 Задача 5. Граффити на заборе Автор задачи – Денис Денисов Разбор задачи – Денис Денисов

59 Идеи решения Каждый граффити-художник разрисовывает сплошной отрезок плит забора Если исходно художник i находится левее художника j, то и плиты, которые он разрисовывает находятся левее

60 Двоичный поиск по ответу Если художники могут разрисовать забор за T минут, то могут и за T+1 минуту Решим более простую задачу – проверим, могут ли художники разрисовать все плиты за не более, чем T минут После этого можно организовать двоичный поиск по T

61 Решение более простой задачи – 1 «Жадный» алгоритм Каждый художник разрисовывает столько плит, сколько он успевает за время T

62 Решение более простой задачи – 2 Правую границу можно найти линейным поиском, добавляя плиты по одной пока художник успевает их разрисовать t i = (min(|p i –L|,|p i –R|)+(R–L))·a + (R–L+1)·b

63 Оценка времени работы – 1 Предварительная сортировка художников по неубыванию начальной позиции – O(m·logm) (или O(n+m) при использовании сортировки «подсчетом») Верхняя оценка на время покраски – (2a+b)n

64 Оценка времени работы – 2 Время работы «жадного» алгоритма – O(n+m) – так как на каждом шаге либо разрисовывается еще одна плита, либо происходит переход к следующему художнику Итого: O(m·logm+(n+m)·log((2a+b)n)) Такое решение получает 100 баллов

65 Другие варианты Искать новую правую границу на каждом шаге двоичным поиском – 100 баллов Искать правую границу, решая линейные неравенства – 100 баллов Время работы этих решений пропорционально logn – они работают и при гораздо больших значениях n

66 Частичное решение – 1 Динамическое программирование (O(n 2 m)) F[i][j] – минимальное время, которое требуется первым i художникам на разрисовывание первых j плит своими рисунками 40 баллов

67 Частичное решение – 2 Обработка случая m 2 Перебрать точку разделения отрезков и по формуле найти время, требуемое для разрисовывания 40 баллов

68 Что можно забыть? Сортировку по неубыванию – получите не больше 30 баллов Быстрые алгоритмы сортировки – получите не больше 80 баллов 64-битный тип данных – получите не больше 80 баллов: int64 в Delphi long long в С++

69 Система тестов M2M2M100M10 5 Всего N N Всего

Спасибо за внимание! Вопросы?

71 Задача 6. Стековый калькулятор Автор задачи – Денис Денисов Разбор задачи – Сергей Копелиович, Виталий Вальтман

72 Идея решения Динамическое программирование Поиск кратчайшего пути в графе

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

74 50 баллов Состояние – пара (n, k) Переходы: f(n, k) = min(f(a, k) + f(b, k-1) + 1), где a, b – такие числа, что либо a+b=n, либо a-b=n, либо a*b=n Числа, большие чем 2N, использовать не надо Динамическое программирование?

75 Нет! Есть циклы: f(70, k) f(75, k) + f(5, k-1) + 1 f(75, k) f(70, k) + f(5, k - 1) + 1 Итерационный алгоритм: изначально f(1, k) = 1 для всех k > 0, остальные f(n, k) = 10 9 улучшаем по формуле f(n, k) = min(f(a, k) + f(b, k-1) + 1) Форд-Беллман O(TE)=O(KN 2 logN) Дейкстра O(V 2 )=O((NK) 2 )

76 Улучшение до O(Nlog 2 N) Всегда хватит K 5 Число переходов типа «умножение» – O(NlogN) Число переходов типа «сложение» и «вычитание» – O(N 2 ) f(N,5)4·log 2 N при сложении и вычитании одно из двух чисел должно быть «маленьким». «Маленькие» = {-3,-2,-1,0,1,2,3} O(NlogN) переходов и O(N) состояний У нас уже 80 баллов!!!

77 Полное решение f(a,k)=2a-1, для a 3 Сложение и вычитание: f(n,k) f(n+a,k)+2|a|, для |a| 3 Объединяем с умножением: f(n,k) f(x,k) + f(y,k-1) + 2|a| + 1, где x*y=n+a и |a| 3 n > x, n > y при n > 5 – поэтому граф ацикличен Динамическое программирование?

78 Да!!! Есть решение за O(NlogN) Конечное состояние достижимо из O(sqrt(N)) состояний «Ленивая динамика» с конца 100 баллов

79 Система тестов N100N1000N10^5N10^6N10^9 Всего K=2426 K= K= K=5268 K=622 K= K= Всего

Спасибо за внимание! Вопросы?