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