Всем привет!
Ну что же, вот и пришел сезон личных олимпиад в Беларуси. Совсем скоро, 12-13 января по всей Беларуси будет проходить областная олимпиада по информатике.
Предлагаю в этом посте выкладывать условия, обсуждать задачи и прочее и прочее. Я же от себя после туров буду делиться своими идеями по задачам.
В прошлом году тоже было что-то похожее, кому интересно — вот ссылка.
Good luck && Have fun!
Day 1.
Тупая реализация! Главное, аккуратно чекать случай, когда есть ### и выстрел в центр.
A — массив ответ. A[1] = y. Дальше просто добавляем единичные биты в свободные позиции. Проверяем, что набралось N элементов — выводим ответ, иначе -1.
Дп F[pref] — ответ для префикса pref. left[x] — левая граница числа x, right[x] — правая соответственно, cnt[x] — количество. Пересчет
- f[pref] = f[pref — 1]
- если pref == right[a[pref]], то f[pref] = max(f[pref], f[left[a[pref]] — 1] + cnt[a[pref]]
Ответ лежит в f[n].
- Брут за N * K^2 довольно простой, фиксим позицию которая так и останется стоять (это N * K) а дальше смотрим как нужно повернуть минимально остальные диски.
По ограничению из условия — это 60.
Итого — 360 очень простых баллов.
Кто знает как решать 4-ую на сто?
Day 2.
Обычная потная реализация! (фу-фу-фу давать такие задачи два дня подряд).
дпшка f[i][j] — где i — последний чувак, которого мы поставили, j — сколько пьедесталов рассмотрели. f[i][j] — минимальная высота, на которой стоит i — парень.
дпшка f[i][j] — где i — последнее письмо, которое мы доставили, а j — сколько раз мы ходили вдоль домов. f[i][j] — максимальное количество писем, которые можно доставить с такими параметрами. Пересчет фенвиком, ибо думаю что ДО должно упасть.
Единственная задачка, которая требует чутка внимательности и соображалки. Ответ всегда 2!!! Исходя из этих соображений просто закидываем весь набор в сет пар (количество книг, тип книги). Дальше просто жадно берем первый и последний элемент. Они гарантированно замостят всю строку! Ну вот и все, генерим outputs и получаем 100 баллов.
Итого — 400 очень простых баллов :).
Условия первого дня:https://goo.gl/photos/QKFXuHDqQ5wANCMs8
Условия второго дня: https://goo.gl/photos/AwWQZ8TbpB3ZVLdF7
Автокомментарий: текст был обновлен пользователем Yury_Bandarchuk (предыдущая версия, новая версия, сравнить).
4ая задача. Давайте переберём цвет, который будем ставить в один ряд. Теперь смотрим на его позиции во всех строках. Допустим в строке i это b1, b2, ..., bk. Теперь видно, что нам выгодно сдвигать bi к позициям с bi до (bi + 1 + bi) / 2, а bi + 1 к позициям с (bi + bi + 1) / 2 + 1 и до bi + 1. Видно, что нам надо просто уметь добавлять арифметическую прогрессию на отрезке, а потом после добавлений получать наш массив. Делать это можно с помощью префиксных сумм.
Также можно реализовать эту идею, возможно, чуть проще: опять же разбиваем каждую строку на соответствующие отрезки, но потом используем не дерево отрезков, а проходим сканлайном.
Так никто вроде про дерево отрезков и не говорил)
Вроде префиксные суммы легче сканлайна.
Хех. Да, моя ошибка, поторопился, не дочитал до конца, сделал неправильный ход.
На самом деле просто я придумал решение со сканлайном, а когда увидел фразу "прибавлять ... на отрезке", ни о чем, кроме ДО, думать уже не мог.
Автокомментарий: текст был обновлен пользователем Yury_Bandarchuk (предыдущая версия, новая версия, сравнить).
в 3ей задаче не надо дп. Просто максимальная возрастающая в массиве A+rev(A)+A+rev(A)+...+B. B=rev(A), если K чётное, а иначе B=A. Речь идёт о 3ей задаче второго дня.
Одна из самых красивых реализаций — считать возрастающую подпоследовательность фенвиком и ходить туда обратно по массиву.
Резы брестской области: https://drive.google.com/file/d/0B1q0wOKbpjEfeWVQY01sbVdVd0U/view?usp=sharing
В третьей задаче первого тура (дня) дп не нужно: решение без дп, но с графами
Не понимаю, почему у этого коммента так много минусов.. (хотя код я не смотрел:) )
Действительно, можно было придумать красивое решение за O(N + max(A)^2). Будем хранить для всех чисел A(i-е) самое левое и правое его вхождение в исходную последовательность, а также количество чисел, равных A(i-е) (обозначим как cnt(i-е)).
Теперь построим ориентированный граф, где вершинами будут являться числа A(i-е) ( не более 100 вершин). Тогда добавим ребро между i-ой и j-ой вершиной тогда и только тогда, когда самое правое вхождение числа A(i-е) находиться левее (т.е. индекс меньше) самого левого вхождения числа A(j-е).
Вполне очевидно, что получившийся граф ацикличен. Теперь для нахождения ответа осталось лишь посчитать путь максимальной стоимости, где стоимость определяется суммой cnt по вершинам, входящим в путь. Делать это можно как угодно, например, запуская дфс из каждой вершины.
Не понимаю, почему у этого коммента так много плюсов. Cuellius'а минусили не за то, что его решение "некрасивое" (кто и как определяет красоту — непонятно) , а скорее за то, что он не рассказал свое решение, а просто скинул код, в котором не каждый сможет разобраться. За такое действительно можно минусить.
Вот именно потому, что граф ацикличен, Cuellius'a заминусовали. Вы же с ним только что такое же дп написали, как и у всех, просто у вас пересчет необычный. А так — все то же самое, ведь состояния и переходы в дп и есть ацикличный граф. Это были минусы за что-то в духе "ты че тут самый умный штоле?"
"ты че тут самый умный штоле?"(с)
Это было ожидаемо
Будут ли сводные результаты ? Результаты г.Минска
Здесь результаты претендентов в областные команды Минска, Гомеля, Бреста (прошу прощения, если чью-то фамилию с фотки набрала неверно) и Лицея БГУ. То что доступно.
Результаты минской области.
Результаты Гродненской области
Нет прав на промотр...
Исправлено
А где результат Юры, его нет в таблице?
Юра в Казахстане, на Жаутыковской олимпиаде. На Республику едет без участия в областном туре.
Все команды, кроме Витебска и Могилева.
Результаты Витебской области: https://goo.gl/photos/hyQnHqkna23WAfDJ9
Результаты команд без Могилева
Результаты Могилевской области
Сколько человек планируется команда Могилевской области?
15 + 1 (город, не область) => 16 человек
Т.е. позиции 1-15 и 17.
И наконец, результаты 3 этапа Белорусской республиканской олимпиады по информатике. Сводная таблица всех команд. Смотрите, анализируйте, делайте выводы. Всем успехов в марте в Могилеве.