Partitioning into Three#11811

Partitioning into Three (Editorial)

Problem Author:	Anton Trygub
Problem Prepared by:	Ignat Zharikhin
Editorial Written by:	Ignat Zharikhin

10pt

Block 1( $n = 3$ n = 3)

Obviously, there is only one possible partitioning into three subarrays, each of size one element.

Block 2( $a_{i} \leq 1$ a_i \leq 1)

First, we decide what the sums of the subarrays will be. Let $c n t$ be the number of ones in the array. It is logical to make each subsegment’s sum as close as possible to $⌊ \frac{c n t}{3} ⌋$ \left\lfloor \frac{cnt}{3} \right\rfloor. If $c n t ∣ 3$ cnt \mid 3, then we are fine and we have found the sums. Otherwise, we might still have $1$ or $2$ residual ones that we haven't distributed anywhere. If there is one, we add it to any subarray, and if there are two, we distribute them to any two different subarrays.

When we know the sums, we just traverse the array and add the next element to the current subarray. When we reach its sum (and we cannot skip it because $a_{i} \leq 1$ a_i \leq 1), we close it and open the next one. This way we find the boundaries of the subarrays.

$a + b = c$ a+b=c

Block 3(guaranteed answer $0$ )

We will calculate the total sum of the array, let this be $s u m$ . Additional constraints of this group mean that there is a partitioning where all three subarrays have a sum of $\frac{s u m}{3}$ \frac{sum}{3}. Any subarrays with a different sum do not interest us at all.

For each index $i$ , we will calculate such a minimum index $n e x t_{i} \leq n$ next_i \leq n (if it exists) that the sum on the segment $[a, b)$ is equal to $\frac{s u m}{3}$ \frac{sum}{3}. If it doesn't exist, we remember this.

We traverse the array, iterating over the start of the first subarray — $i$ . If $n e x t_{i}$ next_i doesn't exist, then this start is definitely unsuitable, and we skip it. Then, let $j = n e x t_{i}$ j = next_i. Similarly, it is mandatory that $n e x t_{j}$ next_j exists, otherwise this partitioning is not suitable. If it does exist, we have found all three boundaries between the segments. The first two of them have a sum of $\frac{s u m}{3}$ \frac{sum}{3}, so the third also has the same, hence we have found the answer. Complexity — $O (n)$

Block 4( $n \leq 100$ n \leq 100)

We will completely iterate over the three starts of the subarrays, as suggested in the «output format». Having boundaries $x, y, z$ x, y, z, we calculate the sums just by traversing the array or using prefix sums. Complexity — $O (n^{4})$ \mathcal{O}(n^4) or $O (n^{3})$ \mathcal{O}(n^3), depending on which method to choose.

From now on, all sums will be calculated using prefix sums.

Block 5( $n \leq 2000$ n \leq 2000) and 6( $n \leq 5000$ n \leq 5000)

We will iterate only the first two indices. Now with their help, we have split the array into two subsegments. We leave one of them, and calculate its sum, let this be $s$ . Now we just need to split the second subsegment into two more: prefix and suffix. Notice that many of these splits are definitely not optimal. Intuitively, we are interested in splitting the array into two as equally sum-wise as possible. Theoretically, let's assume that we split such that the sums of the prefix and suffix are $p r e f$ and $s u f f$ respectively. Without loss of generality, let $p r e f \leq s u f f$ pref \leq suff. Suppose that one element of the array (the one that is now at the boundary) can be transferred from the suffix to the prefix (same as shifting the boundary by one), and at the same time, the inequality remains valid. Formally, $p r e f + x \leq s u f f - x$ pref+x\leq suff-x. It will always be beneficial for us to make this transition, because $min (s, p r e f) \leq min (s, p r e f + x)$ \min(s, pref) \leq \min(s, pref+x) and $max (s, s u f f) \geq max (s, s u f f - x)$ \max(s, suff) \geq \max(s, suff-x), thus the answer will not be worse. The only moment when it might be unprofitable to make the transition is when the sign in the inequality changes. Therefore, we actually need to check only two cases: the largest prefix whose sum is less than the sum of the suffix, and conversely, the largest suffix whose sum is less than the sum of the prefix. From all others, we can transition to these, not worsening the answer.

The first implementation variant: after the first two indices are iterated, we find the breakpoint in sums using a binary search, and check these two cases. Complexity — $O (n^{2} \cdot lo g n)$ \mathcal{O}(n^2 \cdot\log n), passes the fifth group.

The second implementation variant: we find the breakpoint using a second pointer, which always moves to the right through the cyclic array. Complexity — $O (n^{2})$ \mathcal{O}(n^2), passes the sixth group.

Block 7( $n \leq 1 0^{5}$ n \leq 10^5) and 8(no additional constraints)

Let the sum of all elements of the array be $s u m$ . Notice that in any partition exactly one of the following two statements is true:

either exactly two arrays have a sum $\leq ⌊ \frac{s u m}{3} ⌋$ \leq \left\lfloor \frac{sum}{3} \right\rfloor and the third has a sum $\geq ⌊ \frac{s u m}{3} ⌋$ \geq \left\lfloor \frac{sum}{3} \right\rfloor,
or exactly two arrays have a sum $\geq ⌊ \frac{s u m}{3} ⌋$ \geq \left\lfloor \frac{sum}{3} \right\rfloor and the third has a sum $\leq ⌊ \frac{s u m}{3} ⌋$ \leq \left\lfloor \frac{sum}{3} \right\rfloor.

We will iterate over the split of the array between two subarrays, both of which have a sum not exceeding a third of $s u m$ . Similarly to the reasoning from the previous group, among all such arrays it is beneficial to take the largest in terms of sum from both sides. This can be done using binary search or two pointers. The sum of the third segment is calculated as the remainder.

Similarly, we iterate over the split between two subarrays both of which have a sum greater than a third of $s u m$ , but now we minimize these two subarrays. The final complexity — $O (n \cdot lo g n)$ \mathcal{O}(n\cdot\log n) with binary search (group 7) and $O (n)$ with pointers (full solution).

In terms of implementation, it might help to double the array by inserting a copy of the initial one at the end. Then instead of transitioning from the last element to the initial one, you can just continue traversing the array, only needing to check whether the end of the third subarray doesn’t overlap with the first.