Overview

Given a log consisting of \(N\) parts, we want to cut it at \(K\) locations to divide it into \(K+1\) fragments, minimizing the maximum length among the fragments. This can be solved using the classic technique of binary search on the answer.

Analysis

Key Insight: “Fix the answer”

This problem has the form “minimize the maximum value.” For this type of problem, the approach of fixing the answer value \(M\) first and then determining whether it is achievable is extremely effective.

Specifically, we consider the following decision problem:

“Can we divide the log using at most \(K\) cuts so that each fragment has length at most \(M\)?”

If we can answer this decision problem, we can efficiently find the value of \(M\) using binary search.

Why a naive approach doesn’t work

There are \(\binom{N-1}{K}\) ways to choose the cut positions, and when \(N\) is large, exhaustive search is far too slow.

Greedy solution for the decision problem

Determining whether we can divide the log with a maximum length of \(M\) or less can be done greedily in \(O(N)\). We add parts from left to right, and whenever the running total exceeds \(M\), we make a cut there and start a new fragment. If the number of cuts needed is at most \(K\), we judge it as “achievable.”

Concrete example

When \(A = [3, 5, 4, 7, 3]\), \(K = 2\):

• Try \(M = 10\) → \([3,5]\) (sum 8), \([4]\) then adding 7 gives 11 > 10 so cut → \([4,\,]\) cut and \([7,3]\) (sum 10) → 2 cuts → OK
• Try \(M = 9\) → \([3,5]\) (8), adding 7 to \([4]\) gives 11 > 9 → cut, adding 3 to \([7]\) gives 10 > 9 → cut → 3 cuts → NG

Therefore the answer is \(10\).

Algorithm

1. Determine the binary search range

   • Lower bound \(lo = \max(A)\) (no matter how we divide, a single part cannot be split)
   • Upper bound \(hi = \sum A\) (the length when no cuts are made at all)

2. Binary search

   • For \(mid = \lfloor (lo + hi) / 2 \rfloor\), call the decision function can_split(mid)
   • If achievable, set \(hi = mid\) (an even smaller value might be possible)
   • If not achievable, set \(lo = mid + 1\) (a larger value is needed)
   • When \(lo = hi\), that is the answer

3. Decision function can_split(max_len)

   • Add parts from left to right; when the running total exceeds max_len, increment the cut count by 1 and reset the total
   • If a single part exceeds max_len, immediately return False
   • If the final cut count is at most \(K\), return True

Complexity

• Time complexity: \(O(N \log S)\) (where \(S = \sum A_i\))
  • The binary search loop runs \(O(\log S)\) times, and each decision check takes \(O(N)\)
• Space complexity: \(O(N)\) (for storing the array \(A\))

Implementation Notes

• By setting the lower bound of the binary search to \(\max(A)\), the case where “a single part exceeds max_len” will not occur after the initial check within the decision function, but a guard condition is included for safety.

• In the greedy approach, when “the total exceeds max_len, make a cut,” the new fragment after the cut starts from the part that caused the excess (current = a).

• Fast input using sys.stdin.read() is employed to avoid TLE even with large inputs.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    def can_split(max_len):
        cuts = 0
        current = 0
        for a in A:
            if a > max_len:
                return False
            current += a
            if current > max_len:
                cuts += 1
                current = a
        return cuts <= K
    
    lo = max(A)
    hi = sum(A)
    
    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(mid):
            hi = mid
        else:
            lo = mid + 1
    
    print(lo)

solve()

---

This editorial was generated by claude4.6opus-thinking.