JOINSTATE - Editorial

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)

can someone explain for this test case?
input:
5 3
1 2 1 3 2
actual output: 2
but we can get 3 states by combining [1,2] [1,2] & [3]

The answer lies in this line of question :

the government can combine two or more consecutive states to represent a new state

Your are not combining consecutive states for the given test case.

1 Like

ohk understood.

The states have to be next to each other. Hence, there can only be one [1, 2] combination.