Разбор задач

1. Разбор задач 26.12.2016

2. Задача 1. Незнайка учиться считать

Областная олимпиада 2005 года
ЗАДАЧА 1. НЕЗНАЙКА УЧИТЬСЯ
СЧИТАТЬ

3. Постановка задачи

• Дана строка, состоящая из цифр;
• Найти такую подстроку, которая
представляет собой последовательность
подряд идущих натуральных чисел и
является самой длинной по количеству
чисел.

4. Решение

• Перебираем начальную позицию, с которой
начинается искомая последовательность;
• Перебираем длину начального числа;
• Прибавляем единицу к начальному числу и
проверяем следующее;
• Проделываем тоже самое до тех пор пока
строка не закончится либо число не будет
удовлетворять последовательности;
• Сложность решения O(|S|3).

5. Трудности

• Прибавление единицы к длинному числу
(представленному в виде массива);
• 0 не является натуральным числом;

6. Задача 2. Поврежденная карта

Областная олимпиада 2005 года
ЗАДАЧА 2. ПОВРЕЖДЕННАЯ
КАРТА

7. Постановка задачи

• Дан двумерный массив, состоящий из
нулей и единиц;
• Найти наибольший по площади квадратный
подмассив, который состоит из единиц;
• Вычислить площадь найденного
подмассива.

8. Решение

• Задача решается с помощью динамического
программирования;
• Пусть A – исходный массив, D – массив состояний ДП;
• D[i][j] – максимальная площадь квадрата из единиц,
правая нижняя вершина которого находится в точке (i,
j);
• Если клетка (i, j) повреждена, то D[i][j] = 0;
• Если не повреждена D[i][j] = min(D[i – 1][j], D[i][j – 1], D[i
– 1][j – 1]) + 1;
• Первая строка и первый столбец заполняются отдельно
D[1][j] = A[1][j] и D[i][1] = A[i][1];
• Сложность решения O(N * M);

9. Задача 3. Abracadabra

Региональная олимпиада РФ за 2012 год
ЗАДАЧА 3. ABRACADABRA

10. Постановка задачи

• Дан набор строк s1, s2, s3, …, sm;
• Для каждой из строк si определить сколько
слов из словаря t1, t2, …, tn имеют суффикс и
префикс равный si;
• iй суффикс – это последние i символов
строки t;
• iй префикс – это первые i символов строки
t;

11. Решение

• Преобразуем каждую строку t, состоящую
из n символов к виду:
t0 tn-1 t1 tn-2 … tn-2 t1 tn-1 t0
• Например слово table будет преобразовано
в tealbblaet
• Отсортируем преобразованный словарь в
лексикографическом порядке;
• Таким образом, все слова с одинаковым
супрефиксом идут подряд;

12. Решение (1)

• Для каждой из строк s проделаем
аналогичное преобразование;
• Двоичным поиском найдем самое левое
вхождение (left) и самое правое вхождение
(right);
• Тогда ответом для строки si будет right – left
+ 1;
• Сложность решения O(n * Log(m));

13. Пример

• Пусть задан набор строк из примера
задачи;
• Тогда строки будут преобразованы
следующим образом:
abacaba => aabbaaccaabbaa;
abracadabra => aabrrbaacdaadcaabrrbaa;
aa => aaaa;
abra => aabrrbaa;

14. Пример (1)

• Отсортируем словарь в лексикографическом
порядке:
aaaa
aabbaaccaabbaa
aabrrbaacdaadcaabrrbaa
aabrrbaa
• Для образца a (aa) left = 1, right = 4, ответ = 4;
• Для образца abra (aabrrbaa) left = 3, right = 4, ответ =
2;
• Для образца abac (acbaabca) left = -1, right = -1, ответ
= 0;

15. Задача 4. Землетрясение

USACO Open 2001
ЗАДАЧА 4. ЗЕМЛЕТРЯСЕНИЕ

16. Постановка задачи

• Задан неориентированный граф из N вершин и M
ребер;
• Каждое из ребер необходимо восстановить за
время t и потратив на это c денежных единиц;
• Задача состоит в том, чтобы восстановить ребра
таким образом, чтобы граф оказался связным;
• При этом обещано вознаграждение F за
выполненную задачу;
• Требуется вычислить максимально возможную
прибыльность (т.е. количество денег, которые
можно заработать за час работы);

17. Решение

• Допустим, что нам известна прибыльность
работ v;
• Тогда очевидно, что мы можем вычислить
стоимость каждого из ребер как t * v + c:
первое слагаемое – полученная прибыть,
второе – стоимость восстановления дороги;
• В этом случае мы можем построить
минимальное остовное дерево и если его
стоимость меньше вознаграждения F, то такая
прибыльность нам подходит;

18. Решение (1)

• Заметим, что если увеличивать прибыльность
v, то и стоимость дерева будет расти;
• Следовательно, cost(v) – возрастающая
(монотонная функция);
• Таким образом, v можно перебирать
двоичным поиском;
• Найденное оптимальное значение прибыли и
будет ответом;
• Сложность решения O(Log(C * M) * M *
Log(M));