Спасибо, теперь вроде бы правильно написано
102 2011-05-02 21:46:09
Re: Статья "Кратчайшие пути фиксированной длины, количества путей ..." (1 ответов, оставленных в Feedback)
Точно, спасибо!
103 2011-05-02 21:26:12
Re: Подскажите алгоритм (7 ответов, оставленных в Problems)
Сканирующей прямой это ещё называют - т.е. мы проводим вертикальную прямую x = -infty, потом двигаем её слева направо - к x = +infty, по пути просматривая все изменения, которые происходят с картинкой.
104 2011-04-29 00:56:26
Re: Задача на строковый алгоритм (1 ответов, оставленных в Problems)
Неужели они завалили int64-ый хеш? Что-то даже не верится 
Если я правильно понял условие, то задача сводится к тому, что какой-то суффикс строки должен совпадать с предыдущими символами, но в обратном порядке? Т.е., выходит, должен быть палиндром на конце строки?
Тогда решать можно какой-нибудь префикс-функцией - ведь если мы перевернём строку, то задача сведётся к сравнению префикса строки и какой-то подстроки - а это можно делать, глядя в значения префикс-функции.
105 2011-04-26 15:56:39
Re: Диаграмма Вороного (1 ответов, оставленных в Feedback)
Да, Вы, конечно, правы.
106 2011-04-26 15:54:10
Re: Дерево Фенвика (3 ответов, оставленных в Feedback)
Напиши сюда.
Реализации за log N не знаю, хотя слышал когда-то про гипотетическое существование такой.
107 2011-04-25 15:03:18
Re: LCA online (2 ответов, оставленных в Algo)
Если мы для каждой вершины знаем её глубину в дереве (расстояние от корня), то вроде бы можно - следующим образом:
* вот нам поступили на вход две вершины a и b, тогда возьмём ту из них, которая глубже, и поднимем двоичным подъёмом до глубины другой вершины
* теперь, когда обе вершины одной высоты, мы можем уже заметить, что LCA находится от них на одном и том же расстоянии
* значит, будем идти двоичным подъёмом - если мы шагнули от обеих вершин вверх и пришли в одну и ту же вершину, то это LCA или его предок (в общем, надо попробовать подняться на меньше), а иначе, т.е. если этим шагом пришли в разные вершины - надо попробовать подняться на больше.
108 2011-04-24 21:07:36
Re: Алгоритм Диница или Шумахера??? (3 ответов, оставленных в Algo)
Вспоминается, в одном из петрозаводсков авторское решение искало Диницем поток среди 50000 вершин...
109 2011-04-12 12:59:01
Re: disjoint set (7 ответов, оставленных в Algo)
Да, я за 5 лет занятий олимпиадами ещё не встречал задачи, где надо было бы делать LCA или RMQ за O(1) с линейным препроцессингом
110 2011-04-12 11:26:30
Re: Timus 1590 hash (32 ответов, оставленных в Problems)
Пишутся хеши, конечно, побыстрей - я сам большой их любитель
Я говорил про время выполнения - собсно, этот топик отсюда и возник, что решение-то за n^2 log n, или за n^2, но с константой хешсета.
111 2011-04-12 11:24:31
Re: disjoint set (7 ответов, оставленных в Algo)
Ну да.
В этом результате, кажется, нет ничего удивительного - с предпосчетом n log n (sparse-table) отвечать на такие запросы за O(1) вообще легко. Это же более мощный метод, и у него предпосчет за n.
112 2011-04-12 07:38:01
Re: disjoint set (7 ответов, оставленных в Algo)
А, забыл дописать. Фарах-Колтона-Бендера действительно не использует dsu, и вообще он отвечает на запросы в онлайне. Но есть гораздо более простой алгоритм Тарьяна, который основан на dsu, и отвечает на запросы lca в оффлайне.
Как непосредственно применить dsu к задаче rmq, без сведения к lca, не знаю.
113 2011-04-12 00:54:23
Re: disjoint set (7 ответов, оставленных в Algo)
Ссылка не стоит, но вот есть статья по этому поводу:
http://e-maxx.ru/algo/rmq_linear
Подозреваю она из Кормена, но уже мозги вспухли от идей, как применить DSU к поиску минимума, при чем за &O(1)
И вообще если такое возможно, тогда возможна сортировка за линейное время (что как известно в общем случае не возможно)
Ну одно дело _находить_ минимум, а другое - находить и _извлекать_ его из массива. Без этого сортировку не сделать. Так что противоречия тут нет.
114 2011-04-12 00:49:16
Re: Timus 1590 hash (32 ответов, оставленных в Problems)
Acmefan пишет:
e-maxx пишет:А, ну кстати по решению с бором - не всё так плохо, можно строить сжатый бор - за квадрат его строить не так уж и сложно
а смысл тогда, если хешами тоже за квадрат решаем с меньшим напрягом
Думаю, всё же хеши с хешсетами сложнее запихать, чем "чистый" квадрат бора
115 2011-04-11 22:54:28
Re: Timus 1590 hash (32 ответов, оставленных в Problems)
А, ну кстати по решению с бором - не всё так плохо, можно строить сжатый бор - за квадрат его строить не так уж и сложно, а точнее, почти не сложнее обычного бора. А размер сжатого бора (aka суффиксного дерева), как известно, линеен.
116 2011-04-11 22:52:48
Re: Timus 1590 hash (32 ответов, оставленных в Problems)
Кратко идея решения такая: начнём с пустой строки, и будем дописывать к ней по одному символу в начало, и поддерживать текущее число различных подстрок.
Изначально, когда буква одна, - подстрока одна.
Теперь как пересчитывать это количество при добавлении одного символа в начало строки? Понятно, что все старые подстроки останутся, а добавятся подстроки, начинающиеся с добавленного символа, и не встречающиеся больше нигде в текущей строке. Т.е. нам надо научиться считать для текущей строки, сколько есть у неё префиксов, не встречающихся более внутри неё. Это делается с помощью z- или префикс-функции.
117 2011-04-11 22:23:02
Re: Timus 1590 hash (32 ответов, оставленных в Problems)
Только, наверно, в этой задаче бор будет сложно в память запихать? Как-никак, миллионов 5-10 вершин в нём будет.
Если говорить о не-хешовых решениях, то видимо проще всего будет с помощью префикс или z-функции за квадрат: рассматривая символы строки по одному слева направо и поддерживая текущее число различных подстрок.
118 2011-04-08 22:32:00
Re: Timus 1590 hash (32 ответов, оставленных в Problems)
На такой длине можно попробовать интовый хеш - поподбирать нужную базу хеша придётся тогда, ибо коллизии на интовом хеше - не редкость. Но зато инт гораздо быстрее, раз уж так хочется именно хешом решать эту задачу.
119 2011-03-29 16:09:05
Re: Четыре касательные к двум окружностям (3 ответов, оставленных в Problems)
Ну как раз, только operator- у pt и не хватает. Но это же максимальная халява:
pt operator- (pt p) {
pt res = { x-p.x, y-p.y };
return res;
}Никаких проблем с четвертями не будет, это общее геометрическое решение.
С первым примером у меня числа сходятся (хотя прямые выводятся в другом формате - в виде коэффициентов уравнения ax+by+c=0), а со вторым - нет, но там как будто где-то минус забыт: например, b[0] = 2.16204 не может быть, потому что обе окружности находятся выше 2.16204.
120 2011-03-26 01:12:10
Re: Количество разложений числа на множители N<=2*10^9 (5 ответов, оставленных в Problems)
Конечно, гадание - не лучший вариант, но вообще структура этой комбинаторной задачи выглядит достаточно сложной. Если бы порядок множителей был бы важен, то было бы более-менее понятно как решать.
Вообще, если даже N = p^k, т.е. простое в какой-то степени, то ответ - это число способов разбить k на слагаемые. А уже эта задача - достаточно "жёсткая" - обычно решается квадратной динамикой, есть довольно странная формула (выводимая с помощью производящих функций), позволяющая искать ответ за N sqrt(N).
В общем, даже в таком простом случае решение быстрее квадрата получить достаточно сложно, что уж говорить про общий случай...
121 2011-03-26 00:35:49
Re: Количество разложений числа на множители N<=2*10^9 (5 ответов, оставленных в Problems)
Ну с динамикой не всё хорошо по асимптотике, хотя есть подозрение, что всё же она должна укладываться в TL.
Дело в том, что динамика - фактически идёт по делителям заданного числа N, а т.к. N<=10^9, то по известной оценке число делителей будет в худшем случае в районе 1000.
Динамика видится такой: d[ i ][ j ] - количество разбиений числа i на множители, если разрешается брать только множители >=j. Без второго параметра не получается добиться того, чтобы 2*3 и 3*2 считались разными.
А переходы в динамике: мы перебираем число k как делитель i, больше либо равный j, и прибавляем к d[ i ][ j ] число d[i/k][k].
По асимптотике это куб, но во-первых там куб делить пополам, а во-вторых в сумме по всем i не может быть совсем уж много делителей, поэтому я верю, что это спокойно должно укладываться.
P.S. На самом деле, такое ощущение, что эту динамику можно сделать и за квадрат...
122 2011-03-26 00:26:24
Re: Дерево Отрезков (1 ответов, оставленных в Problems)
Ну понятно, что задача в том - чтобы посчитать высоту дамбы в каждой точке X - потому что тогда легко будет узнать и её объёмы на всех подотрезках (чтобы быстро отвечать на запрос объёма на подотрезке, запомним объёмы на всех отрезках вида [0;i]).
Как посчитать эти высоты? Ну L небольшое, поэтому это можно делать достаточно прямолинейно, итерируясь по точкам X=0..L и поддерживая два множества: в первом у нас будут лежать пирамиды, крыши которых сейчас идут вверх (возрастают), во втором - пирамиды, крыши которых идут вниз (убывают). Изначально оба множества пустые, а когда мы переходим к очередному X, у нас могли:
0) высоты всех пирамид в первом множестве увеличились на 1, во втором - уменьшились;
а) появиться новые пирамиды - мы их добавляем в первое множество с высотой 0;
б) исчезнуть старые пирамиды - мы их удаляем из второго множества;
в) сменить тип пирамиды с возрастающей на убывающую - мы переносим их из первого множества во второе.
Все эти преобразования можно делать втупую, просто обрабатывая все пирамиды, у которых что-то меняется при данном X.
А высотой дамбы в текущей точке X будет просто максимум из максимумов в первом и втором множествах.
Итого - под множествами легко угадывается дерево отрезков для максимума.
123 2011-03-25 23:42:05
Re: Четыре касательные к двум окружностям (3 ответов, оставленных в Problems)
Моя реализация:
const double EPS = 1E-9;
double sqr (double x) { return x * x; }
struct pt {
double x, y;
};
struct circle : public pt {
double r;
};
struct line {
double a, b, c;
};
void tangents (pt c, double r1, double r2, vector<line> & ans) {
double r = r2 - r1;
double z = sqr(c.x) + sqr(c.y);
double d = z - sqr(r);
if (d < -EPS) return;
d = sqrt (abs (d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back (l);
l.a = (c.x * r - c.y * d) / z;
l.b = (c.y * r + c.x * d) / z;
l.c = r1;
ans.push_back (l);
}
vector<line> tangents (circle a, circle b) {
vector<line> ans;
for (int i=-1; i<=1; i+=2)
for (int j=-1; j<=1; j+=2)
tangents (b-a, a.r*i, b.r*j, ans);
for (size_t i=0; i<ans.size(); ++i)
ans[i].c -= ans[i].a * a.x + ans[i].b * a.y;
return ans;
}Только прямых вернётся не 4, а 8 - там повторяющиеся будут, но лучше уж так, чем недосчитаться их 
124 2011-03-04 18:09:05
Re: округление после преобразования фурье (2 ответов, оставленных в Algo)
В смысле? Когда числа отрицательны?
125 2011-02-20 18:00:18
Re: Дерево отрезков (изменение на отрезке) (5 ответов, оставленных в Feedback)
Есть небольшие сомнения в тех частях, где рассказывается про поиск подотрезка с максимальной суммой, и где говорится о двумерных деревьях. Вообще все коды я тестировал только вручную, не отсылал никуда, поэтому есть некоторая вероятность ошибки.