Всем ку. Прошло уже 2 дня со второго тура закла ВСОШ, но я все-таки решил написать свое скромное мнение о задачах.
Задача 1 (100) Несложная, хорошая задача для A, единственное, где лично я потерял минут 10 — это забыл, что можно сдвигать изображение не только вправо и вниз, а во все 4 стороны.
Задача 2 (100) Многие засирают эту таску, но мне показалась прикольной, идею с тем, что мы можем расположить n чисел по кругу и для каждого вводимого находим первое справо свободное я придумал минут за 10. Квадрат написал минут за 20, но долго оптимайзил до лога, так что сдал онли на 100 минуте.
Задача 3 (57) Задача, в которой довольно быстро придумывается динамика с n^2 памяти и пересчётом за n^2 на каждом из n чисел. Затем увидим, что на каждом слое меняется только 2n чисел, каждое из которых можно пересчитывать за log.
Задача 4 (23) Странная задача, в которой никто не набрал больше 30 баллов. На 23 очев, хотел ещё сделать предподсчетом на 6, но 2.5% предподсчета отработали за 3 минуты и я забил.
100+100+57+23=280 Хороший балл
Задача 5 (100) Простая задачка на дерево, возможно слишком простая для задачи на закл, но норм.
Задача 6 (100) Сама задача хорошая, однако тесты, как уже многие говорили прекрасные, многие заслали лажу. У меня вроде хорошое решение, которое не ломается: сортим по левым границам отрезки, dp[i] для отрезка — это максимальное множество, которое кончается на i отрезок, пересчитываем так, смотрим на все отрезки, у которых r меньше, чем l[i], берём у них макс dp и +1, запоминаем в o[i] из какого отрезка пересчитались. Затем заметим, что dp не убывает. Рассмотрим отрезки для, которых ответ 1, 2, 3...m/2, если их больше чем для которых dp m/2+1...m, то рассмотрим их, иначе другие. Пусть теперь нам надо выбрать n/2 отрезков из тех, для которых ответ до m/2, тогда рассмотрим любой отрезок, для которого ответ m/2, возьмём его, возьмём отрезок, из которого он пересчитался, затем тот, для которого этот пересчитался и т д Теперь у нас ответ ровно m/2, докинем ещё любых отрезков из тех, для которых ответ не больше, чем m/2 до n/2. Ан-но если отрезков с dp больше, чем m/2. Придумал и написал довольно быстро, однако 20 минут слил, т к сначала прочитал, что множество мероприятий совместно, если все друг с другом пересекаются.
Задача 7 (63) Задача классная, написал за куб, потом решил для b=0, это очень помогло и написал за квадрат, есть ощущение, что мог до 100 добить, но подумал, что лучше оставить побольше время на D, тем более там много подгрупп.
Задача 8 (23) Задача не понравилась, 20 минут на понять условие, упёрся в набрать баллы, не думал над решением на какой то приличный балл, поэтому онли 23.
100+100+63+23 = 286 Можно было добить C и по D баллов побольше, но сойдёт.
280+286=566, твёрдый побед.
Если говорить в целом, то очень классно, что был закл на подумать, а не навалить алгосами.
Поздравляю всех призёров и победов!
