Let us call a contiguous pieces a segment.

Using binary search, it is sufficient to solve the following decision problem (fast):

- Can the \(N\) pieces be divided into \(K\) segments so that each segment has a mass of at least \(X\)? - If possible, how many cut lines are never used by any division among such ways?

For each \(1 \leq i \leq N\), let us consider whether there exists a conforming division that uses cut line \(i\).

Let us re-define the sequence \(A\) of length \(2N\) by letting \(A_{N + i} \coloneqq A_i\) for all \(i\) with \(1 \leq i \leq N\).

If there exists \(j (\leq 2N + 1)\) such that \(A_i + A_{i + 1} + \ldots + A_{j - 1} \geq X\), let \(f(i)\) be the minimum such \(j\); otherwise, let \(f(i) = \infty\). Also, let \(f(\infty) = \infty\). Using the sliding window trick, \(f\) can be evaluated for all arguments in a total of \(O(N)\) time.

There exists a conforming division that uses cut line \(i\) if and only if \(f^K(i + 1) \leq N + i + 1\).

\(f^K\) can be evaluated in \(O(N \log K)\) time using the doubling technique based on \(f^2, f^4, f^8, \ldots\).

Therefore, the number of \(i\) for which there is a division that uses cut line \(i\) can be counted in \(O(N \log K)\) time. Noticing that there is at least one \(i\) such that cut line \(i\) is used by a division if and only if the \(N\) pieces can be divided into \(K\) segments so that each segment has a mass of at least \(K\), this also solves the decision problem.

Alternatively, evaluating \(f^K\) can be boiled down to the Level Ancestor Problem in a tree which has an edge between \(i\) and \(f(i)\) for each \(i\) with \(i \neq f(i)\), so the decision problem can be solved in \(O(N)\) time too. However, in writer’s and tester’s solution, it was solution that the one using doubling.