Всем привет. Решил ли кто 10 задачу неявным декартовым деревом или какое предполагалось решение? Еще интересно послушать про 11 задачу.
Всем привет. Решил ли кто 10 задачу неявным декартовым деревом или какое предполагалось решение? Еще интересно послушать про 11 задачу.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Привет. У меня в 10 зашло FFT. 11 решается через банаховы пространства.
Можешь поподробнее рассказать, как 11-ую решать?
Мне очень интересно узнать про 04 — заходит ли там $$$\frac{qt \log n}{64}$$$ или нет, и если нет, как вообще такое решать?
10 мы сдавали лет 5 назад в ПТЗ явным декартовым деревом с unite. А как неявным делать?
Наше решение 4. Реализуем наивно за O(q*t). По асимптотике почти подходит, но это TL. Дольше всего работают прыжки по массиву red и blue, так как идёт обращение к ОЗУ в случайные места. Мы решили предпосчитать для всех позиций красной и синей фишки первые 512 ходов так же втупую за O(n*512). Как это применить для запросов? Если t<512, то идём втупую, как делали раньше. Иначе уменьшим t на 512 и пройдём по предпосчитаным массивам (тоже втупую) и добавим в сумму xor. За счёт такой техники мы используем кеш процессора, что существенно ускоряет программу
Это авторское решение =)
Задача 10 выглядела несколько баянистой, и в итоге такой и оказалась.
Однако здесь предполагалось гораздо более простое решение. Заметим, что $$$N$$$ небольшое, так что $$$O(N^2)$$$ должно проходить — надо только избавиться от $$$O(Q N)$$$ в асимптотике.
Можно заметить, что т.к. направление сортировки всегда одинаковое, то и количество инверсий никогда не увеличивается, а лишь уменьшается. А всего их $$$O(N^2)$$$, так что если мы будем просто swap-ать неправильно стоящих соседей, то времени на это хватит — главное их быстро находить.
Сортировка вставками работает за $$$O(L + I)$$$, где $$$L$$$ — длина отрезка, а $$$I$$$ — количество инверсий. Поскольку $$$O(I)$$$ в сумме даёт $$$O(N^2)$$$, то надо лишь сделать так, чтобы сумма $$$O(L)$$$ не была слишком большой.
Для этого можно хранить в дереве поиска набор позиций $$$k$$$, таких что $$$A[k-1] > A[k]$$$. Имея такое дерево, мы можем быстро ответить на вопрос, отсортирован ли отрезок. Если нет, то мы делим заданный отрезок этими позициями на возрастающие куски.
Перебираем куски слева направо, для каждого запускаем сортировку вставками, двигая элементы влево насколько нужно. Важный момент: если мы взяли очередной элемент куска и его не надо двигать влево, тогда оставшуюся часть данного куска нужно пропустить, и сразу перейти к следующему куску. За счёт этого мы тратим на запрос $$$O(R + I)$$$ вместо $$$O(L + I)$$$, где $$$R$$$ — количество кусков, а $$$L$$$ — длина запроса. Остаётся заметить, что сумма $$$O(R)$$$ не превышает $$$O(N + Q)$$$, потому что каждый запрос удаляет из дерева поиска все позиции, и добавляет максимум две новых на концах.
Получается решение за $$$O(N^2 + Q log N)$$$.
Как решалась 11 задача?
Посмотрев на определитель матрицы системы можно получить, что верно одно из трёх:
В первом случае ходы неразличимы, решение очевидно
В случае (2 но не 1) все ходы сразу бесполезно, переберём какой ход не используем, задача сведётся к двумерной с невырожденной матрицей.
Когда у нас есть невырожденная матрица, находим методом гаусса единственное решение и проверяем его допустимость.
Немного не очевидно, что определитель равен 0 только в этих двух случаях. Почему нет других вариантов, когда определитель равен 0?
Определитель имеет вид $$$d_1^3 + d_2^3 + d_3^3 - 3 d_1 d_2 d_3$$$
Приравняем к нулю и решим относительно $$$d_1$$$
Получим одно вещественное решение $$$d_1 = -d_2 - d_3$$$.
Остальные два решения комплексных и они будут вещественными только в случае $$$d_1=d_2=d_3$$$.
Добрый день. А где можно на задачи посмотреть или дорешать ?
https://olympic.nsu.ru/nsuts-new/olympiads
Там в тренировках нужно выбрать этот контест
ssor96 Спасибо !
Как решалась 6 задача?
Вызываем package.zaic =)
Придумать какой-то способ строить лабиринт логарифмического размера несложно, но упихать его в ограничения задачи очень непросто.
Взглянем на конструкцию вида:
Количество кратчайших путей при старте из левого нижнего угла будет:
В этой конструкции для получения от 0 до 15 количества кратчайших путей в правом верхнем углу достаточно убирать отдельные стены в средней линии: чтоб добавить от 1 до 3 путей надо убрать одну из стен, помеченных собачкой. И независимо от этого чтоб добавить 4, 8 или 12 путей надо убрать соответственно 1, 2 или 3 стен, помеченных вопросиком:
Весьма удачным, но всё-таки не совпадением, оказывается тот факт, что количество путей дойти правой нижней клетки равно 16. И подставив такую же конструкцию ещё раз справа мы аналогичным образом сможем добавить ещё x*16 различных кратчайших путей (где х от 0 до 15) дойти до правой верхней клетки:
Дополнительный ряд сверху с хреновиной посередине нужен, чтоб удлинить верхние пути: иначе б пути из второй конструкции справа уже бы не были кратчайшими до правой верхней клетки.
Обобщая, имея в левом нижнем углу 2^k путей мы научились строить конструкцию, с помощью которой можно до 15 раз добавить 2^k кратчайших путей и которая при этом получает в нужном месте 2^(k+4) путей и тем самым позволяет продолжить себя такой же конструкцией. Её размер 5*10 клеток и для получения до 2 миллиардов путей понадобится до 7 с половиной таких вот штук. В оптимальных конструкциях жюри получаются поля размера до 75*5 — площади 375.
Как решалась задача 2?
Динамика по изломанному профилю. Заполняем матрицу комнат построчно и для каждой комнаты выбираем в переходах в динамике ее ориентацию, при этом профиль динамики хранит, есть ли дверь в комнаты профиля снизу, а также есть ли дверь в последнюю комнату справа. Соответственно, когда мы выбираем ориентацию очередной комнаты, мы можем сразу проверить, подходит ли она под профиль.