1

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

nlogn, при помощи дерева отрезков

2

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

казалось бы, можно написать простое дерево отрезков, в каждой вершине которого хранятся такие функции:
1. максимальный подотрезок
2. максимальный префикс
3. максимальный суффикс
4. сумма отрезка
тоже online за O(log(n))

Предлагаю алгоритм, немного лучший, чем описанный здесь: 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

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

несколько месяцев назад этим занимался, тоже выискивал методы, комбинировал их. по теме скажу, что  у меня в реализации применяется следующая комбинация:
- проверить на простые до 10^6 (10^7)
далее рекурсия:
- проверка на простое Миллером-Рабином
- Монте-Карло
- если не нашли делитель, то Ро
- если не нашли делитель, то Ферма

Я заметил, что Монте-Карло очень сильно вывозит ситуацию на некоторых тестах, и, в частности, на этом.
Реализовывал по основе этого: http://algolist.manual.ru/maths/teornum … /monte.php (второй метод)