Разбор задач 3-го этапа республиканской олимпиады по информатике 2018 года

Июль 31, 2022

Главная
Информатика
Разбор задач 3-го этапа республиканской олимпиады по информатике 2018 года

Содержание

2. Тур 2 Задача 1 Условие Дана квадратная матрица размера N, нужно поменять местами две строки, и
3. Решение на 40 баллов Полный перебор. Можно перебрать две строки и два столбца и проверить матрицу
4. Решение на 80 баллов Переберем две строки, которые поменяем местами. Тогда во всех столбцах должен установиться
5. Решение на 100 баллов Заметим, что если мы поменяем местами два столбца, то порядок следования элементов
6. Тур 2 Задача 2 Условия. Нам задана матрица 2k на 2k в заданном в условии формате.
7. Решение на 50 баллов Рекурсивно строим матрицу и затем считаем число в ней. Сложность O(22k).
8. Решение на 100 баллов Для каждой 1 мы можем определить квадрат какого размера она заполняет. Достаточно
9. Тур 2 Задача 3 Условие. Была дана последовательность из N элементов, у которой было такое свойство:
10. Решение на 30 баллов Делаем то, что просят. Максимальная возрастающая подпоследовательность можно найти с помощью динамического
11. Решение на 60 баллов На 60 баллов ai Сложность O(max2{a1, a2, … , an} * K).
12. Решение на 100 баллов Интересный факт. Если есть какие-то i, j (i Сложность O(N log N
13. Тур 2 Задача 4 Условие. Была дана матрица N на M, а также строка длины L.
14. Решения Существует много разных решений, основанных на переборе и случайных подходах. Разберём полные решения. Напишем динамическое
15. Первый подход Можно доказать, что можно оставить в каждой строчке только первое и последнее вхождение каждой
16. Второй подход Пересчитывая матрицу по слоям найдем оптимальный ответ и запомним W-ую позицию в обходе, а
18. Скачать презентацию

Слайд 2

Тур 2 Задача 1
Условие
Дана квадратная матрица размера N, нужно поменять местами

две строки, и два столбца, чтобы числа во всех строках и столбцах шли по возрастанию.

Слайд 3

Решение на 40 баллов
Полный перебор. Можно перебрать две строки и два

столбца и проверить матрицу на валидность.
Сложность O(N6).

Слайд 4

Решение на 80 баллов
Переберем две строки, которые поменяем местами. Тогда во

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

Слайд 5

Решение на 100 баллов
Заметим, что если мы поменяем местами два столбца,

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

Слайд 6

Тур 2 Задача 2
Условия. Нам задана матрица 2k на 2k в

заданном в условии формате. k <= 30. Требовалось найти число единиц в этой матрице.

Слайд 7

Решение на 50 баллов
Рекурсивно строим матрицу и затем считаем число в

ней.
Сложность O(22k).

Слайд 8

Решение на 100 баллов
Для каждой 1 мы можем определить квадрат какого

размера она заполняет. Достаточно посмотреть на количество незакрытых открывающихся скобок. Путь это число open. Тогда, образуется квадрат со стороной 2(k - open).
Сложность O(N).

Слайд 9

Тур 2 Задача 3
Условие. Была дана последовательность из N элементов, у

которой было такое свойство: для любого i > 1 и меньше либо равного N модуль разности ai с ai - 1 не превосходит 1. Также было дано K запросов. Каждый запрос задавался двумя числами l и r. Нужно было найти максимальную возрастающую подпоследовательность среди элементов al, al+1, … ,ar.

Слайд 10

Решение на 30 баллов
Делаем то, что просят. Максимальная возрастающая подпоследовательность можно

найти с помощью динамического программирования. fi - длина максимальной возрастающей подпоследовательности, которая заканчивается в i-ом элементе.
Сложность O(K * N2).

Слайд 11

Решение на 60 баллов
На 60 баллов ai <= 100. Запишем другое

динамическое программирование. fi, j - минимальная позиция на которую может оканчиваться возрастающая подпоследовательность длины i и последний элемент которой меньше либо равен j.
Сложность O(max2{a1, a2, … , an} * K).

Слайд 12

Решение на 100 баллов
Интересный факт. Если есть какие-то i, j (i

< j) и ai < aj, то для любого q (ai < q < aj) существует такое i < p < j, что ap = q. Из этого следует, что длина максимальной возрастающей подпоследовательности, которая начинается в i и заканчивается в j равна aj - ai + 1. Построим дерево отрезков, где в каждой вершине будем хранить минимальное, максимальное значение на отрезке, а также максимальную возрастающую на этом отрезке. Тогда можно легко обновить ответ.
Сложность O(N log N + K log N).

Слайд 13

Тур 2 Задача 4
Условие. Была дана матрица N на M, а

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

Слайд 14

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

полные решения. Напишем динамическое программирование fi,j,k - максимальная длина первых k прыжков, что в итоге мы окажемся в клетке i, j. Это динамическое программирование можно посчитать за O(N * M * L). Чтобы восстановить порядок нужно n * m * l памяти, что может не поместиться в оперативную память. Существуют три подхода для решения задачи.

Слайд 15

Первый подход
Можно доказать, что можно оставить в каждой строчке только первое

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

Слайд 16

Второй подход
Пересчитывая матрицу по слоям найдем оптимальный ответ и запомним W-ую

позицию в обходе, а также стартовую и финишную. Тогда наш путь разделится на две части от старта к W и от W к финишу. Запустимся от этих путей рекурсивно. Будем делить путь, пока не сможем полностью сохранить путь в динамике.
Сложность O(N * M * L * ln L).