Статья Автор: Лебедев Дмитрий

ЕГЭ_27-24 Разница интервалов. Часть 2

Z-функция. Префикс-функция
По мотивам задания 27 ЕГЭ-24 (Основная волна 07.06.24) /Источник - Задание № 17538.kompege.ru
Часть 2. Эффективное решение (для файла B)
Часть 1. Переборное решение (для файла A). 
 

Постановк задачи.
(По мотивам задания 27 ЕГЭ-24 (Основная волна 07.06.24) 

Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 0.
Обозначим S(L, R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S,
начиная с элемента с номером L и заканчивая элементом с номером R.
Ваша задача найти такие значения номеров элементов L, M, R, где \(0\leq L<M<R-1 <N-1 \) 
(т. е. между элементами с номерами M и R есть ещё как минимум один элемент),
чтобы разность суммы элементов подпоследовательноcти S(M+1, R)
и суммы элементов подпоследовательности S(L, М) была максимальна.
В ответе укажите максимальное значение разности подобных сумм.

Входные данные
Дан список целых чисел 
Выходные данные
Ответ на задание: максимально возможное значение sum(S(M+1, R)) - sum(S(L, М)) и значение L,M,R
Если таких наборов L,M,R несколько, то выведите наименьший в лексико-графическом значениии????

 
Items Ожидаемый результат Пояснение
20, 4, -2, 13, -1, 2, -10  12, 1, 2, 5  M может принимать значения от 1 до 4 
Оптимальным оказываются значения 
M=2, R=5 и L=1, тогда значение разности
равно (13+(-1)+2)- (4+(-2))=14-2-12

 


В части 1 было представлено переборное решение, для оптимизации которого использоваличь "префиксные суммы"
В это части будет предложено более эффективное решение, которое можно разбить на два этапа

  • предварительная обработка - создание списков/стеков префиксных сумм и "поддержки максимумов"
  • линейный перебор с вычисление результата 

 


Построение эффективного решения.
Пусть \(A_0,A_1,\cdots,A_{N-1} \) элементы последовательности. Размер последовательности равен N
Положим:
  • \(AA=[A_0,A_1,\cdots,A_{n-1}] \) - список элементов
  •   \(B_j=A_0+\cdots+A_j=\Sigma_{i=0}^{j}\ A_i\) ;  \(BB=[B_0,\cdots, B_{N-1}] \) - список/стек префиксных сумм
  • \(D_j=max([B_0,\cdots, B_j])=max(Bi\ | i=0,\cdots,j)\); \(DD=[D_0,\cdots, D_{N-1}] \) - стек префиксных максимумов массива BB
  • \(E_j=max([B_j,\cdots, B_{n-1}])=max(Bi\ | i=j,\cdots,n-1)\); \(EE=[E_0,\cdots, E_{N-1}] \) - стек суффиксных максимумов массива CC
Тогда:
  •  \(sum(S_{(M+1,R)})=B_R-B_M\)
  • \(\ sum(S_{(L,M)}) = \begin{cases} B_M-B_{L-1} & \quad \text{if }\ L>0\\ B_M & \quad \text{if }\ L==0 \end{cases} \)
  • Следовательно \(sum(S_{(M+1,R)})-sum(S_{(L,M)})=B_R-B_M-(B_M-B_{L-1})=B_R+B_{L-1}-2\cdot B_M\ \ \ \ \ \ (1)\)
При фиксированном значении М, значение (1) будет максимальным при максимальных BR, BL-1,
Обозначим через FM - максимальное значение (1) при фиксированном M.
Если учесть, что \(0\leq L<M<R-1<N-1\), 
Можно утверждать, что \(F_M=E_{M+2}+max(D_{M-1},0)-2\cdot B_M\)

Таким образом, для выполнения задания, на предварительном этапе, необходимо по значениям списка AA
построить списки BB, DD, EE
 


Итоги
Эффективное решение работает за O(N) и для последовательности из файла B выполняет задание быстрее 2 секунд.
Для построения эффективного решения потребовалось несколько просмотров последовательности
для предварительной подготовки:
  • построения списка префиксных сумм
  • стека поддержки максимальных значений префиксных сумм при просмотре "слева"
  • стека поддрежки максимальных значений префиксных сумм при просмотре "справа"
В формулировке задания на ЕГЭ не требовался поиск индексов, что упрощает решение, однако для отладки и
понимания процесса это дополнение полезно. Сложность предложенного алгоритма  O(N)
 

Прикрепленные файлы
27_A_17538.txt
27_B_17538.txt
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать