Ошибка «Алгоритмическая раздача»

Это проблема HackerRank Алгоритмическая раздача :

  

Вам предоставляется список размеров N, инициализированный нулями. Вы должны выполнить операции M в списке и вывести максимум конечных значений для всех N в списке. Для каждой операции вам даются три целых числа: a, b и k. Значение k должно быть добавлено ко всем элементам: от индекса a до b (оба включительно).

     

Формат ввода

     

Первая строка будет содержать два целых числа N и M, разделенных одним пробелом.
  Следующие строки M будут содержать три целых числа a, b и k .
  Номера в списке пронумерованы из 1 в N

     

Формат вывода

     

Единственное целое число на отдельной строке, содержащее максимальное значение в обновленном списке .

     

Ограничения

     

\ $ 3 ≤ N ≤ 10 ^ 7 \ $
    \ $ 1 ≤ M ≤ 2 \ cdot 10 ^ 5 \ $
    \ $ 1 ≤ a ≤ b ≤ N \ $
    \ $ 0 ≤ k ≤ 10 ^ 9 \ $

     

Пример ввода:

5 3
1 2 100
2 5 100
3 4 100
     

Пример вывода:

200
     

Объяснение

     

После первого обновления список будет 100 100 0 0 0.
  После второго обновления список будет 100 200 100 100 100.
  После третьего обновления список будет 100 200 200 200 100.
  Таким образом, требуемый ответ будет 200.

Это мое решение Python 3:

tempArray = [int(n) for n in input().split(" ")]
N = tempArray[0]
M = tempArray[1]
arr = [0 for x in range(N)]
for i in range(0,M):
    tempArray = [int(n) for n in input().split(" ")]
    for j in range(tempArray[0]-1, tempArray[1]):
        arr[j] = arr[j] + tempArray[2] 
print(max(arr))

Это дает мне ошибку тайм-аута для некоторых тестовых случаев. Я очень мало знаю о временной сложности, но я думаю, что это \ $ O (NM) \ $. Что я делаю неправильно?

12 голосов | спросил enthusiastic 4 J000000Saturday15 2015, 11:36:33

3 ответа


13
  

Ограничения

     

\ $ 3 ≤ N ≤ 10 ^ 7 \ $
    \ $ 1 ≤ M ≤ 2 \ cdot 10 ^ 5 \ $
    \ $ 1 ≤ a ≤ b ≤ N \ $
    \ $ 0 ≤ k ≤ 10 ^ 9 \ $

Вы должны убедиться, что каждое значение, которое вы читаете у пользователя, является допустимым значением в вашей программе.

Что касается сложности, то это дерево суффиксов со сложностью \ $ O (N \ log {} N) \ $ по сравнению с вашим текущим решением \ $ O (MN) \ $, которое добавляет разницу к каждому значению в диапазон \ $ [A, B] \ $. С \ $ N \ sim 10 ^ 7 \ $ решение \ $ O (N \ log {} N) \ $ может быть слишком медленным.

Для этой проблемы я бы использовал максимальное префиксное суммирование в разностном массиве. Чтобы сгенерировать набор различий в диапазоне, мы корректируем \ $ arr_ {a} \ mathrel {{+} {=}} k \ $ и \ $ arr_ {b + 1} \ mathrel {{-} {=}} k \ $. Возвращаясь к вашим примерным данным, ваш разностный массив будет выглядеть так:

         #   1.......................N...N+1
5 3      #   0     0     0     0     0     0
1 2 100  # 100     0  -100     0     0     0       
2 5 100  # 100   100  -100     0     0  -100
3 4 100  # 100   100     0     0  -100  -100

Чтобы вычислить максимальную сумму префикса, скопируйте разностный массив в \ $ N \ $ при максимальном накопленном префиксе. (*) обозначает новый найденный максимум.

DiffArray  100  100    0    0  -100  -100
PrefixSum  100*
Max = 100

DiffArray  100  100    0    0  -100  -100
PrefixSum       200*
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum            200
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum                 200
Max = 200

DiffArray  100  100    0    0  -100  -100
PrefixSum                       100
Max = 200

Построение разностного массива в \ $ O (M) \ $ и нахождение максимальной суммы префикса в \ $ O (N) \ $ приводит к линейному алгоритму \ $ O (M + N) \ $.

ответил Snowhawk 5 J000000Sunday15 2015, 00:03:54
5

Несколько общих предложений стиля кодирования:

  • Вместо назначения M и N в отдельных строках, вы можете использовать распаковку:

    N, M = tempArray
    
  • Я бы использовал разные имена переменных для первой строки ввода и всех последующих строк. Например:

    init_line = [int(n) for n in input().split()]  # split() defaults to whitespace
    size_of_list, number_of_operations = init_line
    
    for i in range(number_of_operations):
        this_line = [int(n) for n in input().split()]
        # Do some stuff
    

    Я также изменил имена других переменных: M и N были заменены более описательными именами, а соглашение Python - использовать snake_case, а не dromedaryCase

    Или даже лучше, вы можете просто полностью удалить эти переменные:

    size_of_list, number_of_operations = [int(n) for n in input().split()]
    
    for i in range(number_of_operations):
        a, b, k = [int(n) for n in input().split(" ")]
    

    Обратите внимание на распаковку кортежа для a, b и k: это упрощает логику, если у нас есть эти именованные переменные.

  • В обратном порядке M /number_of_operations, так как значение i не используется, обычно используется вместо подчеркивания:

    for _ in range(number_of_operations):
    

Сложность времени - это фактически \ $ O (MN) \ $, потому что существует внешний цикл длины M и внутренний цикл длиной N и одним добавлением для каждого шага.

Я не вижу хорошего способа улучшить временную сложность. Некоторые люди предложили другие структуры данных в комментариях, но я не знаю достаточного количества CS, чтобы предложить его сам.

ответил alexwlchan 4 J000000Saturday15 2015, 13:45:35
1

Позвольте мне привести свой ответ из Hackerrank обсуждение .

Объяснение:

Прямая реализация начинается с массива \ $ s [i] = 0 \ $ для \ $ i \ in \ {1, \ dotsc, n \} \ $ и выполняет модификации \ $ m \ $, где элементы \ $ s [j] \ $ для \ $ j \ in \ {a_j, \ dotsc, b_j \} \ $ получают значение \ $ k_j \ $.

Это понадобится     $$ \ sum_ {j = 1} ^ m \ lvert \ {a_j, \ dotsc, b_j \} \ rvert \ approx m \ frac {n} {2} $$ операций, поэтому это \ $ O (m n) \ $. Ограничения требуют обработки до \ $ m = 2 \ cdot 10 ^ {5} \ $ и \ $ n = 10 ^ 7 \ $, что приводит к примерно $ 10 ^ {12} \ $ операциям, которая находится за пределами данных ресурсов .

вышеописанное решение управляет необходимостью \ $ m \ $ шаги настройки и заключительный шаг интеграции, посещая не более $ \ n \ $ элементов массива, поэтому это \ $ O (\ max \ {m, n \}) \ $. Для ограничений требуются не более чем $ \ $ \ cdot 10 ^ 7 \ $ шагов, которые можно вычислить с заданными ресурсами.

Подробно:

Начнем с непрерывного случая:

Начнем с постоянной функции \ $ s_0 (t) = 0 \ $, а затем добавим модификации \ $ m \ $, пройдя последовательность модифицированных функций \ $ s_i (t) \ $.

Учитывая \ $ s_i (t) \ $ и добавляя значение \ $ k \ $ для всех времен \ $ t \ in [a, b] \ $, это приводит к модифицированной функции     $$ \ {Начать выравнивать} S_ {+ 1} (т) & = s_i (t) + k \, \ chi _ {[a, b]} (t) \\ & = s_i (t) + k \, \ text {Rect} _ {[a, b]} (t) \\ & = s_i (t) + k \, \ Theta (t-a) - k \, \ Theta (t-b) \ Конец {} Align $$ где \ $ \ chi_I \ $ - характеристическая функция множества \ $ I \ $ и \ $ \ Theta (t) \ $ - распределение Хевисайда     $$ \ Theta (t) = \ BEGIN {случаи} 0 & t <0 \\ 1 & t> 0 \ конец {случаи} $$ Производная     $$ \ dot {s} _ {i + 1} (t) = \ dot {s} _i (t) + k \ delta (t-a) - k \ delta (t-b) $$ где \ $ \ delta \ $ - распределение Дирака.

Для дискретного случая это, похоже, превращается в     $$ \ Delta s_ {i + 1} [t] = \ Delta s_i [t] + k \ delta [t-a] - k \ delta [t-b + 1] $$ с     $$ \ delta [n] = \ BEGIN {случаи} 1 & n = 0 \\ 0 & n \ ne 0 \ конец {случаи} $$

Таким образом, моделирование производной \ $ \ Delta s [t] \ $ очень эффективно, только запись изменений на границах интервалов.

После \ $ m \ $ модификаций константной нулевой функции получаем:     $$ \ Delta s [t] = \ sum_ {j = 1} ^ m k_j \ delta [t-a_j] - k_j \ delta [t-b_j + 1] $$

Наконец, \ $ s \ $ восстанавливается суммированием (интегрированием) \ $ \ Delta s \ $ over \ $ t \ $:     $$ s [t] = \ sum _ {\ tau = 1} ^ t \ Delta s [\ tau] $$ где мы использовали \ $ t_ \ min = 1 \ $ как наименьшее значение.

ответил mvw 24 SunEurope/Moscow2017-12-24T23:13:52+03:00Europe/Moscow12bEurope/MoscowSun, 24 Dec 2017 23:13:52 +0300 2017, 23:13:52

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132