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

Автор vamaddur, история, 7 лет назад, По-английски

Problem Statement Solution

Could someone please provide an alternate solution with an explanation to this problem, or explain the official solution with more clarity (I only understand the first two lines)? I do not understand the logic behind precomputing "cost" or how the recurrence works.

Thanks in advance!

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

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

Here is my solution: https://pastebin.com/v8iWX27j

It is similar to the analysis solution. The idea is to first, loop through all 2^15 vertical subsets, and then to binary search on the answer. When we binary search on the answer we want to make sure that no area gets bigger than our current answer, which is how we assign the horizontal lines.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Someone ended up explaining the official sol to me, but upvote for the interesting sol! Is the runtime complexity better than the intended one (fairly sure it is a ratio of logN to N)?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This should be (N^2) (log 225000) (2^N) — probably a little slower, but more understandable to me at least. I set my binary search upper bound to 1e8, but it should really be 225000 based on the info that each grid cell is <= 1000. In this case it is slightly slower than the official solution as log_2 225000 is ~18.