Problem Author: | Anton Trygub |
Prepared by: | Ihnat Zharikhin |
Analysis written by: | Ihnat Zharikhin |
10pt
Block 1 (n = 3)
It is obvious that there is a unique possible partition into three subarrays, each of size one element.
Block 2 (a_i \leq 1)
First, let's determine what the sums in the subarrays will be. Let the variable denote the number of ones in the array. Logically, each subsegment should be made as close to \left\lfloor \frac{cnt}{3} \right\rfloor as possible. If cnt \mid 3, then everything is fine and we have found the sums. Otherwise, we may have or leftover ones that we have not 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 simply traverse the array and add the next element to the current subarray. If we reach its sum (and we cannot skip it because a_i \leq 1), we close it and open the next one. Thus, we find the boundaries of the subarrays.
a+b=c
Block 3 (guaranteed, answer )
Let's calculate the total sum of the array, let this be . The additional constraints of this group mean that there is such a partition where all three subarrays have a sum of \frac{sum}{3}. Any subarrays with a different sum do not interest us at all.
For each index , we calculate the minimum index next_i \leq n (if it exists) such that the sum over the segment equals \frac{sum}{3}. If it does not exist, we remember this.
We traverse the array, iterating the start of the first subarray — . If there is no next_i, then this start definitely does not fit, we skip it. Then, let j = next_i. Similarly, it is necessary that next_j exists, otherwise such a partition does not fit. If it exists, we have found all three boundaries between the subsegments. The first two of them have a sum of \frac{sum}{3}, so the third also has the same, meaning we have found the answer. The complexity is — .
Block 4 (n \leq 100)
We will completely enumerate three starts of subarrays, as proposed in «output format». When we have the boundaries x, y, z, we calculate the sums simply by traversing the array or using prefix sums. The complexity is — \mathcal{O}(n^4) or \mathcal{O}(n^3), depending on which method to choose.
From now on, we will calculate all sums using prefix sums.
Block 5 (n \leq 2000) and 6 (n \leq 5000)
We will only enumerate the first two indices. For now, using them, we have divided the array into two subsegments. We keep one of them and calculate its sum, let this be . Now we need to divide the second subsegment into two more: a prefix and a suffix. Notice that many of these divisions are definitely not optimal. Intuitively, we are interested in dividing the array into two as equal as possible in sum. Theoretically, let's say we divided it such that the sums of the prefix and suffix are and , respectively. Without loss of generality, let pref \leq suff. Suppose that one element of the array (the one currently at the boundary) can be moved from the suffix to the prefix (which is the same as shifting the boundary by one), and the inequality remains true. Formally, pref+x\leq suff-x. It will always be beneficial for us to make this transition because \min(s,pref)\leq \min(s,pref+x) and \max(s,suff)\geq \max(s,suff-x), thus the answer will not be worse. The only moment when it may not be beneficial to make the transition is when the sign in the inequality changes. Therefore, we only need to check two cases: the largest prefix whose sum is less than the sum of the suffix and vice versa, the largest suffix whose sum is less than the sum of the prefix. From all others, we can transition to these without worsening the answer.
First implementation option: after enumerating the first two indices, we use binary search to find the turning point in the sums and check these two cases. The complexity is — \mathcal{O}(n^2 \cdot\log n), passing the fifth group.
Second implementation option: We find the turning point with a second pointer that always moves right through the cyclic array. The complexity is — \mathcal{O}(n^2), passing the sixth group.
Block 7 (n \leq 10^5) and 8 (without additional constraints)
Let the sum of all elements of the array be . Notice that in any partition, exactly one of the following two statements is true:
either exactly two arrays have a sum \leq \left\lfloor \frac{sum}{3} \right\rfloor and the third has a sum \geq \left\lfloor \frac{sum}{3} \right\rfloor,
or exactly two arrays have a sum \geq \left\lfloor \frac{sum}{3} \right\rfloor and the third has a sum \leq \left\lfloor \frac{sum}{3} \right\rfloor.
We will enumerate the cut of the array between two subarrays, both of which have a sum not greater than a third of . Similarly to the proof from the previous group, from all such arrays, it is beneficial to take the largest in 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 enumerate the cut between two subarrays, both of which have a sum greater than a third of , but now we minimize these two subarrays. The final complexity is — \mathcal{O}(n\cdot\log n) with binary search (group 7) and with pointers (full solution).
From the implementation perspective, it may help to double the array by appending a copy of the original at the end. Then, instead of transitioning from the last element to the first, we can simply continue traversing the array, the only thing we need to check is whether the end of the third subarray overlaps with the first.