What are the advantages of the z-algorithm over KMP?

No advantages =)

But if we compare Z-function and Prefix-function then:

1) “monotony”

If z[i] = x, it means substrings [0..j] [i..i+j] are equals for all j from 0 to x.

If p[i] = x, it means [0..j] = [i..i+j] for all j = x, p[x], p[p[x]] and so on.

2) LCP (Largest Common Prefix)

Z-function in fact calculates LCP[0,j] for all j. It can be used for not only substring searching.

I also have two examples of problems which, I hope, show advantages Z-function over Prefix-function.

1) Determine number (No.) of the string in its suffix array in O(n).

2) Determine number (amount) of substrings, which have at least two occuarances in the string in O(n²) (of course, you can solve it in O(n) using suffix tree).

На тимусе случился rejudge по задаче 1147…

Теперь min-time = 0.062

=)

1) Я не знаю как 2D-дерево отрезков связано с hashmap-ом. Я знаю, что такое “динамическое дерево”, в частности “динамическое 2D дерево отрезков”. Это значит, что изначально есть только корень, все остальные вершины создаются по мере надобности.

2) Если запустить эту структуру на тесте, что я описывал здесь, она создаст N^2 вершин.

Как теперь?

Добавил UPD, получилось понятнее?

Online обрабатывать запросы покраски — не значит “еще и Online отвечать на какие-то get запросы”. Это значит, что запросы покраски поступают один за одним.

Решение за NlogN, которое я пытался рассказать, принципиально использовало то, что мы все запросы покраски знаем заранее.

Структуры данных типы КД-дерева, квадродерева, 2D дерева отрезков не пользуются этим, им можно выдавать запросы покраски по очереди, поэтому я говорю, что они Online.

Получится N^2. Я об этом уже написал в соседнем комментарии.

Если получится, будет круто :-)

Да, ты прав.

Странно, я почему-то всегда 2 ребенка хранил в массиве, а больше 2-х детей ссылками :-D

К сожалению N прямоугольников могут бить поле на N^2 клеток.

Пример: N/2 горизонтальных длинных палок, N/2 вертикальных, все (N/2) * (N/2) пересекаются, получается разноцветная решетка.

Online алгоритмы покраски должны понимать, что нужно хранить N² разных цветов. Это я к тому, что все идеи с Online покраской исходного поля будут работать за время не меньше N².

UPD: N² разных цветов — я не правильно выразился. Имелось в виду N² клеток таких, что соседи имеют разные цвета. Для понимания можно нарисовать предложенный мной тест.

Рекурсивная процедура такая же.

Нам нужно только научиться быстро обрабатывать добавление в нашу структуру информации “в момент времени T отрезок [L,R] был покрашен в цвет C”

Такой запрос я умею обрабатывать за O(log²N). Для этого мне нужно дерево отрезков для [L..R] с декартовым деревом по T в каждой вершине.

Конкретно в этой, да… Но с точки зрения теория, все равно шаг вперед :-)

Эх… где ты был 2-3 дня назад :-)

Я сегодня это попробовал закодить. Понял, в чем ошибался. Идея со сжатием координат не должна работать. Теперь я верю только в асимптотику Nlog³N.

Сжатие координат нужно использовать до квадродерева. Мы говорим, что прямоугольники делят плоскость на “клетки” и “клеток” не 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, все не просто, но в конечном итоге работает :-)

Идем слева направо. Поддерживаем кучу пар <время, цвет> — отрезки, которые покрывают текущую клетку. Выбираем пару с максимальным временем и красим текущую клетку в соответствующий цвет. Чтобы менять кучу у нас есть 2N событий вида “отрезок начался” и “отрезок закончился” мы их заранее отсортировали.

Не соглашусь.

Сейчас все строго объясню:

Что значит, что погрешность вычислений не влияет на верность ответа? Это значит, что одинаковые числа, даже с учетом погрешности, мы способны понимать, как одинаковые, а разные, как разные.

Математически это можно записать так: такой что

1. |x - y| > 2·ε означает неравество

2. |x - y| < ε означает равенство.

3. Чисел таких, что ε ≤ |x - y| ≤ 2·ε не существует.

Если формулировать сравнение через ε так, как я описал выше, то сортировка всегда работает. А иначе можно сделать вывод, что погрешность настолько велика, что у нас начались более серьезные проблемы.

Если компилировать без оптимизаций, сюрприза никакого нет, правда? ;-) На доступных мне компах по крайней мере не проявилось. По-моему, это все-таки спецэффект оптимизатора.

Все проще :-)

Квадродерево стоит рассматривать, как обобщение дерева отрезков на грид. Только один запрос обрабатывается не за logN, а за N.

Если понятно, как решить задачу деревом отрезков за NlogN, квадродеревом нужно делать также и получится N^2.

Собственно решение: N раз сделать операцию “покраска на прямоугольнике”, затем в конце один раз нужно сделать обход всего дерева и узнать, сколько какого цвета у нас есть.

0.001 в 0.062 это не объясняет. 4 цикла все-таки.

На самом деле, чего говорить… Дадут решение, посмотрю, расскажу, в чем было дело :-)

Спасибо. Сейчас напишу UPD.

А вы посмотрели на собственно табличку резов? :-) Приведу на всякий случай табличку здесь.

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). Но не более!

Удачи!) А я вот половину этих 4-х часов уже потратил на GCJ…

Да, мне тоже интересно…) P.S. Попросил у админов код решения, жду ответа.

А у меня тут нигде нет откатов ;-) Идея эволюционировала.

Предлагаю все-таки прочесть википедию: СНМ

От себя добавлю, что Fredman and Saks в 1989 показали, что лучше, чем alpha(n) не бывает (взято с eng-wiki).

Про авторов тестов: в общем, просто опробуй мой вариант на существующих задачах :-)

Идея теста: нужно много раз делать p[Get(v)] = new Vertex, где v — текущая самая глубокая вершина. Утверждается, что если изначально ничего нет, то N Get-ов сработают за Theta(NlogN) операций.

Да =) Построить такой тест тянуло на целую задачу сборов к межнару… вроде же, это где-то там было?)

Кстати, если автор тестов не изверг, я бы сам писал реально быстрый СНМ так:

Get(a) : return a == p[a] ? p[a] : (p[a] = Get(p[a]))
Join(a, b) : p[Get(a)] = Get(b)

Это уже в худшем случае работает аморатизированно за O(logN)

Чтобы работало принципиально дольше чем за O(1), нужно строить специфические тесты.

for i=1..n-1 : Join(i,i+1)

Кстати, ты мне напомнил еще одну хорошую задачу, где принципиально, чтобы СНМ работало быстро:

Зимние всероссийские сборы 2010, 5 декабря 2010, bridges.

Краткое условие: нужно добавлять ребра в граф и после каждого запроса говорить “сколько сейчас мостов”. Собственно, тогда первый раз и завалил :-)

http://informatics.mccme.ru/moodle/mod/resource/view.php?id=671

Далее: Структуры данных –> Cистема не пересекающихся множеств

От себя добавлю, что hos.lyric уже улучшил мою идею (Klog^2K) до KlogK. Там вообще нет СНМ :-)

А еще, если интересны подобные фичи, советую почитать похожую идею в статье Eppstein-а Dynamic MST, Offline Solution

Например:

Persistent-Stack — олимпиада ЛКШ :-)

Persistent-Queue — один из контестов Андрея Станкевича в Петрозаводске.

Persistent-Treap — на это были задачи в последнем Петрозаводске (контест не помню)

Persistent-Lists-With-Merge — мой последний контест в Харькове.

Правда вот на Online Judge почти все они отсутствуют. Но чтобы порешать, обычно достаточно достать тесты и протестить у себя локально :-) Если нужны тесты, пишите в личку.

Yes. Binary Search = Binarniy Poisk = Binpoisk.

I’ve read the statement. As I understand: solution = binary search by the answer + greedy. So It can be solvable without [moncost]flows.

Idea of solution is really similar.

But the problem itself, as I see, no.

I agree, it’s not good idea to use old problems.

1) I’m sorry, but authors of the contest are all from Russia, we just did not know about task 3680 from poj.org

2) Anyway, I hope, for many participators it was not too boring problem :-)

Fixed. Спасибо)

Ну… возможно получилось непонятно =(

По некоторым задачам претесты делал я… Про такие задачи могу сказать только: мало я наверное в codeforces участвую, плохо пока знаю обычаи :-)

Я, как бурундук, добавлю от себя.

Да, всех нас в какой-то момент отчисляли :-)

Меня уже только на 5-м курсе. Это уже сильно позже финала.

Юру, если правильно помню, во время второго финала.

Олега на год позже.

Пост выше, очевидно, не про меня и не про Олега. А вот инфу, что Юру восстанавливали на короткий срок специально для встречи с президентом — нет не слышал :-)

UPD: Да, всех за неуспеваемость.

Челенджей, конечно, мало. Но вот падали люди пачками. И на раунд 2, и на раунд 3.

А что такое сильными? Например, да, мы обычно включали какой-нибудь случайный большой тест. Но “случайный большой” — не тоже самое, что “макстест” ;-) Или в сложных задачах (D,E) я старался включать пару крайних случаев… Но вроде, людей решивших D или E на обоих раундах не много.

Да, правильно. Добавил в разбор две строки…

Как сделать пути вершиннонепересекающимися? Раздвоить вершины.

Как добавить стоимость? Между двумя половинками вершины должна быть стоимость  $-c_i$.

Да не правда, что не заходит)

Может, ты внутри бинпоиска граф не уменьшаешь до размера K^2 ребер? :-)

Видимо “кто-то выше” это Степа Гатилов. Ему уже ответили, почему его решение не работает…

P.S. Если сдашь за полином, расскажи обязательно. Я не умею =(

Кажется, у меня есть возможность вас порадовать :-) Некоторый разбор только что появился.

Спасибо за быстрое замечание. В разбор вкралась ошибка. Fixed.

Ваня, это не геом… Это перебор :-) Ну не умею я геометрии придумывать. То жадность, то перебор, то структуры данных выходят.

Тем не менее почему-то у тебя все равно TL ;-) А авторское решение работает за 0.2…

Но вообще ты прав и некоторая часть задачи для кого-то должна была быть баяном.

P.S. А вообще совет “смотри на то, что сдают в мониторе” особенно ценен для тех, кто любит зависать над чем-то очень интересным и забывает получать более халявные плюсики :)

Монитор — очень мощный инструмент.

Помогает знание команд, вместе с которыми ты участвуешь.

Пример1: я прочел задачу в начале 3-го часа контеста, мне кажется что это очевидное декартово дерево с реверсом, я смотрю в монитор и вижу что ее не сдали все мои знакомые любители стандартных структур данных. “Мозг: что-то не так, марш искать багу в решении!”

Пример2: я час не могу решить задачу на вывод формулы… в принципе ее не очень сдают, наверное сложная. Но тут ее сплюса сдает знакомая не супер сильная школьная команда. “Мозг: google или подгон? пойду-ка тоже по подгоняю…”

Пример3: задачу быстрее сдают знакомые java-команды :-) тут выводы могут быть разнообразнее..

Но в целом, монитор — не более чем подсказка. Если команда не может показать похожий результат вообще без монитора (честно порешать все задачи, халяву решить быстрее, не халяву за более долгое время, гробы не решить)… грустно это, когда команда не может думать самостоятельно и принимать при этом верные решения. Тут я говорю про зрелые команды, способные хотя бы успеть за тур прочесть и порешать все задачи :-) а не выбрасывать “математику, длинное условие и а тут вообще что-то страшное” еще в начале контеста.

Я бы добавил сюда fputs.

putc  : 0.34
fputs : 0.40

Если я правильно понимаю, puts после себя делает fflush, а fputs не делает. Кстати, это правда? :-)

По-моему, не стоит настолько категорично)

не нужно тратить время на микрооптимизацию

Похоже на “Оптимизатор он такой сложный, лучше ему верить” :-)

Тем не менее, если в каких-то отдельных случаях понимать, как ведет себя оптимизатор хотя бы родного языка, это круто. Это реально может пригодится, чтобы получить +20% к скорости.

А думать надо об асимптотической сложности программы.

Если попробовать сперва сложить N строк в бор, а затем в хэш-таблицу, желание верить в то, что “нужно думать только об асимптотике” пройдет само собой (разница, помнится, раз в 10-15) :-)

Может быть, но точно не от меня :-) Я даже условий не читал.

Количество делителей — это уже очень много. Примерно 10^5. Мое решение делает 3*10^4 итераций на тест.

Суровая ситуация… Компилировать, кстати, можно и на стороннем online-judge. Например, acm.timus.ru

где это? :-D P.S. Fixed.

Fixed :)

Sparse Table же дает O(1) На запрос? Тут та же идея, отрезок [L..R] покрывается 2-мя отрезками длины 2^k, для которых уже все посчитано.

Если у нас есть N точек на плоскости, то КД-дерево — это структура аналогичная дереву отрезков на массиве длины N. Если у нас есть просто вся плоскость.. то непонятно.

Да, давай.

1. Сумма на прямоугольнике [x1..x2] x [y1..y2] = Sum(x2, [y1..y2]) — Sum(x1-1, [y1..y2])

2. Теперь нужно только для каждого x построить дерево отрезков по Y c операцией сумма. А Tree[x+1] получается из Tree[x] обработкой некоторых событий.

3. Если предположить, что все X-ы и Y-ки от 0 до 10^6, то решение уже готово. На самом деле, теперь нужно еще подумать про сжатие координат. Сжатие координат придется делать только по прямоугольникам-операциям, прямоугольников-запросов на этот момент мы еще не знаем. Чтобы теперь посчитать Sum(x, [y1..y2]) берем дерево Tree[x’] где x’ — ближайшая к X-у точка, для которой у нас есть дерево. И говорим, что на [x’..x] сумма менялась линейно, а значит ее можно посчитать.

Я не умею пересчитывать сумму после удаления =( После одного удаления из массива 1 1 1 1 1 1 мог получиться массив 2 3 4 5 6 7…

А операцию “удаление” ты при этом делаешь? или, как и я, аккуратно от нее избавляешься?)

Да, расскажи, пожалуйста, про квадро-дерево. Как оно помогает ответить на такие запросы?

Сейчас сделаю UPD к посту про (2).

Сейчас сделаю UPD к посту.

Да :-) Я, правда, обычно это называю не “разделяй и властвуй”, а “дерево отрезков”. Наверное, потому что там нужно только разделить отрезок запросов на два.

Да, ты прав. Я забыл сказать, что функция, хранящаяся в дереве отрезков = A*x + B

Паш, кстати, а ты понял мои решения? А лучше умеешь? :-)

(1,1,4,4) был последним, значит будет значение 2.

Точек нет. Вернее так, в каждой целой точке плоскости (x,y) находится точка.

Есть прямоугольники. Значение value_i говорит нам, например, что нужно сделать += value_i на всем прямоугольнике.

Так понятнее получилось? :-)

Ну…)))) Ну и что?) Если класть вершины всегда, памяти O(E), но зато работает так же, как и bfs. А теперь заметим, что если не класть, то хуже не станет. Кажется, все. Я не прав?

Ну у а как bfs работает Вы же понимаете? Там тоже в одной и той же очереди лежат вершины, до которых расстояние d, а потом вершины, до которых расстояние d+1.

Класс! Я такого почему-то не знал =(

Илья, скажи, а тебе известны какие-нибудь оценки снизу на асимптотику алгоритма, который ищет кратчайшие пути в графе с отрицательными ребрами?

Классический алгоритм Форд-Беллмана: будем V раз пытаться релаксировать все ребра.

Алгоритм Форд-Беллмана с очередью (также называемый “Левит с добавлением в конец”): будем на каждой из V итераций обрабатывать только ребра из тех вершин, расстояние которых улучшилось на предыдущей итерации (это как раз те вершины, что лежат в очереди).

Вроде бы очевидно, что второй алгоритм работает всегда не хуже, чем первый =)

Паша правду говорит, в поезде СПБ-Петрозаводск оказалось, что я не умею доказывать оценку O(VE) для алгоритмов, добавляющих в начало. Оставлять это просто так было нельзя :-)

Если не класть в очередь вершину, которая уже в очереди, то эффект будет тот же.

Это очень просто. Возьмите таблицу умножения.