PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: raysh_07
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
There are N states, the i-th has A_i literate people.
Two or more adjacent states can be combined into a single larger one.
What’s the maximum number of states that can exist, such that each one has at least M people?
EXPLANATION:
Combining several adjacent states into one can be thought of as partitioning the given array into subarrays and taking their sum.
Now, observe that you can simply choose these subarrays greedily from the front (or back).
That is, the following algorithm is correct:
- Let \text{sm} denote the sum of the current subarray. Initially, \text{sm} = 0.
- For each i = 1, 2, 3, \ldots, N:
- Add A_i to \text{sm}, meaning we take index i into the current subarray.
- If \text{sm} \geq M, break the subarray immediately: add 1 to the answer, and set \text{sm} back to 0.
This way, we greedily break A into subarrays with sum \geq M.
The last few elements of A might not be taken into any subarray; but that’s ok: that can always just be clubbed with the last taken subarray.
Proof of correctness
Our claim is that we can greedily “cut out” the smallest prefix whose sum is \geq M, and then repeat this process for the remaining part to obtain an optimal solution.
It’s not too hard to prove that this is true.
Consider any optimal solution (meaning a partition of A into the maximum number of subarrays, each of which has sum \geq M).
Let the first subarray be [A_1, A_2, \ldots, A_i].
There are two cases:
- If i = N, we take the whole subarray. If this is optimal, it’s also the only solution (and hence the one our algorithm finds).
- if i \lt N, there’s another subarray starting at i+1.
If A_1 + \ldots + A_{i-1} \geq M, we can move A_i to this second subarray - its sum remains \geq M, the total number of chosen subarrays is the same, and we’ve now chosen a smaller prefix.
Repeat this till the first subarray is as small as possible, thus proving our claim.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
sm, ans = 0, 0
for x in a:
sm += x
if sm >= m:
ans += 1
sm = 0
print(ans)