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

Equal Cut Atcoder
Автор icpc_expert, история, 6 лет назад, По-английски

Can anybody tell me how to solve Atcoder question Equal cut. The question is Cut the array at 3 positions such that difference of maximum sum of any one part and minimum sum of another part is minimum?

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

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

Quick summary:

Fix the position of the second (middle) cut. Then, the optimal left cut is the one which splits the left side approximately equally (as best as possible). Similarly for the best right cut. This can be found by binary searching on a prefix sum array (or 2-pointers, your preference).

Answer is the minimum across all possible second cuts.

Editorial's out, btw: Here

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

    So according to you we should iterate over all the possible middle position. Then for each middle position we have to split the part to its left and the part to its right almost equally but how can we do that Can you have your code which is explaining your idea.(i.e using binary search).

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

      Exactly. Finding the position to split is done by creating a prefix array of the original array, and binary searching on that.

      My code for reference.

      → Ответить