Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных).
Сегодня я принял виртуальное участие в Educational Codeforces Round 137 (Rated for Div. 2).
Первая задача
Если посмотреть на ограничения, то можно сделать вывод, что задачу можно решить перебором.
Можно и комбинаторикой, но зачем?
Я долго тупил, поэтому 9 минута, Python.
Вторая задача
У нас 100% будет существовать две перестановки:
- Длины 1
- Длины n
От остальных мы можем избавиться, если сразу после 1 поставим n [1, n, ...]. И у нас останется две перестановки - длины 1 и длины n.
14 минута, Python.
Третья задача
Мы будем рассматривать массив слева направо.
- Если на i-той позиции стоит '1', то к. счётчику прибавляем a[i]
- Если на i-той и i+1-той позиции стоят '0', то ничего не делаем
- Если на i-той позиции стоит '0', а на i+1-той позиции стоит '1', то мы смотрим. Если a[i+1] > a[i], то на i+1-ую позицию ставим '0', а к счётчику прибавляем a[i].
Асимптотика O(n)
25 минута, Python.
Четвёртая задача
Меня смутил пункт про то, что все тесты случайны. Задачу я решал просто жадным брутфорсом. Одной из подстрок была вся строка, а вторая - это префикс строки.
Тут кстати речь идёт о побитовых операциях, о которых я писал отдельно. Важно, что в задаче речь идёт о побитовой операции OR, а в моей статье по бОльшей части написано про XOR.
Асимптотика O(n2)
49 минута, C++
Шестая задача
Метод решения - динамическое программирование.
- Если x < l[i] или r[i] < x, то dp[i] = dp[i — 1] * 2
- Если l[i] <= x <= r[I], то dp[i] = 3 ^ (i — 2) * 2
Асимптотика O((n + M)logn)
1 час, С++
P. S. В разборе задач приведено другое решение, где используется мат. ожидание и метод Contribution to the sum. Об этом методе я не знал. В скором времени я его изучу и также напишу в Дзене о нём.
Пятая задача
Над пятой задачей я думал больше всего. В один момент я даже думал сдаться, но всё-таки решил довести решение до конца. И опять задача решается через динамическое программирование.
Короче, у нас будет некое Т - время между двойными выстрелами. Оптимальными будут те Т, которые будут множителями t1 и t2 (время перезарядки первого и второго), что в общем и целом логично.
А дальше перебираем все возможные T и перебираем все i * t1 и i * t2. I - i максимальное.
Асимптотика O(I2)
1 час 53 минуты, С++
Очевидно, что я не решил бы седьмую задачу за 7 минут, поэтому на этом всё.