codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![ ](/predownloaded/6a/a2/6aa29fab054d6e266f152f167ca5b1367e77c49c.png)
     43 
     44 Eventually we reach the end of the array
     45 
     46 ![ ](/predownloaded/f7/51/f751cbe613f80e3b38eb33b00d8da842378d94a8.png)
     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 ![ ](/predownloaded/4d/d2/4dd2b5b6f33954755bfb9bf9b5274dd76aca2302.png)
     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 ![ ](/predownloaded/ee/ec/eeecfc416aa77af2097f6078a319a228a0907853.png)
     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 !