51

(10 ответов, оставленных в Feedback)

cpn[ i] =  rmq_get (pos[a], pos[ b] - 1);  вроде ближе к истине для c[a] != c[ b] ...

52

(10 ответов, оставленных в Feedback)

Алгоритм поиска lcp на http://e-maxx.ru/algo/suffix_array не всегда срабатывает sad

В частности if (c[a] != c[ b]) -> lcpn[ i] = lcp[pos[a]];  может быть не верно

для строки "abaabca"

на втором шаге "abca" идет перед "baabca", lcpn копируется с предыдущего и получается равным 1.

53

(10 ответов, оставленных в Problems)

http://acm.timus.ru/problem.aspx?space=1&num=1076

54

(4 ответов, оставленных в Problems)

Смотри проблему Tri и ее решение http://www.ceoi2009.ro/view_page.php?id=24

55

(1 ответов, оставленных в Feedback)

На http://e-maxx.ru/algo/schedule_with_completion_duration

строчку с "t = 0;" нужно поменять местами со следующей за ней.

56

(5 ответов, оставленных в Algo)

Вот тут можно скопипастить
http://acm.mipt.ru/twiki/bin/view/Algorithms/UkkonenCPP

57

(2 ответов, оставленных в Algo)

Спасибо, Егор, за интересные задачи. smile

все-таки  интересно - Максиму повезло (слабость тестов) что его a^(b%phi(с))%c  для a и c не взаимно простых прокатило или все-таки можно и для них ?

58

(11 ответов, оставленных в Problems)

2MSDN: Композиция + segment tree сдается без проблем. Оптимизируй.

59

(7 ответов, оставленных в Problems)

делается двумя dfsами на первом считаешь самую удаленную в _текущем поддереве_
на втором в в параметры dfs а еще добавляешь самую удаленную вершину и путь до нее "снизу" текущего дерева

60

(11 ответов, оставленных в Problems)

Чего-то ты выдумываешь smile
Нарисуй на бумаге небольшое бинарное дерево и сделай его композицию  - когда мы спускаемся с пути на котором лежит A вниз, мы же не попадаем на полный промежуточный путь - а лишь на его часть.

61

(11 ответов, оставленных в Problems)

heavy-light декомпозиция не гарантирует что у нас будет не больше 4х нецелых путей для всех вершин.

Попробуй оптимизировать чтение  / хранение дерева

62

(2 ответов, оставленных в Problems)

Сам себе подсказал. smile

Что б добиться такого времени - храни в sete только точки для текущего круга, а не все вместе. а totalPoints изменяй вручную:

if (i < j && edges.find(p) == edges.end())
   totalPoints++;

Получается экономия и по памяти и по времени.

63

(2 ответов, оставленных в Problems)

Интересно как они в 300 KB укладываются - как-то же надо определить новая эта точка пересечения или нет.
У меня тоже получилось только за 1.3 сдать с похожим алгоритмом.

64

(4 ответов, оставленных в Problems)

Только что получилось сдать  на тимусе без всяких симплексов и конвекс холов.

Для каждого человека у нас есть N - 1 уравнений length1 * x + length2 * y + length3 * z < 0
взяв length3 за 1, получаем N - 1 полуплоскостей.
каждая из точек пересечения полуплоскостей дает нам возможный length1 и length2

Получилось O(N^4) но на практике работает быстро.

65

(6 ответов, оставленных в Problems)

Идейно код выглядит правильно. Попробуй только добавить +/- eps в местах где ты сравниваешь double типы.

66

(10 ответов, оставленных в Problems)

Согласен smile

67

(10 ответов, оставленных в Problems)

Спасибо, интересно.

Ужать координаты только для такой задачи не получится... Но в этом случае вместо дерева отрезков можно, например, декартово дерево взять с этого сайта.

Потестировать алгоритм можно на http://www.spoj.pl/problems/GANNHAT/

68

(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

(13 ответов, оставленных в Algo)

Кстати, наверняка человек это и имел ввиду иначе зачем он указал что граф взвешенный. При взвешенном графе, если конечно вес = длина ребра, диаметр считается по длине пути.

70

(2 ответов, оставленных в Problems)

Ну так идем в начало перепрыгивая через 2, потом назад к S cнова через 2, потом до N прыгая по одному.
На бумажке то порисуй smile

71

(4 ответов, оставленных в Problems)

Определенно с N*M не пройдет.
Получил accepted используя алгоритм с http://wenku.baidu.com/view/cde30c22590 … 09c25.html
Выглядит как китайская грамота wink но разобраться можно.

72

(0 ответов, оставленных в Problems)

Давно ломаю голову над

http://www.spoj.pl/problems/EOPERA/

bfs явно не подойдет - слишком много состояний.  Как-то наверное надо сортировать по половинам, но тоже не понятно как.
поделитесь мыслями плз smile

73

(1 ответов, оставленных в Problems)

sqrt декомпозиция + дерево сегментов ее сломали. Тема закрыта smile

74

(1 ответов, оставленных в Problems)

Вот такая вот интересная задачка.
http://www.spoj.pl/problems/UNTITLE1/

Можно свести к более постой - как нам организовать массив из N чисел что б
после операции когда мы к первому числу прибавили K ко второму 2K... к последнему NK
мы смогли за O(1) или хотя бы O(log(N)) опеределить какое теперь число наибольшее в массиве.

Есть идеи ?

75

(2 ответов, оставленных в Problems)

Можно и одномерным - только нужно запоминать все считывыемые строчки и вместо p[s1] = s2;  тебе нужно p[s1] = номер_строчки и на каждой строчке тоже держать best_prev[строчка] = предыдущая строчка.