icpc_expert's blog

Equal Cut Atcoder
By icpc_expert, history, 6 years ago, In English

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?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply