Разбиение всего массива на k отрезков с одинаковой суммой [решено, вопрос об оптимальности решения]

Revision ru7, by dmkz, 2018-06-14 23:29:23

Здравствуйте! На acmp.ru есть интересная задача — самая сложная задача с полуфинала ВКОШП 2016/2017 Красноярского края. Ниже приведу краткое условие.

Есть циклический массив длины n (1 ≤ n ≤ 105) из целых неотрицательных чисел (все его элементы расположены по кругу), сумма элементов которого не превосходит 109. Требуется для каждого k от 1 до n определить, можно ли разбить отрезок [1..n] массива на k непересекающихся отрезков, сумма элементов в которых равна и каждый элемент покрыт хотя бы одним отрезком. Так как массив циклический, то за элементом с индексом n следует элемент с индексом 1, таким образом, последний отрезок может переходить через границу массива.

Раньше этот пост содержал просьбу помочь, так как не проходило мое решение. После обсуждения и изучения контр-тестов, предоставленных YANORMALNOSUPERGOOD, выяснилось, что это решение и не должно проходить, так как оно основывается на жадности, после чего было придумано следующее решение: для каждого делителя si суммы всех элементов S для каждого отрезка [l,  r], содержащего начальный элемент массива, при помощи бинарного поиска и префикс-сумм предпринимается попытка построить еще ki =  отрезков (ki ≤ n), сумма на которых в точности равна si. Если я ничего не перепутал, то это решение занимает O(count(kin + sum(kilog(n)) ≈ O(n4 / 3·log(nlog(log(n))) по времени. На сервере оно работает за 1.5 секунды.

Вопрос: можно ли решить оптимальнее, легче (возможно, за один проход по массиву), и нет ли контр-тестов, которые должны вызывать TLE у решения выше?

Tags проблема с задачей

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru8 Russian dmkz 2018-06-15 16:10:10 1029
ru7 Russian dmkz 2018-06-14 23:29:23 1310 Мелкая правка: 't log(n)) ~ O(n^(4/3)' -> 't log(n)) \approx O(n^(4/3)'
ru6 Russian dmkz 2018-06-14 16:53:11 9
ru5 Russian dmkz 2018-06-14 16:51:16 1 Мелкая правка: '1.5 секунд следующее' -> '1.5 секунды следующее'
ru4 Russian dmkz 2018-06-14 16:37:33 436
ru3 Russian dmkz 2018-06-14 14:56:30 6 Мелкая правка: ', r)$ $(0 <= l < r < n' -> ', r)$ $(0 \le l < r < n'
ru2 Russian dmkz 2018-06-14 14:42:32 448
ru1 Russian dmkz 2018-06-14 12:49:26 1394 Первая редакция (опубликовано)