Здравствуйте! На acmp.ru есть [интересная задача](https://acmp.ru/asp/do/index.asp?main=task&id_course=3&id_section=25&id_topic=175&id_problem=1151) — самая сложная задача с полуфинала ВКОШП 2016/2017 Красноярского края. Ниже приведу краткое условие.↵
↵
Есть циклический массив длины $n$ $(1 \le n \le 10^5)$ из целых неотрицательных чисел (все его элементы расположены по кругу), сумма элементов которого не превосходит $10^9$. Требуется для каждого $k$ от $1$ до $n$ определить, можно ли разбить отрезок $[1..n]$ массива на $k$ непересекающихся отрезков, сумма элементов в которых равна и каждый элемент покрыт хотя бы одним отрезком. Так как массив циклический, то за элементом с индексом $n$ следует элемент с индексом $1$, таким образом, последний отрезок может переходить через границу массива.↵
↵
Раньше этот пост содержал просьбу помочь, так как не проходило [мое решение](https://ideone.com/rgmJZC). После обсуждения и изучения контр-тестов, предоставленных [user:YANORMALNOSUPERGOOD,2018-06-145], выяснилось, что это решение и не должно проходить, так как оно основывается на жадности, после чего было придумано следующее [решение](https://pastebin.com/VJGNg4FA): для каждого делителя $s_i$ суммы всех элементов $S$ для каждого отрезка $[l, r]$, содержащего начальный элемент массива, при помощи бинарного поиска и префикс-сумм предпринимается попытка построить еще $k_i = $ $\dfrac{S}{s_i}-1$ отрезков $(k_i \le n)$, сумма на которых в точности равна $s_i$. Если я ничего не перепутал, то это решение занимает $O(count(k_i) \cdot n + sum(k_i) \cdot log(n)) \approx O(n^{4/3} \cdot log(n) \cdot log(log(n)))$ по времени. На сервере оно работает за 1.5 секунды.↵
↵
Вопрос: можно ли решить оптимальнее, легче (возможно, за один проход по массиву), и нет ли контр-тестов, которые должны вызывать TLE у решения выше?↵
↵
UPD: [user:AeonHQ,2018-06-15] и [user:YANORMALNOSUPERGOOD,2018-06-15] показали, что оптимальнее решить можно, а именно, за время $O(n \cdot numberOfDivisors(S) $. Причем, в оценке участвуют только делители, которые не превосходят n. Ключевой момент — избавиться от бинарного поиска, который выполнялся sumOfDivisors(S) раз. Для этого можно перейти к динамическому программированию и для одного делителя предподсчитать определенную величину, которая позволит за O(1) отвечать на запрос о максимальном количестве искомых отрезков. Решения с указанной асимптотикой приведены в комментариях [здесь](http://codeforces.net/blog/entry/60015?locale=ru#comment-437478) и [здесь](http://codeforces.net/blog/entry/60015?locale=ru#comment-437475). ↵
↵
Возможно, асимптотику можно еще улучшить, воспользовавшись тем фактом, что если мы выяснили, что для какого-то делителя суммы ответ 0, то и для всех делителей, кратных ему, ответ 0, а если для какого-то делителя ответ 1, то и для всех делителей, на которые он делится, ответ 1.
↵
Есть циклический массив длины $n$ $(1 \le n \le 10^5)$ из целых неотрицательных чисел (все его элементы расположены по кругу), сумма элементов которого не превосходит $10^9$. Требуется для каждого $k$ от $1$ до $n$ определить, можно ли разбить отрезок $[1..n]$ массива на $k$ непересекающихся отрезков, сумма элементов в которых равна и каждый элемент покрыт хотя бы одним отрезком. Так как массив циклический, то за элементом с индексом $n$ следует элемент с индексом $1$, таким образом, последний отрезок может переходить через границу массива.↵
↵
Раньше этот пост содержал просьбу помочь, так как не проходило [мое решение](https://ideone.com/rgmJZC). После обсуждения и изучения контр-тестов, предоставленных [user:YANORMALNOSUPERGOOD,2018-06-1
↵
Вопрос: можно ли решить оптимальнее, легче (возможно, за один проход по массиву), и нет ли контр-тестов, которые должны вызывать TLE у решения выше?↵
↵
UPD: [user:AeonHQ,2018-06-15] и [user:YANORMALNOSUPERGOOD,2018-06-15] показали, что оптимальнее решить можно, а именно, за время $O(n \cdot numberOfDivisors(S) $. Причем, в оценке участвуют только делители, которые не превосходят n. Ключевой момент — избавиться от бинарного поиска, который выполнялся sumOfDivisors(S) раз. Для этого можно перейти к динамическому программированию и для одного делителя предподсчитать определенную величину, которая позволит за O(1) отвечать на запрос о максимальном количестве искомых отрезков. Решения с указанной асимптотикой приведены в комментариях [здесь](http://codeforces.net/blog/entry/60015?locale=ru#comment-437478) и [здесь](http://codeforces.net/blog/entry/60015?locale=ru#comment-437475). ↵
↵
Возможно, асимптотику можно еще улучшить, воспользовавшись тем фактом, что если мы выяснили, что для какого-то делителя суммы ответ 0, то и для всех делителей, кратных ему, ответ 0, а если для какого-то делителя ответ 1, то и для всех делителей, на которые он делится, ответ 1.
