cpn[ i] = rmq_get (pos[a], pos[ b] - 1); вроде ближе к истине для c[a] != c[ b] ...
51 2010-09-04 13:36:59
Re: Наибольший общий префикс двух подстрок (10 ответов, оставленных в Feedback)
52 2010-09-04 13:14:19
Тема: Наибольший общий префикс двух подстрок (10 ответов, оставленных в Feedback)
Алгоритм поиска lcp на http://e-maxx.ru/algo/suffix_array не всегда срабатывает
В частности if (c[a] != c[ b]) -> lcpn[ i] = lcp[pos[a]]; может быть не верно
для строки "abaabca"
на втором шаге "abca" идет перед "baabca", lcpn копируется с предыдущего и получается равным 1.
53 2010-07-02 23:46:14
Re: MinCostFlow (10 ответов, оставленных в Problems)
54 2010-06-28 09:53:43
Re: triangles (4 ответов, оставленных в Problems)
Смотри проблему Tri и ее решение http://www.ceoi2009.ro/view_page.php?id=24
55 2010-06-26 08:48:59
Тема: Еще опечатка (1 ответов, оставленных в Feedback)
На http://e-maxx.ru/algo/schedule_with_completion_duration
строчку с "t = 0;" нужно поменять местами со следующей за ней.
56 2010-06-19 23:40:10
Re: Суффиксный автомат (5 ответов, оставленных в Algo)
Вот тут можно скопипастить
http://acm.mipt.ru/twiki/bin/view/Algorithms/UkkonenCPP
57 2010-06-11 20:17:57
Тема: Codefoces 17 (2 ответов, оставленных в Algo)
Спасибо, Егор, за интересные задачи.
все-таки интересно - Максиму повезло (слабость тестов) что его a^(b%phi(с))%c для a и c не взаимно простых прокатило или все-таки можно и для них ?
58 2010-06-04 10:48:13
Re: timus 1553 (11 ответов, оставленных в Problems)
2MSDN: Композиция + segment tree сдается без проблем. Оптимизируй.
59 2010-06-03 17:06:18
Re: timus 1752 (7 ответов, оставленных в Problems)
делается двумя dfsами на первом считаешь самую удаленную в _текущем поддереве_
на втором в в параметры dfs а еще добавляешь самую удаленную вершину и путь до нее "снизу" текущего дерева
60 2010-06-03 10:12:46
Re: timus 1553 (11 ответов, оставленных в Problems)
Чего-то ты выдумываешь
Нарисуй на бумаге небольшое бинарное дерево и сделай его композицию - когда мы спускаемся с пути на котором лежит A вниз, мы же не попадаем на полный промежуточный путь - а лишь на его часть.
61 2010-06-03 00:18:44
Re: timus 1553 (11 ответов, оставленных в Problems)
heavy-light декомпозиция не гарантирует что у нас будет не больше 4х нецелых путей для всех вершин.
Попробуй оптимизировать чтение / хранение дерева
62 2010-05-20 10:08:03
Re: timus 1429 (2 ответов, оставленных в Problems)
Сам себе подсказал.
Что б добиться такого времени - храни в sete только точки для текущего круга, а не все вместе. а totalPoints изменяй вручную:
if (i < j && edges.find(p) == edges.end())
totalPoints++;
Получается экономия и по памяти и по времени.
63 2010-05-20 09:50:30
Re: timus 1429 (2 ответов, оставленных в Problems)
Интересно как они в 300 KB укладываются - как-то же надо определить новая эта точка пересечения или нет.
У меня тоже получилось только за 1.3 сдать с похожим алгоритмом.
64 2010-05-19 22:59:59
Re: NEERC 2000 Triathlon (4 ответов, оставленных в Problems)
Только что получилось сдать на тимусе без всяких симплексов и конвекс холов.
Для каждого человека у нас есть N - 1 уравнений length1 * x + length2 * y + length3 * z < 0
взяв length3 за 1, получаем N - 1 полуплоскостей.
каждая из точек пересечения полуплоскостей дает нам возможный length1 и length2
Получилось O(N^4) но на практике работает быстро.
65 2010-05-18 10:13:40
Re: Задача (6 ответов, оставленных в Problems)
Идейно код выглядит правильно. Попробуй только добавить +/- eps в местах где ты сравниваешь double типы.
67 2010-04-22 15:27:54
Re: задача на дерево отрезков (10 ответов, оставленных в Problems)
Спасибо, интересно.
Ужать координаты только для такой задачи не получится... Но в этом случае вместо дерева отрезков можно, например, декартово дерево взять с этого сайта.
Потестировать алгоритм можно на http://www.spoj.pl/problems/GANNHAT/
68 2010-04-16 13:16:34
Тема: небольшая опечатка (1 ответов, оставленных в Feedback)
на http://www.e-maxx.ru/algo/binomial_coeff
вместо
for (int i=n-k+1; i<=n; ++k)
нужно бы
for (int i=n-k+1; i<=n; ++i)
69 2010-04-16 13:12:22
Re: Диаметр графа (13 ответов, оставленных в Algo)
Кстати, наверняка человек это и имел ввиду иначе зачем он указал что граф взвешенный. При взвешенном графе, если конечно вес = длина ребра, диаметр считается по длине пути.
70 2010-04-09 22:22:50
Re: Обход масива (2 ответов, оставленных в Problems)
Ну так идем в начало перепрыгивая через 2, потом назад к S cнова через 2, потом до N прыгая по одному.
На бумажке то порисуй
71 2010-04-08 13:41:33
Re: timus 1557 (4 ответов, оставленных в Problems)
Определенно с N*M не пройдет.
Получил accepted используя алгоритм с http://wenku.baidu.com/view/cde30c22590 … 09c25.html
Выглядит как китайская грамота но разобраться можно.
72 2010-02-20 00:10:59
Тема: EOPERA с SPOJ (0 ответов, оставленных в Problems)
Давно ломаю голову над
http://www.spoj.pl/problems/EOPERA/
bfs явно не подойдет - слишком много состояний. Как-то наверное надо сортировать по половинам, но тоже не понятно как.
поделитесь мыслями плз
73 2009-12-25 16:52:17
Re: spoj 2940 (1 ответов, оставленных в Problems)
sqrt декомпозиция + дерево сегментов ее сломали. Тема закрыта
74 2009-12-25 13:56:08
Тема: spoj 2940 (1 ответов, оставленных в Problems)
Вот такая вот интересная задачка.
http://www.spoj.pl/problems/UNTITLE1/
Можно свести к более постой - как нам организовать массив из N чисел что б
после операции когда мы к первому числу прибавили K ко второму 2K... к последнему NK
мы смогли за O(1) или хотя бы O(log(N)) опеределить какое теперь число наибольшее в массиве.
Есть идеи ?
75 2009-12-12 17:37:36
Re: Футбольные парадоксы (2 ответов, оставленных в Problems)
Можно и одномерным - только нужно запоминать все считывыемые строчки и вместо p[s1] = s2; тебе нужно p[s1] = номер_строчки и на каждой строчке тоже держать best_prev[строчка] = предыдущая строчка.