В детстве мне очень нравилась задача 1147 с тимуса statements. Нравилась в первую очередь тем, что я знал кучу решений, но никак не мог придумать ни одного быстрее, чем за N2. Сейчас у меня наконец появились мысли, как решать эту задачу за NlogN.
Обобщим сперва задачу, чтобы асимптотику оценивать только через N: пусть A, B < 109, color < 106
Я знаю следующие решения, все они используют сжатие координат:
Квадродерево за O(N2)
Решение одномерной задачи деревом отрезков за O(NlogN) => O(N2 logN)
Решение одномерной задачи проходом слева направо с кучей за O(NlogN) => O(N2 logN)
Решение одномерной задачи с помощью СНМ за O(N) => O(N2) [здесь в оценке я опускаю обратную функцию Аккермана]
Новое: Решение за O(NlogN) [использует разделяй и властвуй по X и сжатие координат при переходе к подзадаче].
Если кто-то знает что-то еще, расскажите, пожалуйста, в комментариях, мне это будет очень интересно :-)
Самое короткое и быстрое из того, что я сдавал на тимус — решение [4].
Решение [5] пришло в голову буквально только что..
Хочется его записать. Чтобы не забыть :-)
А всем, кто читает этот текст, предлагается проверить на наличие ошибок и понятность описания.
Решение:
Прямоугольник = отрезок [X1..X2] и операция на отрезке "присвоить отрезку [Y1..Y2] цвет C в момент времени T".
У нас N прямоугольников, значит, после сжатия координат у нас не более 2N элементарных промежутков по X и по Y. Обозначим количество различных X-ов за M. Для всех M различных X-ов мы хотим получить раскраску столбца (вернее посчитать количества цветов).
Используем идею разделяй и властвуй, обработаем сперва первую половину X-ов, затем вторую. Алгоритм = рекурсивная функция go.
Общее состояние рекурсии: go( [xL..xR], column, rectangles ). [xL..xR] — отрезок X-ов, который мы сейчас обрабатываем, column — текущая раскраска всей полоски [xL..xR], rectangles — запросы-прямоугольники, которые я еще не обработал. Изначально [xL..xR] = [0..M-1], column = [0,0,0 ... 0], rectangles = все запросы.
Первым делом "go" разбивает rectangles на 3 группы: "не пересекается с [xL..xR]", "целиком покрывает [xL..xR]", "пересекает [xL..xR]". 1-ю группу можно выкинуть. 2-й группой перекрасить как-то column. А 3-ю группу будем передавать вниз в рекурсию.
Второе, что делает "go": сжатие координат. Да, каждый раз происходит новое сжатие координат.
За [5] и [6] я добился того, что column состоит из O(Len) элементарных клеток, и массив rectangles содержит O(Len) элементов, где Len — длина отрезка [xL..xR]. Теперь можно сделать два рекурсивных вызова. Решение закончилось.
Оценим время работы: T(K) = T(K/2) + T(K/2) + [5-перекрасить] + [6-сжатие-координат]. Если все координаты у меня от 0 до K-1, то сжатие координат работает за O(K). [5-перекрасить] — перекрашивание массива column, этим я занимаюсь в пункте [5]. По сути это решение одномерной задачи (см. список решений одномерной задачи). Используя СНМ, я получаю время O(Kα), где α — обратная функция Аккерамана. Итого: T(K) = 2T(K/2) + O(Kα). T(K) = O(KlogKα).
P.S. Это решение просто переиспользует все ту же мою любимую идею из dynamic-connectivity
UPD1: Михаил Колупаев верно подсказывает, что в [7] ошибка. Правильная версия такова: количество элементарных клеток = O(rectangles), а суммарное количество rectangles по всем 2M состояниям рекурсии = O(NlogN), т.к. каждый прямоугольник также, как и в дереве отрезков, присутствует только в O(logN) вершинах.
UPD2: Ошибка Я попробовал это все реализовать. Выяснилась отличная ошибка. В [6] сжатие координат не работает, т.к. уже покрашенная область имеет дурацкое свойство — у каждой клетки свое время покраски. Итог: алгоритма работающего за NlogN таки нет =((( у меня осталась только старая, уже проверенная идея, за Nlog3N.
А точно ли СНМ с откатами работает за O(alpha) в среднем на операцию? Ведь возможно, что каждый раз при откате мы будем восстанавливать какой-то путь, а затем сразу же его опять сжимать.
А у меня тут нигде нет откатов ;-) Идея эволюционировала.
Понятно, сорри. Значит, не надо было писать не разобравшись. Я просто прочитал сразу последнюю строчку про dynamic-connectivity и решил, что решение основано полностью на нем. Сейчас, увы, не могу вникать в идею, поскольку у меня всего 4 часа чтобы закончить курсовую.
Удачи!) А я вот половину этих 4-х часов уже потратил на GCJ...
Паралельно возник вопрос: а чем объяснить такой феномен, что самое быстрое рещение по задаче датируется аж 18 ноября 2001 года? И какой алгоритм (оценка сложности) в том решении?
Да, мне тоже интересно...) P.S. Попросил у админов код решения, жду ответа.
Тогда вроде была другая система измеряющая время, а исторические результаты никто не ретестировал. Может в этом дело?
За что заминусили Петросяна?
Он прав: с какого-то момента на Тимусе поменяли измерение времени работы и даже А+Б стало отрабатывать 0.015 вместо 0.001
А вы посмотрели на собственно табличку резов? :-) Приведу на всякий случай табличку здесь.
1: 18 ноября 2001, С++ — time = 0.001
2: 18 ноября 2001, С++ — time = 0.015
3: 18 ноября 2001, С++ — time = 0.015
4: Duplicate login detected
5: 18 ноября 2001, Pascal — time = 0.015
6..18: среди них решения разных лет от 2001 до 2011, time = 0.062
Удивляет разница 0.015 ---> 0.062. По-моему, что-то здесь все же не так ;-) Когда добавляют новые тесты ретестят всех. Когда делают upgrade тестирующей машины, время должно только уменьшаться. Когда меняют judge, время должно поменяться не более чем на 0.015 (у отдельных людей в крайнем случае на 0.031). Но не более!
Да, но то что такую скорость показали люди сдававшие в один день одного года, и за 10 лет больше никто — наводит на мысль что это всё же из-за методов оценки используемых тогда. Судя по тому что время примерно кратно 15 мс, можно предположить что оценка проводится по полным time slice циклам, и тогда первое решение уложилось в 1 изменение контекста, и могло выполняться от 0 до 14 мс, а второе не уложилось, и могло выполняться от 15 до 29 мс. И как мне кажется это было что-то вроде 13 мс для первого, и 16 мс для второго.
Почему остальные решения более медленные? Возможно изменились опции компиляции, округление оценки времени исполнения по time slice циклам вверх, а не вниз, т.е. неполный цикл учитывается как полный. Памяти те решения, кстати, тоже используют меньше
0.001 в 0.062 это не объясняет. 4 цикла все-таки.
На самом деле, чего говорить... Дадут решение, посмотрю, расскажу, в чем было дело :-)
На тимусе случился rejudge по задаче 1147...
Теперь min-time = 0.062
=)
Почему "column состоит из O(Len) элементарных клеток, и массив rectangles содержит O(Len) элементов"? Если, например, все прямоугольники имеют одинаковый llx и разные lly и ury, то все они дойдут до нижнего уровня рекурсии при [xL..xR]=[llx-1..llx] и заодно сделают там 2N элементов в сжатом columns. Тем не менее, каждый прямоугольник создаст O(log N) элементов в сумме во всех columns и rectangles во всех вызовах, так что наверно все хорошо.
Спасибо. Сейчас напишу UPD.
Каким образом используется квадродерево для этой задачи ?
Можно было бы делать так: перед тем как положить очередной прямоугольник делать запрос к квадродереву: какие цвета и сколько по площади накрываются, а потом закрашивать в квадродереве этот прямоугольник.
Будут ли эти запросы работать за O(n) или надо по-другому решать ?
Все проще :-)
Квадродерево стоит рассматривать, как обобщение дерева отрезков на грид. Только один запрос обрабатывается не за logN, а за N.
Если понятно, как решить задачу деревом отрезков за NlogN, квадродеревом нужно делать также и получится N^2.
Собственно решение: N раз сделать операцию "покраска на прямоугольнике", затем в конце один раз нужно сделать обход всего дерева и узнать, сколько какого цвета у нас есть.
С квадродеревом теперь понятно.
Решение 4 с СНМ, как я понимаю, есть на http://e-maxx.ru/algo/dsu "Задача о покраске подотрезков в оффлайне".
А как решать через кучу ?
Идем слева направо. Поддерживаем кучу пар <время, цвет> — отрезки, которые покрывают текущую клетку. Выбираем пару с максимальным временем и красим текущую клетку в соответствующий цвет. Чтобы менять кучу у нас есть 2N событий вида "отрезок начался" и "отрезок закончился" мы их заранее отсортировали.
Не очень понятно, как это решение учитывает, что у каждого прямоугольника есть еще время T. Решение как-то это учитывает?
Эх... где ты был 2-3 дня назад :-)
Я сегодня это попробовал закодить. Понял, в чем ошибался. Идея со сжатием координат не должна работать. Теперь я верю только в асимптотику Nlog3N.
xD при ограничениях этой задачи (N = 1000) Nlog^3N = N^2
Конкретно в этой, да... Но с точки зрения теория, все равно шаг вперед :-)
Что за идея за Nlog^3? Рокет сайнс какой-то?
Если в оффлайн, то правда же можно деревом отрезков двумерным это сделать Nlog^2?
Учитывая, что двумерное дерево отрезков тратит суммарно O(N * log2(N)) времени на все запросы, то и записей в память происходит тоже O(N * log2(N)).
Но как тут избавиться от массива NxN, который стандартно используется с таким деревом ?
Можно конечно завести hashmap.
К сожалению N прямоугольников могут бить поле на N^2 клеток.
Пример: N/2 горизонтальных длинных палок, N/2 вертикальных, все (N/2) * (N/2) пересекаются, получается разноцветная решетка.
Online алгоритмы покраски должны понимать, что нужно хранить N2 разных цветов. Это я к тому, что все идеи с Online покраской исходного поля будут работать за время не меньше N2.
UPD: N2 разных цветов — я не правильно выразился. Имелось в виду N2 клеток таких, что соседи имеют разные цвета. Для понимания можно нарисовать предложенный мной тест.
Как я понимаю под online-покраской понимается задача, в которой надо сообщать статистику о цветах не только в конце покраски но и в промежуточные моменты?
Иначе в чём разница online и offline. У нас же в исходном условии ответ требуется выдать только один раз в конце.
Online обрабатывать запросы покраски — не значит "еще и Online отвечать на какие-то get запросы". Это значит, что запросы покраски поступают один за одним.
Решение за NlogN, которое я пытался рассказать, принципиально использовало то, что мы все запросы покраски знаем заранее.
Структуры данных типы КД-дерева, квадродерева, 2D дерева отрезков не пользуются этим, им можно выдавать запросы покраски по очереди, поэтому я говорю, что они Online.
Не очень понял про N^2 разных цветов, у нас N запросов, откуда берется N^2 цветов? Видимо ты мысль как-то недоформулировал.
Добавил UPD, получилось понятнее?
Непонятно как из того, что у нас N2 клеток с разноцветными соседями следует, что online-алгоритм будет работать не меньше, чем за N2 времени.
И в чём ошибка, если задачу реализовывать через 2D-дерево отрезков на hashmap'е ? Почему там не получается сложность O(N * log2(N)) ?
1) Я не знаю как 2D-дерево отрезков связано с hashmap-ом. Я знаю, что такое "динамическое дерево", в частности "динамическое 2D дерево отрезков". Это значит, что изначально есть только корень, все остальные вершины создаются по мере надобности.
2) Если запустить эту структуру на тесте, что я описывал здесь, она создаст N^2 вершин.
Как теперь?
1) Да, с hashmap'ом я перемудрил — хотел сказать о создании вершин по мере надобности.
2) Я ошибочно полагал, что знаю как 2D дерево отрезков может выполнять прямоугольный запрос покраски за O(log2(N)).
Про N2 вершин согласен.
По поводу второго: http://habrahabr.ru/post/131072/ не подходит? Кажется, можно переделать прибавление на покраску и аккуратно дописать проталкивание. Поправьте, если я не прав.
Рекурсивная процедура такая же.
Нам нужно только научиться быстро обрабатывать добавление в нашу структуру информации "в момент времени T отрезок [L,R] был покрашен в цвет C"
Такой запрос я умею обрабатывать за O(log2N). Для этого мне нужно дерево отрезков для [L..R] с декартовым деревом по T в каждой вершине.
Хм, по сути это такая трехмерная структура данных. Просто первое измерение у тебя это рекурсивная функция. Казалось бы, что если у нас оффлайн по запросам, то можно их посортить по времени тогда нужна будет только лишь двумерная структура (например просто двумерное дерево отрезков)?
Получится N^2. Я об этом уже написал в соседнем комментарии.
Когда я читал пост первый раз в голове крутилось решение за NLog^2(N), но у тебя было круче и я забил, сейчас попробую восстановить.
Если получится, будет круто :-)
У меня возник вопрос. Говоря квадродерево, ты подразумеваешь дерево в котором у каждой вершины 4 сына, делящих плоскость отца на 4 части? Если да, то реализация этого у меня получает МЛ 11(что вполне резонно). Но у тебя ещё написано использовать сжатие координат. Я, честно говоря, вообще не понимаю как можно использовать сжатие координат с квадродеревом. Можешь прояснить?
UPD. Вроде уже понял.
Сжатие координат нужно использовать до квадродерева. Мы говорим, что прямоугольники делят плоскость на "клетки" и "клеток" не AxB, а 2Nx2N.
Клеток 4*10^6. Компактно хранить квадродерево можно так: 1) У каждой вершины не 4, а 2 сына. 2) На четном шаге делим пополам по X, на нечетном шаге по Y. Получается, что за 2 хода в глубину мы поделили вершину как раз на 4 части.
Бинарное представление квадродерева удобней тем, что теперь его также, как и дерево отрезке можно хранить в одномерном массиве :-) Корень = 1, дети i-й вершины = 2i и 2i+1.
Вершин в дереве 2*N = 8*10^6, в каждой я храню только цвет, в который нужно красить все поддерево. Используем для компактного хранения bitset<>
Памяти используется 8*10^6 * (12/8) байт = 12M, ограничение по памяти = 16M, все не просто, но в конечном итоге работает :-)
мдааа...
Написал сжатие отправил — опять МЛ. Потом зашёл сюда, прочитал и понял что всё это ..., короче всё ещё писать и писать. Я ведь писал квадродерево динамическое с 4-мя указателями в каждой вершине и т д. Ограничения по памяти в задаче конечно жёсткие. Спасибо большое за разъяснение.
Кстати идея делить на 2 сына класс. Это всё ещё реализовать бы.
Можно же дерево с любой постоянной степенью вершин k хранить в массиве: дети i это k*i+j.
Да, ты прав.
Странно, я почему-то всегда 2 ребенка хранил в массиве, а больше 2-х детей ссылками :-D
Ура. 3 часа и задача наконец сдалась.
P.S. если использовать 4 сына, то bitset-ы не требуются, что значительно упростило мне задачу.