Всем привет!
10 февраля в 12:00 по московскому времени состоится вторая личная интернет-олимпиада для школьников, которая также будет являться вторым отборочным туром ИОИП. Вам предстоит помочь людям-паукам разобраться с их проблемами и вернуться в родные вселенные!
Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл личных интернет-олимпиад в этом сезоне перед началом олимпиады, если вы не сделали этого раньше.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.
Олимпиаду для вас подготовили Николай Будин (budalnik), Михаил Анопренко (manoprenko), Дмитрий Филиппов (DimaPhil) и Григорий Шовкопляс (GShark).
Для связи с жюри можно использовать адрес электронной почты [email protected].
Удачи!
Итак, раунд закончился Как решать, желательно все?
Я справился, к сожалению, только со второй, но, если кому-то нужно:
Сначала стоит вспомнить об импликации Если A -> B = 111....11__2 = -1, то в двоичном представлении A нет ни одной единицы, чтобы ее не было в B Назовем это А полностью входит в В
Зная это, мы можем сразу убрать из заданного списка такие числа, которые не полностью входят в В
После удаления нужно проверить, получим ли мы вообще ответ. Можно сделать ИЛИ для всех чисел и посмотреть, полностью ли входит в полученное В. Если В входит, значит получить можно, иначе — какой-то бит мы не заполним
И, наконец, чтобы ускорить решение, удалим все числа, полностью входящие в А. Теперь сортируем числа по убыванию и применяем самые большие к А. Применив самое большое, удаляем все невходящие в новое А и повторяем процесс, пока список подходящих чисел не закончится
Надеюсь, что это хоть чуточку понятно
Скоро должен быть разбор. Вот, что зашло по TL у меня: C: Воспользуемся динамическим программированием. Будем хранить достижимость состояния dp[i][j][k], где i, j отвечают за номер ячейки в нашей таблице, а k — это разница между площадью восточнее линии раздела и западнее линии раздела (k может принимать значения от -N * M до N * M). Чтобы ускорить решение, будем хранить состояние в битсете. Получаем решение за O(n^2 * m^2 / 64). Чтобы хватило памяти, пересчитывать надо по слоям.
D: На 67 баллов построим обычный бор, будем удалять/добавлять в него строки. Клавишу "tab" можно использовать, пока из текущей вершины есть только один путь вперед. Чтобы получить 100, будем хранить в каждой вершине, куда приведет нас нажатие в tab, когда мы находимся в этой вершине (на сколько символов вперед мы переместимся и в какую вершину бора). На запрос мы отвечаем за O(answer_length). Получаем решение O(Q * sqrt(C)), где C — сумма длин всех строк в боре (1млн).
Да, авторское решение по C на полный балл такое же, как у вас.
А вот авторское решение по D отличается от вашего :) Забавно, что есть решение с корневой эвристикой.
Разбор скоро появится.