2013.md (12304B)
1 Source: https://codeforces.com/blog/entry/134298 2 3 This is my version of the editorial for problem D of [Codeforces Round 973 (Div. 2)](/contest/2013 "Codeforces Round 973 (Div. 2)"). It was motivated by [GrishinD](/profile/GrishinD "Specialist GrishinD")'s great blog about his solution and presents a slower yet interesting alternative. I wanted to try this exercise to improve my thinking process and maybe become a div1 codeforcer along with [GrishinD](/profile/GrishinD "Specialist GrishinD") ! 4 5 I first had a dynamic programming approach and got TL. Then I tried to work with binary search. I used a constructive algorithm inside the search to check for the validity of the current value. My solution got AC but I wasn't convinced by the correction and I wanted to understand in depth. 6 This blog explains my solution and brings a comprehensive proof. I'll first describe my algorithm and intuition, and then go through the proof. 7 8 # Statement 9 10 Your are given an array $a_1,a_2,…,a_n$ of the length n 11 12 You can perform any number (possibly, zero) of operations on the array. 13 14 In one operation, we choose a position $i (1 \leq i \leq n-1)$ and perform the following actions: 15 - $a_i:=a_i-1$, 16 - $a_{i+1}:=a_{i+1}+1$ 17 18 Find the minimum possible value of $max(a_1,a_2,…,a_n)-min(a_1,a_2,…,a_n)$ 19 20 # I — Notation and vocabulary 21 22 I will use some notations I found useful. 23 - $\forall i, 1 \leq i \leq n$ I will denote $a_i$ as $a[i]$. 24 - $max(a) $ and $min(a)$ will denote respectively $max_{i \in [1, n]}{a[i]}$ and $min_{i \in [1, n]}{a[i]}$ 25 26 I had a pretty mathematical approach, but I will describe the problem as a line of columns of blocks of size $a[i]$. 27 28 # II — Constructive algorithm and intuition 29 30 The solution first shows that the smallest maximum (denoted $alpha$) and the largest minimum obtainable (denoted $beta$) can be found with binary search in $\mathcal{O}(n*log(n))$. Then I bring the proof that these two values can be obtained simultaneously using the operation. 31 32 I'll describe here my first algorithm used in the binary search to check whether $alpha$ can be larger than all values of a rearranged $a$ array. 33 34 For $i=1$ to $i=n-1$, if $a[i] \gt alpha$: 35 - $a[i] := alpha$ 36 - $a[i+1] := a[i+1] + alpha - a[i]$ 37 38 **Note that it is alway a valid algorithm**, since it can be decomposed in separation application of the operation. 39 Visually, the algorithm go through columns from left to right. If a column exceeds $alpha$, the excedent is reported to the next column. 40 Let's start with an input array $a$. The first column excedent is reported to the next, and so on. 41 42  43 44 Eventually we reach the end of the array 45 46  47 48 At the end of the loop, $alpha$ is an admissible majorant iff the last column doesn't exceed $alpha$. In this case, $alpha$ is too low, it can't be the smallest minimum. 49 50 **Quick proof** 51 52 I draw here a quick yet valid proof : 53 $[A \Rightarrow B]$ If the construction algorithm yields a valid array, then $alpha$ has to be a valid majorant. 54 $[\bar{A} \Rightarrow \bar{B}]$ If the construction algorithm yields an invalid array, i.e. $a'[n] \gt alpha$ after the algorithm: - either initially $a[n] \gt alpha$, then it can't be affected by the operation for $alpha$ to be a valid majorant. 55 - or initially $a[n] \lt = alpha$, and the excedent came from previous columns. This means that the excedent blocks were necessarely propagated from a previous starting position, and couldn't find enough place until they reached the last position. More formally, we can verify that after the algorithm there is necessary an interval $[n-k, n-1]$ such that $a'[i]=alpha$ and $a'[n-k-1] \lt alpha$ (or $k=n-1$). 56 In other words, $\sum_{i=n-k}^{i=n}a[i] \gt (k+1)*alpha$, and there is just too many blocks in the $k+1$ last rows for the operation to allow $alpha$ to be a valid majorant. 57 58 The same logic can be applied to show that $beta$ can be the smaller than all values of a rearranged array with the following algorithm 59 60 For $i=n$ to $i=2$, if $a[i] \lt beta$: 61 - $a[i] := beta$ 62 - $a[i-1] := a[i-1] - (beta - a[i])$ 63 64 Starting from another input array $a$, the propagation goes backwards : 65 66  67 68 Values in $a$ can be temporarly negative as shawn in orange, only the value of $a[0]$ needs to be tested. 69 70  71 72 At the end of the loop, $beta$ is an admissible minorant iff the first column is greater or equal than $beta$. In this case, $beta$ is can be an admissible minorant. 73 The proof is similar. 74 75 The intuition is then that we can apply the $alpha$-algorithm and then the $beta$-algorithm to get a rearranged array with the smallest maximum $alpha$ and the largest minimum $beta$. Then the solution of the problem is $alpha - beta$. 76 77 **Code** 78 79 ``` 80 #include <bits/stdc++.h> 81 82 using namespace std; 83 typedef long long ll; 84 typedef unsigned long long ull; 85 86 #define forn(i,j,k) for(ll i=(j); i<=(k); i++) 87 #define rofn(i,j,k) for(ll i=(j); i>=(k); i--) 88 89 int main() { 90 ll t; 91 cin >> t; 92 93 ll n; 94 while(t--) { 95 cin >> n; 96 vector<ll> a(n+1); 97 ll mn = 1e15, mx=-1; 98 forn(i, 1, n) { 99 cin >> a[i]; 100 mn = min(mn, a[i]); 101 mx = max(mx, a[i]); 102 } 103 104 ll low = mn, high = mx; 105 ll alpha, beta; 106 while(low+1 < high) { 107 alpha = (low + high) / 2; 108 ll tmp = 0; 109 bool valid = true; 110 rofn(i, n, 1) { 111 tmp += a[i]; 112 if(tmp > (n-i+1)*alpha) { 113 valid = false; 114 break; 115 } 116 } 117 if(valid) high = alpha; 118 else low = alpha; 119 } 120 alpha = high; 121 122 low = mn; high = mx; 123 while(low+1 < high) { 124 beta = (low + high) / 2; 125 ll tmp = 0; 126 bool valid = true; 127 forn(i, 1, n) { 128 tmp += a[i]; 129 if(tmp < i*beta) { 130 valid = false; 131 break; 132 } 133 } 134 135 if(valid) low = beta; 136 else high = beta; 137 } 138 beta = low; 139 140 cout << alpha - beta << endl; 141 } 142 } 143 ``` 144 145 It seemed logical at first, but I couldn't be sure of its validity. I took some time to think, and the rest of the blog is a formal proof of this result. **Time for the heavy guns.** 146 147 # III — Formal proof of $alpha$-$beta$ 148 149 Previous parts showed that we can find $alpha$ and $beta$ with a constructive algorithm starting from the initial array $a$. The idea of the proof is to show that applying $alpha$-algorithm yields an array for which it is alway possible to apply $beta$-algorithm as well. 150 151 ## A — Characterization of admissible maximum and minimum 152 153 The first step is to find $beta= max(min(\tilde{a}))$, where $\tilde{a}$ is the input array after performing an arbitrary number of operations. This is the largest value that can be obtained for the minimum value in the array $a$. 154 155 For a value $beta$ to be an admissible minimum of $\tilde{a}$ is equivalent to this statement : $\forall i, 1 \leq i \leq n, \sum_{j=1}^{j=i}{a[j]} \geq i * beta$ 156 157 In other words, the following statements are equivalent 158 159 * For any position $i$, the total amount of blocks left to this position must possible to be less or equal to $i$ columns of size $beta$. 160 * The columns $1$ to $i$ can be rearranged using the operation to be all greater than $beta$. 161 162 ### Proof 163 164 $(H_k) : (\forall i, 1 \leq i \leq k, \sum_{j=1}^{j=i}{a[j]} \geq i * beta) \iff (beta=min_{i \in [1, k]}[\tilde{a}[i]])$ 165 166 (Note that this applies to the prefix of size $k$ of $\tilde{a}$.) 167 168 #### Initialisation 169 170 * For $k=1$, the statement is obvious. 171 * For $k=2$, the first column alone has to be larger than i, because it can't ever grow. The second can be smaller, as long as there is enough in a[1]. This writes as : $a[1] \geq beta$ and $a[2] + (a[1] - beta) \geq beta$, which is equivalent to $(H_2)$. 172 173 #### Induction 174 175 Suppose $(H_k)$ is true for an arbitrary value of $k$. Let's show that $(H_{k+1})$ is true. 176 177 $[A \Leftarrow B]$ Suppose the right part of $(H_{k+1})$. If $\sum_{j=1}^{j=k+1}a[j] \lt (k+1)*beta$, there is simply not enough blocks left from $k+1$ for $beta$ to be an admissible minimum. Therefore, reductio ad absurdum, $\sum_{j=1}^{j=k+1}a[j] \geq (k+1)*beta$ has to be true. 178 179 $[A \Rightarrow B]$ Suppose the left part of $(H_{k+1})$. By supposition, we can rearrange $a[1], ..., a[k]$ to be larger than $beta$. If $a[k+1] \geq beta$, the right part of $(H_{k+1})$ is true. Else, 180 181 $\sum_{j=1}^{j=k+1}{a[j]} \geq (k+1)*beta \iff \sum_{j=1}^{j=k+1}{a[j]} - k*beta \geq beta \iff \sum_{j=1}^{j=k}{a[j]} - k*beta \geq beta - a[k+1] \geq 0$ 182 183 The sum $\sum_{j=1}^{j=k}{a[j]}$ represents the excedent left to $a[k+1]$ after rearranging $a[1], ... a[k]$ that can be used to get $\tilde{a}[k+1] \geq beta$ 184 185 #### Conclusion 186 187 The two statements are equivalent. **Moreover**, there are also both equivalent to the statement "apply the $alpha$-algorithm yields a feasible solution". I won't write it again, but a symmetrical proof can be written to prove that the three following statements are equivalent : 188 189 * $\forall i, 1 \leq i \leq n, \sum_{j=i}^{j=n}a[j] \leq (n-i+1)*alpha$ 190 For any position $i$, the total amount of blocks right to this position must less or equal to $i$ columns of size $alpha$ 191 * $alpha = max(\tilde{a})$ 192 The columns $i$ to $n$ can be rearranged using the operation to be all lower than $alpha$ 193 * The $alpha$-algorithm yields a valid array for which $alpha$ is a majorant. 194 195 The **first interesting result** is that this prefix (resp. suffix) sum can be used in the binary search for $beta$ (resp. $alpha$) instead of building a modified array. **But the best is yet to come !** 196 197 ## B — Use of smallest maximum and largest minimum in the solution 198 199 Finally, this last part shows that we can always rearrange initial $a$ into an array solution that has both $alpha$ as maximum and $beta$ as minimum. 200 201 With the optimal $alpha$ found with binary search and the suffix sum criterion, suppose that we apply $alpha$-algorithm to the input array $a$. We will show that it implies that the prefix sum criterion is still respected, and the $beta$-algorithm can always be applied as well. 202 203 $beta$ being the largest admissible minimum for a rearranged $a$, the prefix sum criterion is respected before applying $alpha$-algorithm. 204 We denote $a^{(k)}$ the state of the rearranged $a$ after applying the k-th step of the $alpha$-algorithm, i.e right after possibly modifying $a[k]$ and $a[k+1]$. 205 206 $(H_k) : (\forall 1 \leq i \leq k, a^{(k)}[i] \leq alpha) \wedge (\sum_{j=1}^{j=i}a^{(k)}[j] \geq i*beta)$ 207 208 #### Initialisation 209 210 $(H_1)$ : after one step, $a^{(k)}[1]$ was either set to $alpha \geq beta$ or kept as $a[1] \geq beta$. 211 212 #### Induction 213 214 Suppose $(H_k)$ true for a fixed $k$. Consider $(H_{k+1})$ : 215 216 * either $a^{(k)}[k+1] \leq alpha$ then $a^{(k+1)}[k+1] = a^{(k)}[k+1]$, and no blocks were moved after the column $k$. The prefix sum at index $k+1$ hasn't changed and the second part of $(H_{k+1})$ it true as well. 217 * or $a^{(k)}[k+1] \gt alpha$, then $a^{(k+1)}[k+1] := alpha$ and $a^{(k+1)}[k+2] := a^{(k)}[k+2] + a^{(k)}[k+1] - alpha$. 218 219 By induction, $\sum_{j=1}^{j=k}a^{(k)}[j] \geq k*beta$ and $a^{(k+1)}[k+1] = alpha \geq beta$, 220 $\Rightarrow \sum_{j=1}^{j=k+1}a^{(k+1)}[j] \geq (k+1)*beta$. 221 222 #### Conclusion 223 224 $(H_n)$ is true, and the complete application of $alpha$-algorithm maintains the prefix-sum criterion, so $beta$ is still the largest minimum possible. 225 It is possible to search for $alpha$ and $beta$ separately, and combine them to build the final answer, $alpha-beta$. 226 227 Thank you for reading it so far, it took me much to much time, but I loved trying to formalize the proof. Let me know if you find mistakes, or simpler way of proving the result. 228 Thank you [soullless](/profile/soullless "Master soullless") for organizing this contest, and [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") for this great plateform. See ya !