Не понимаю, что не так с моим решением [решено]

Правка ru6, от dmkz, 2018-06-14 16:53:11

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

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

Мое решение: пусть сумма всех элементов массива равна S, а k — количество отрезков, сумма в которых равна s. Тогда выполняется тождество S = s * k. Для каждого делителя S проверяю явно, можно ли сформировать k отрезков. Особый случай: когда сумма всех элементов равна 0, тогда возможны все значения k от 1 до n. Сначала проверяю, есть ли отрезок [l, r) (0 ≤ l < r < n): sum[l...r - 1] = s, затем от r до l прохожу, формируя остальные отрезки. Решение проходит 30 тестов, а на 31-м вердикт Wrong Answer.

UPD: Задача сдана, вот код. Прошло за 1.5 секунды следующее решение: для каждого делителя s суммы всех элементов S для каждого отрезка [l, r], содержащего нулевой элемент, при помощи бин.поиска и префикс-сумм пробуем построить еще S div s  -  1 отрезков, сумма на которых в точности равна s. Предыдущее решение было неверное в силу его жадности при поиске отрезка: нужно смотреть все отрезки.

Теги проблема с задачей

История

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