nlogn, при помощи дерева отрезков
2 2012-07-19 10:41:10
Re: Поиск подотрезка с максимальной суммой. (4 ответов, оставленных в Algo)
казалось бы, можно написать простое дерево отрезков, в каждой вершине которого хранятся такие функции:
1. максимальный подотрезок
2. максимальный префикс
3. максимальный суффикс
4. сумма отрезка
тоже online за O(log(n))
3 2012-07-18 08:06:41
Тема: Суффиксный автомат. Наибольшая общая подстрока нескольких строк. (1 ответов, оставленных в Algo)
Предлагаю алгоритм, немного лучший, чем описанный здесь: http://e-maxx.ru/algo/suffix_automata#27.
Будем решать задачу как для двух строк, то есть построим автомат для первой строки S[0], будем бежать по префиксам второй S[k] и находить максимальный суффикс этого префикса, входящий в S[0]. Всё, как в соостветсвующей статье, но при этом будем запоминать, например в массив nowlen[], что для состояния V мы нашли длину Len. После обработки строки, нужно вспомнить, что у состояний есть суффиксные ссылки, а значит эти длины нужно "просеить" вверх по этим ссылкам. Если L = link[V], то nowlen[L] = min(len[L], nowlen[V]). Чтобы это сделать за O(n) можно отсортировать состояния по длине какой-нибудь линейной сортировкой (списочной или поразрядной), и пробежаться от большего к меньшему. Теперь пусть у нас есть для предыдущих k-1 строк ответ на задачу, но в неявном виде: ans[V] - это максимальная длина состояния V, что оно входит в первые k-1 строк. В явном виде ответ - это максимум на этом массиве. Осталось самое простое - объединить результаты ans и nowlen, очевидно, что ans[V] = min(ans[V], nowlen[V]). Изначально ans равен длинам сотояний в S[0].
У алгоритма получилась такая же ассимптотика, но он гораздо выгоднее по памяти. Во-первых нет разделителей, а значит меньше алфавит, во вторых автомат нужно строить только для одной строки, лучше для самой короткой.
P.S. можно добавить задачу "1227 - The longest constant gene" с uva
4 2012-01-15 11:01:40
Re: Теория чисел. Факторизация. Проверка на простоту (3 ответов, оставленных в Algo)
несколько месяцев назад этим занимался, тоже выискивал методы, комбинировал их. по теме скажу, что у меня в реализации применяется следующая комбинация:
- проверить на простые до 10^6 (10^7)
далее рекурсия:
- проверка на простое Миллером-Рабином
- Монте-Карло
- если не нашли делитель, то Ро
- если не нашли делитель, то Ферма
Я заметил, что Монте-Карло очень сильно вывозит ситуацию на некоторых тестах, и, в частности, на этом.
Реализовывал по основе этого: http://algolist.manual.ru/maths/teornum … /monte.php (второй метод)