Блог пользователя Yura_Sultonov

HackerRank, задача: Omar Loves Candies
Автор Yura_Sultonov, история, 9 лет назад, По-русски

Я интересуюсь алгоритмами. Два года назад я научился находить такой подматрицу [L1...R1, L2...R2] заданной матрицы, которая имеет максимальную сумму чисел в ней. Этот алгоритм работает за O(N3). Но, я увидел одну задачу на HackerRank, в этой задаче нужно находить максимальную сумму за O(N2). Я искал через интернет, но не нашёл такого алгоритма, идей тоже нету. Вот ссылка для задачи: link. У кого есть какие идеи, если кто-то решал, помогите пожалуйста. Заранее спасибо!

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Вообще я слышал про некий алгоритм Тадао Такаока, который решает данную задачу за О(N^3*loglog(N)/log(N))... В интернете я нашел этот алгоритм, но он мне показался очень сложным,вот ссылка http://habrahabr.ru/post/136188/... Лично я умею решать эту задачу за О(N^4) с двумерными префиксными суммами, и мне интересно как решать за О(N^3) опишите ваш алгоритм

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Перебираем верхнюю и нижнюю границу, дальше превращаем обычный массив. В обычном массиве легко можно решить за O(N). В сумме O(N^3)

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Цитата из условия: "They noticed something else, any candy (except for those in the first row) is healthier than the candy which is exactly above it, and any candy (except for those in the first column) is healthier than the candy which is exactly to its left (healthier means having higher score as defined above)." (это важно)
Решение

→ Ответить