Тема: Предлагаю добавить задачу на принцип включений/исключений
Предлагаю добавить в перечень задач на принцип включений/исключений задачу http://www.olymp.vinnica.ua/index_ua.ph … mp;cid=133
Re: Предлагаю добавить задачу на принцип включений/исключений
А как её решать принципом включений-исключений?
Вот вертикальной декомпозицией за N^3 log N понятно как решать: мы сводим трёхмерную задачу к O(N) двумерным задачам (перебрав Z среди имеющихся в инпуте), а каждую двумерную задачу с прямоугольниками сводим к O(N) одномерным (перебрав Y среди имеющихся в инпуте), а каждую одномерную задачу - решив за O(N log N) (сортировкой).
Re: Предлагаю добавить задачу на принцип включений/исключений
То есть -- как???
Непосредственно согласно формулировке -- мера объединения (которую собственно и надо найти) равна сумме мер отдельно взятых множеств, минус ... ... ... плюс ... ... ... и т д
Без ограничений (насчёт стольки-то процентов пересечений не более чем по два и подобных) принцип включений и исключений даёт сложность алгоритма O(2^N), а упомянутый Вами способ -- наверно, действительно O(N^3*log(N)). Но с учётом упомянутых ограничений получается, что рекурсивная реализация, вовремя отсекающая пустые пересечения множеств, будет работать за O(N^3 + 2^(N/10)), что именно при таких ограничениях не хуже, и при том пишется гораздо короче. И я не говорю, будто эта задача достойна быть на первом месте. Я высказываю мнение, что она достойна быть в списке.
Если надо -- могу выслать (куда?) решение, но оно практически полностью повторяет функцию CountX со стр. 301 Порублёв--Ставровский, "Алгоритмы и программы. Решение олимпиадных задач".
Извините за задержку с ответом.
Re: Предлагаю добавить задачу на принцип включений/исключений
Эта задача уж точно не является классической задачей на применение формулы включений-исключений. Тем более, что без нее она делается за O(N log^2(N)) стандартными методами (при помощи двумерного дерева отрезков). Ну или можно за O(N^2 log N) при помощи одномерного. Да и не понятно, откуда берется 2^(N/10) в асимптотике. Почему там не чистое 2^N?
Re: Предлагаю добавить задачу на принцип включений/исключений
KADR пишет:
Тем более, что без нее она делается за O(N log^2(N)) стандартными методами (при помощи двумерного дерева отрезков).
1) Точно-точно O(N log^2(N)) ? Я что-то не вижу гарантий, почему оное двумерное дерево отрезков всегда можно сделать с кол-вом узлов O(N), а не вплоть до theta(N^2). А алгоритмы, в которых оценка памяти больше оценки времени, всегда настораживают -- кто гарантирует инициализацию?
2) Количество кода (в строках и байтах)? В моём коде 2006 года 60 непустых строк, 1758 байт -- при том, что всё это на ФриПаскале, где самому писать минимум и максимум, и вообще не_очень экономно написано. См. http://ideone.com/JASqa
KADR пишет:
Да и не понятно, откуда берется 2^(N/10) в асимптотике. Почему там не чистое 2^N?
Повторю ещё раз -- благодаря тому, что в условии написано, что не более чем 10% параллелепипедов пересекаются более чем по 2 одновременно. А также благодаря тому, что принцип реализован рекурсивно, с проверками, а не пусто ли текущее пересечение (в этом случае, естесно, вся ветка рекурсии отсекается).
Разумеется, именно в данной задаче оно немного неестественно. Но вообще говоря -- почему бы и нет? Что принципиально неестественного в том, что далеко не все 2^N пересечений действительно непусты?
Re: Предлагаю добавить задачу на принцип включений/исключений
В условии столько воды, что вообще не понятно, что действительно следует принимать во внимание, а что написано просто так.
Если это ограничение про 10% используется, то тем более эта задача не является примером. Ведь существуют решения, которые работают быстрее и которые не используют никаких дополнительных неестественных ограничений.
Насчет дерева отрезков. Я никогда не пробовал реализовывать двумерное дерево отрезков с подобными операциями, но в теории вершин должно быть O(NlogN). Решение полностью аналогично двумерному случаю. Только теперь у нас не сканирующая прямая, а плоскость. Когда встречаем начало или конец параллелепипеда, делаем обновление на прямоугольнике.