Official

A - Partition Editorial by evima


If \(K \geq 1\)

By sorting \(A\) in ascending order, it can always be made into a good sequence.

Assume \(A\) is sorted in ascending order. Let \(B\) be the cumulative sums of \(A\).

Values in \(A\) that are less than \(0\) appear before values that are \(0\) or greater. Therefore, \(B\) can be represented as a concatenation of a strictly decreasing sequence and a non-decreasing sequence. Thus, when looking at the elements of \(B\) in order of increasing indices, after starting from \(B_0 = 0 < K\) and decreasing for a while, it begins to increase from a value less than \(K\). Once it becomes \(K\) or greater, it remains so thereafter. Therefore, \(A\) is a good sequence.

If \(K \leq 0\) and \(\displaystyle\sum_{i=1}^{N}A_i \geq K\)

By sorting \(A\) in descending order, it can always be made into a good sequence.

Assume \(A\) is sorted in descending order. Let \(B\) be the cumulative sum of \(A\).

Values in \(A\) that are \(0\) or greater appear before values that are less than \(0\). Therefore, \(B\) can be represented as a concatenation of a strictly increasing sequence and a non-increasing sequence. Thus, when looking at the elements of \(B\) in order of increasing indices, after starting from \(B_0 = 0 \geq K\) and increasing for a while, it begins to decrease from a value not less than \(K\). Since \(B_0 \geq K\), it is \(K\) or greater from the start, and since \(B_N = \displaystyle\sum_{i=1}^{N}A_i \geq K\), it remains \(K\) or greater until the end. Therefore, \(A\) is a good sequence.

If \(K \leq 0\) and \(\displaystyle\sum_{i=1}^{N}A_i < K\)

No matter how \(A\) is rearranged, it cannot be made into a good sequence.

No matter how \(A\) is rearranged, the initial and final terms of the cumulative sum \(B\) of \(A\) are fixed.

Since \(B_0 = 0 \geq K\) and \(B_N = \displaystyle\sum_{i=1}^{N}A_i < K\), it does not satisfy the conditions for a good sequence.

posted:
last update: