Земледелие 2.0

1. Разбор задачи Земледелие 2.0

2. Решение за O(N10) – 10 баллов

Решение за O(N ) – 10
баллов
10
• Перебираем
удобряемый
прямоугольник за
O(N4)
• Перебираем
прямоугольникответ за O(N4)
• Проверяем
корректность за
O(N2)

3. Решение за O(N6) – 30 баллов

Решение за O(N ) – 30 баллов
6
Перебираем фрагмент под посадку за
O(N4)
За O(N2) проверяем, образует ли часть
из нулей прямоугольник, т.е. можно ли
удобрить.
• Перебираем удобряемый
прямоугольник за O(N4)
• Выбираем оптимальный прямоугольник
за O(N2)

4. Подзадача: поиск оптимального прямоугольника за O(N2)

Подзадача: поиск
оптимального прямоугольника
2
за O(N )
• Перебираем нижнюю
границу
• Перебираем вертикальные
столбцы
• Добавляем очередной
столбец в стек, удаляя с его
вершины все более высокие
• Для каждого столбца узнаём
левую и правую границу
прямоугольника, в котором
он взят полностью, для этого
потребуется дважды
выполнить проход

5. Подзадача: поиск оптимального прямоугольника за O(N2)

Подзадача: поиск
оптимального прямоугольника
2
за O(N )

6. Решение за O(N4) – ~50 баллов

Решение за O(N ) – ~50
баллов
4
• Перебираем
горизонтальные
границы
• Перебираем левую
границу
• Двигаем правую
границу вправо
• Все столбцы внутри
либо чёрные, либо
имеют одинаковую
белую часть

7. Решение за O(N3) – 60 баллов

Решение за O(N ) – 60 баллов
3
• Перебираем
горизонтальные
границы
• Двигаем правую
границу вправо
• Как только появляется
конфликт, нужно
сдвинуть левую границу
• Левая и правая границы
суммарно сдвинутся не
более чем на 2N

8. Решение за O(N2α(N)) – 90-100 баллов

Решение за O(N α(N)) –
90-100 баллов
2
Перебираем нижнюю
границу
При движении верхней
границы обрабатываются
события: столбцы меняют
состояние
0 — столбец не допустим
(более одной группы
нулей)
1 — в столбце одна
группа нулей
2 — столбец полностью
состоит из единиц

9. Решение за O(N2α(N)) – 90-100 баллов: события

Решение за O(N α(N)) –
90-100 баллов: события
2
• Столбец стал
допустимым (не
более одной
группы нулей)
• В столбце
остались только
единицы
• Две группы
столбцов
объединились

10. Решение за O(N2α(N)) – 90-100 баллов: обработка

Решение за O(N α(N)) –
90-100 баллов: обработка
2
• Объединения
обрабатываются
системой
непересекающихся
множеств
• Искать ответ
следует вокруг той
группы столбцов,
где произошло
очередное событие

11. Решение за O(N2) – 100 баллов

Решение за O(N ) – 100
баллов
2
• Объединения выполняются для
столбцов, находящихся рядом
• Используем связный список для их
хранения, получаем время обработки
события O(1)
• Обрабатываем события, относящиеся
только к крайним столбцам множества
(для столбца храним, является ли он
крайним)

12. Система тестов

13. Система тестов

14. Система тестов

15. Спасибо! Вопросы?