# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

Dynamic Programming, Binary Search, Range Minimum Queries, Coordinate Compression

# PROBLEM:

Given array A and integer K. Determine the largest value s such that, it is possible to partition A into K contiguous blocks, where the sum of elements of each block is \ge s.

# EXPLANATION:

Let s be the largest integer such that it is possible to partition A into K contiguous blocks, where the sum of elements of each block is \ge s. This value is the answer we are looking for.

**Step 1:** Use binary searching to find the value of s.

## Why? How?

Let solve(d) represent whether it is possible to partition A into K blocks, where the sum of elements of each block is \ge d. Let solve(d) equal 1 if it’s possible to partition, and 0 otherwise.

**Observation 1:** If solve(d)=1, then solve(d')=1 for all d\ge d'.

(The proof is trivial and left to the reader as an exercise)

**Observation 2:** If solve(d)=0, then solve(d')=0 for all d'\ge d.

## Proof

We prove by contradiction.

Say there exists d'\ge d such that solve(d)=0 and solve(d')=1.

By the previous observation, solve(d')=1 implies solve(x)=1 for all d'\ge x. But solve(d)=0 - a contradiction and we are done.

The two observations imply the monotonic structure of the function solve, sufficiently allowing us to binary search to find the answer.

Let d be the currently considered value in the binary search. Now, we want to check if it’s possible to partition A into K blocks, each whose sum \ge d.

**Definition:** Call an array of elements *good*, if the sum of its elements \ge d.

Let dp_i be the set of all positive integers k, such that it is possible to partition the first i elements of A into k good subarrays. I claim that dp_i is a (possibly empty) set of consecutive integers, for all i.

## Proof

*Since the proof has a lot in common with the logic of the solution, reading the rest of the editorial first will make the proof much more clearer.*

Let pref(x)=A_1+A_2+\dots+A_x.

Computing dp_i is straightforward, and can be described mathematically as:

Let’s define G_i[v] as the set of integers x, such that it is possible to partition the first j elements of A into x good subarrays, where j<i and pref(j)=v.

This recurrence is derived from a simple (yet important!) observation, the proof of which is left to the reader as an exercise.

Finally (the last definition, bear with me), let’s define H_i[v] = G_i[v]\cup H_i[v-1]. That is, H_i[v] is the union of all sets G_i[v'] with v'\le v. It is easy to deduce that H_i[v'] is always subset of H_i[v].

Informally, H_i[v] can be described as the set of integers x, such that it is possible to partition the first j elements of A into x good subarrays, where j<i and pref(j)\le v.

Then, we can rewrite the set relation of dp_i (mentioned at the start) as:

Thus, if we prove that H_i[v] is a (possibly empty) set of consecutive integers for all v, then dp_i is also a (possibly empty) set of consecutive integers, completing the proof.

We prove by induction.

Assume for a particular n, H_n[v] is a set of consecutive integers, for all v. Let us prove by inducting on n.

H_{n+1}[v] = H_n[v] implies our proposition holds for H_{n+1}[v] (since by our assumption, it holds for H_n[v]). So, lets only focus on the former case, which can be expanded as:

One of H_{n+1}[v], H_n[pref(n)-d] is a subset of the other. A bit of case work shows that, the union of two overlapping sets of consecutive integers, after shifting all values of one set by 1, is still a set of consecutive integers. Therefore, the proposition holds true for H_{n+1}[v], establishing the inductive step.

The trivial case of n=0 has H_0[v]=\varnothing for all v, which matches our proposition.

Thus proved.

Why is this claim important? The claim implies that the set of values of dp_i is made up of all integers in some range [L_i,R_i]. Then, A can partitioned into K good subarrays only if L_N\le K\le R_N.

All that remains now is to calculate L_i and R_i efficiently.

## Suboptimal solution

A straightforward DP recurrence relation gives:

where j<i and \sum_{x=j+1}^i A_x \ge d.

This can be calculated in O(N^2), enough for subtask 2, but not viable for the original constraints.

## Optimised solution

Let pref(x)=A_1+A_2+\dots+A_x.

The suboptimal solution can be rewritten as:

where j<i and pref(i)-pref(j) \ge d\implies pref(j)\le pref(i)-d.

Let mini_x represent the set of all L_j such that, j<i and pref(j)=x. Similarly, let maxi_x represent the set of all R_j such that, j<i and pref(j)=x.

Then, from the above stated recurrence constraint, it is easy to see

This can be done easily using range minimum queries on mini and maxi, typically using a Segment Tree/Fenwick Tree with coordinate compression (since the range of x in mini_x/maxi_x is [-1e14, +1e14]).

The time complexity of this approach is O(N\log N), which is efficient enough to AC for the given constraints!

To summarise, binary search for the answer - let the midpoint value we are currently trying be d. For this particular d, calculate [L_i,R_i] for all i, in subquadratic time. Then, A can be partitioned into K subarrays, each with sum of elements \ge d, only if L_N\le K\le R_N. Return the result and continue the binary search until it converges.

# TIME COMPLEXITY:

Binary searching for the answer takes O(\log S), where S is the size of the answer space (S\le 2\times10^{14}). Calculating [L_i, R_i] for each d (using the memory efficient method) takes O(N\log N).

The total time complexity is therefore

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here.

Author’s solution can be found here.

Tester’s solution can be found here.

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters