codeforces-scrape

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

1575.md (21084B)


      1 Source: https://codeforces.com/blog/entry/95561
      2 
      3 ## [1575A. Another Sorting Problem](https://codeforces.com/contest/1575/problem/A)
      4 
      5 Author: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
      6 Developer: [richiesenlia](/profile/richiesenlia "Специалист richiesenlia")  
      7 Editorialist: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")
      8 
      9 **Idea**
     10 
     11 Observe that the even-indexed character of the string can be transformed from `A`-`Z` to `Z`-`A`. E.g. for the first example:
     12 
     13 * AA → AZ
     14 * AB → AY
     15 * BB → BY
     16 * BA → BZ
     17 * AZ → AA
     18 
     19 Now, you can use any known algorithms to sort the string as usual. You can sort it in linear time with trie, or `std::sort` in $O(nm \log n)$ time.
     20 
     21 Time Complexity : $O(nm)$ or $O(nm \log n)$
     22 
     23 ## [1575B. Building an Amusement Park](https://codeforces.com/contest/1575/problem/B)
     24 
     25 Author: [Panji](/profile/Panji "Специалист Panji")  
     26 Developer: [kiwii](/profile/kiwii "Кандидат в мастера kiwii"), [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang")  
     27 Editorialist: [kiwii](/profile/kiwii "Кандидат в мастера kiwii"), [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang")
     28 
     29 **Idea**
     30 
     31 We can binary search the answer $r$ in this case. Here, bird's habitats are referred as points. First of all, define a function $c(x)$ as the maximum number of points that can be covered with a circle of radius $x$ through the origin.
     32 
     33 Define the park as a circle with radius $x$ and $\theta$, in a polar coordinate representation. Observe that each points have a **radial/angle segment** of which the point $p_i$ will be inside the circle if and only if $\theta$ belongs to the radial segment of $[L_{p_{i}}, R_{p_{i}}]$, where $-\pi \lt L_{p_{i}}, R_{p_{i}} \leq \pi$.
     34 
     35 E.g for $x = 4$, Observe the $L_{p_{3}}$ for the $p_3 = (1, 5)$.
     36 
     37 ![](/predownloaded/98/68/986872d3fec2d3e4e63430b985d4bbef26b65692.png)
     38 
     39 The green radial segment $e$ represents the $[L_{p_{3}}, R_{p_{3}}]$. Now, to find the two end points $B_i$ and $C_i$ of the arc for each point $p_i$. Because the triangle that is made by those 3 points are an isosceles triangle, simply find the angle where the distance of $p_i$ and $B_i$ equals to $x$, that is $\Delta = \cos^{-1}\dfrac{||p_i||}{2r}$. Now the segment can be found by calculating the angle of $\tan^{-1}p_i \pm \Delta$. Do a radial sweep to find the maximum number of points.
     40 
     41 Time complexity is $O(n \log n \cdot \log(\text{MAX_R} \cdot \epsilon^{-1}))$.
     42 
     43 We can optimize the binary search part further, since we only need $\log(\epsilon^{-1})$ most significant digits. We can binary search the position of the first non-zero digit in $O(\log\log(\text{MAX_R}))$, then use a normal binary search with $O(\log(\epsilon^{-1}))$ steps. In practice, this improves the time by around a factor of 2.
     44 
     45 Time complexity: $O(n \log n \cdot \log(\text{MAX_R} \cdot \epsilon^{-1}))$ or $O(n \log n \cdot \log(\log(\text{MAX_R}) \cdot \epsilon^{-1}))$.
     46 
     47 ## [1575C. Cyclic Sum](https://codeforces.com/contest/1575/problem/C)
     48 
     49 Author: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")  
     50 Developer: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")  
     51 Editorialist: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")
     52 
     53 **Idea**
     54 
     55 Let a valid segment $[l, r]$ be a segment in $b$ where the sum of elements in the segment is divisible by $k$.
     56 
     57 We can try to solve a simpler problem: find the number of valid segments such that the right endpoint ends at $1$. That is, the valid segments $[l, 1]$ ($1 \leq l \leq n \cdot m$).
     58 
     59 Let $prefix(p) = \sum_{i=1}^{p} {b[i]}$ and $cnt$ be an array where the $cnt[i]$ denote the number of $p$ ($1 \leq p \leq n \cdot m$) such that $i \equiv prefix(p) \mod k$.
     60 
     61 Notice that the number of valid segment $[l, 1]$ is $cnt[prefix(n \cdot m) + b[1]]$. Furthermore, the number of valid segments $[l, 1 + x \cdot n]$ ($0 \leq x \leq m-1$) is the same as the number of valid segment $[l, 1]$.
     62 
     63 Thus, we only need to calculate the number of valid segments for $[l, r]$ with $1 \leq l \leq n \cdot m$ and $1 \leq r \leq n$, then multiply the final result by $m$.
     64 
     65 First we need to find the array $cnt$. Let $sum = prefix(n)$.
     66 
     67 When $sum \equiv 0 \mod k$, we can find $cnt$ in a straightforward manner.
     68 
     69 Now assume $sum \not\equiv 0 \mod k$. For a fixed $i$, let's try to find the contribution of $prefix(i + x \cdot n)$ for all $0 \leq x \leq m-1$ to $cnt$ at once. Observe that if one make a directed graph with $(i, \ (i + sum) \bmod k)$ for $0 \leq i \lt k$ as the edges, one will get a cycle of length $k$ (since $k$ is prime) as the result. To find the contribution of $prefix(i + x \cdot n)$, we can do a range add operation on this cycle. This can be done with offline prefix sums (prefix difference) in $O(k)$ total.
     70 
     71 Now that we have the array $cnt$, we can find the number of valid segments that ends at $1$ easily. To find valid segment that ends at index $2$, we can modify $cnt$ by adding $prefix(n \cdot m) + b[1]$ to the counter and removing $b[1]$. We do this for all $1 \leq r \leq n$.
     72 
     73 This solution is also applicable for arbitary $k$, albeit multiple cycles will be generated and must be handled separatedly.
     74 
     75 Time complexity: $O(n + k)$
     76 
     77 ## [1575D. Divisible by Twenty-Five](https://codeforces.com/contest/1575/problem/D)
     78 
     79 Author: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
     80 Developer: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
     81 Editorialist: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")
     82 
     83 **Idea**
     84 
     85 There are no dirty tricks to solve this problem. Brute force all possible number between $i \in [10^{|s| - 1}, 10^{|s|} - 1]$, with step $i := i + 25$. You might want to handle when $|s| = 1$, because $0$ is a valid $s$, if possible. For easier implementation, you can use the `std::to_string(s)` in C++.
     86 
     87 It is also possible to solve it in $O(|s|)$ by case analysis.
     88 
     89 Time complexity: $O(\frac{1}{25} \cdot |s| \cdot 10^{|s|})$ or $O(|s|)$.
     90 
     91 **Short Solution**
     92 
     93 ```
     94 #include <bits/stdc++.h>
     95 using namespace std;
     96 
     97 #define sz(x) (int)(x).size()
     98 typedef long long LL;
     99 LL expo(LL a, LL b){
    100   // a %= MOD; // USE THIS WHEN N IS REALLY BIG!
    101   LL ret = 1;
    102   while(b > 0){
    103     if(b&1) ret = (ret*a);
    104     a = (a*a); b >>= 1;
    105   }
    106   return ret;
    107 }
    108 
    109 int main(){
    110   ios_base::sync_with_stdio(0);
    111   cin.tie(0);
    112   string s; cin >> s;
    113   int low = expo(10, sz(s) - 1);
    114   int high = expo(10, sz(s)) - 1;
    115   if(low == 1) low--;
    116   while(low%25) low++;
    117   int ans = 0;
    118   for(;low <= high;low += 25){
    119     string current = to_string(low);
    120     char xval = '-';
    121     bool can = 1;
    122     for(int i = 0;i < sz(s);i++){
    123       if(s[i] == '_') continue;
    124       if(s[i] == 'X'){
    125         if(xval != '-' && xval != current[i]){
    126           can = 0;
    127           break;
    128         }
    129         xval = current[i];
    130       }else if(s[i] != current[i]){
    131         can = 0;
    132         break;
    133       }
    134     }
    135     ans += can;
    136   }
    137   cout << ans << endl;
    138 }
    139 ```
    140 
    141 ## [1575E. Eye-Pleasing City Park Tour](https://codeforces.com/contest/1575/problem/E)
    142 
    143 Author: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")  
    144 Developer: [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang"), [kiwii](/profile/kiwii "Кандидат в мастера kiwii"), [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")  
    145 Editorialist: [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang"), [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")
    146 
    147 **Idea**
    148 
    149 We can use centroid decomposition to solve this problem.
    150 
    151 Suppose we find the centroid $cen$ of the tree, and root the tree at $cen$. We consider each subtree of the children of $cen$ as different groups of vertices. We want to find the sum of $f(u,v)$ for all valid tours, such that $u$ and $v$ are from different groups.
    152 
    153 We can solve this with basic inclusion-exclusion. We count the sum of $f(u,v)$ where the path $u \to cen \to v$ uses less than $k$ tickets, without caring which group $u,v$ belongs to. Then, we can subtract it by only considering $u \to cen \to v$ where $u,v$ belongs from the same group.
    154 
    155 Define $cost(u)$ as the number of tickets you need to go from $u$ to $cen$. For a fixed set of vertices $S$, you can count $f(u,v)$ where $cost(u) + cost(v) + z \leq k$ with prefix sums. Note that $z$ depends on whether the last edge of the path from $u \to cen$ and $v \to cen$ has different colors. We can do all of these in $O(|S|)$.
    156 
    157 We use the solution above while setting $S$ as the set of all vertices in $cen$'s subtree, or the set of vertices with the same group.
    158 
    159 Because the depth of a centroid tree is $O(\log n)$, the overall complexity of the solution is $O(n \log n)$.
    160 
    161 ## [1575F. Finding Expected Value](https://codeforces.com/contest/1575/problem/F)
    162 
    163 Author: [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang")  
    164 Developer: [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang")  
    165 Editorialist: [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang")
    166 
    167 **Idea**
    168 
    169 We can use this [trick](https://codeforces.com/blog/entry/77284#comment-620956), which is also explained below.
    170 
    171 Suppose $a_i \neq -1$ for now. We want to find a function $F(a)$ such that $\mathbb{E}(F_{t + 1} - F_t | F_t) = -1$, where $F_t$ is the value of $F(a)$ at time $t$. If we can find such a function, then the expected stopping time is equal to $F(a_0) - F(a_T)$, where $a_0$ is the initial array before doing any operation, and $a_T$ is the final array where we don't do any more operation (that is, all elements of $a_T$ are equal).
    172 
    173 Suppose $occ(x)$ is the number of occurrences of $x$ in the current array, for some $0 \leq x \lt k$. It turns out we can find such $F$ satisfying $F = \sum_{x = 0}^{k - 1} f(occ(x))$ for some function $f$. We now try to find $f$.
    174 
    175 Suppose we currently have $a_t$, and we want to find the expected value of $F(a_{t + 1})$. There are two cases to consider:
    176 
    177 * $\forall x, occ_{t + 1}(x) = occ_t(x)$ if $a_i$ doesn't change when doing the operation. This happens with probability $\frac{1}{k} \cdot \frac{occ_t(x)}{n}$ for each $x$.
    178 * Otherwise, there exist some $x, y$ ($x \neq y$) such that $occ_{t + 1}(x) = occ_t(x) - 1$ and $occ_{t + 1}(y) = occ_t(y) + 1$. This happens if initially $a_i = x$, then by doing the operation we change it to $y$. This happens with probability $\frac{1}{k} \cdot \frac{occ_t(x)}{n}$ for each $x,y$.
    179 
    180 Thus,
    181 
    182 $ \begin{split} & \mathbb{E}(F_{t + 1} - F_t | F_t) = -1\\ \implies & \sum_{i = 0}^{k - 1} f(occ_{t + 1}(i)) - \sum_{i = 0}^{k - 1}f(occ_t(x)) = -1\\ \implies & \sum_{i = 0}^{k - 1} f(occ_{t + 1}(i)) = \sum_{i = 0}^{k - 1}f(occ_t(i)) - 1\\ \implies & \frac{1}{k}\sum_{i = 0}^{k - 1}f(occ_t(i)) + \sum_{x = 0}^{k - 1}\sum_{y = 0}^{k - 1}[x \neq y]\frac{occ_t(x)}{nk}\Big( \sum_{i = 0}^{k - 1}f(occ_t(i)) - f(occ_t(x)) - \\ & f(occ_t(y)) + f(occ_t(x) - 1) + f(occ_t(y) + 1)\Big) = \sum_{i = 0}^{k - 1}f(occ_t(i)) - 1\\ \implies & \sum_{x = 0}^{k - 1}\sum_{y = 0}^{k - 1}[x \neq y]\frac{occ_t(x)}{nk}\Big( - f(occ_t(x)) - f(occ_t(y)) + f(occ_t(x) - 1) + f(occ_t(y) + 1)\Big) = - 1\\ \implies & \sum_{x = 0}^{k - 1}\frac{(k - 1)occ_t(x)}{nk} \Big(f(occ_t(x) - 1) - f(occ_t(x))\Big) + \frac{n - occ_t(x)}{nk}\Big( f(occ_t(x) + 1) - f(occ_t(x)) \Big) = - 1\\ \implies & \sum_{x = 0}^{k - 1}\frac{(k - 1)occ_t(x)}{nk} \Big(f(occ_t(x) - 1) - f(occ_t(x))\Big) + \frac{n - occ_t(x)}{nk}\Big( f(occ_t(x) + 1) - f(occ_t(x)) \Big) + \frac{occ_t(x)}{n} = 0\\ \end{split} $
    183 
    184 Suppose $a = occ_t(x)$. If we can find $f$ such that
    185 
    186 $ \frac{(k - 1)a}{nk} \Big(f(a - 1) - f(a)\Big) + \frac{n - a}{nk}\Big( f(a + 1) - f(a) \Big) + \frac{a}{n} = 0 $
    187 
    188 then $f$ satisfies $F$.
    189 
    190 $ \frac{(k - 1)a}{nk} \Big(f(a - 1) - f(a)\Big) + \frac{n - a}{nk}\Big( f(a + 1) - f(a) \Big) + \frac{a}{n} = 0\\ (k - 1)a \Big(f(a - 1) - f(a)\Big) + (n - a)\Big( f(a + 1) - f(a) \Big) + ak = 0\\ (k - 1)af(a - 1) - (k - 1)af(a) + (n - a)f(a + 1) - (n - a)f(a) + ak = 0\\ f(a + 1) = \frac{1}{a - n}\Big( (k - 1)af(a - 1) + (2a - ak - n)f(a) + ak \Big) $
    191 
    192 So we can set $f$ to any function that satisfies the recursive formula above, and then derive $F$.
    193 
    194 To handle $a_i = -1$, note that $F$ depends only on the occurrence of each value $x$ ($0 \leq x \lt k$), and each of them is independent. Therefore, we can count the contribution for each $x$ towards all possible final arrays separately. This is easy to do in $O(n)$.
    195 
    196 Moreoever, there is only $O(\sqrt{n})$ values of $occ(x)$ in the initial array (before changing $a_i = -1$), and each $x$ with the same occurrences contribute the same amount. Therefore, we can solve the problem in $O(n \sqrt{n})$.
    197 
    198 ## [1575G. GCD Festival](https://codeforces.com/contest/1575/problem/G)
    199 
    200 Author: [tzaph_](/profile/tzaph_ "Мастер tzaph_")  
    201 Developer: [kiwii](/profile/kiwii "Кандидат в мастера kiwii"), [tzaph_](/profile/tzaph_ "Мастер tzaph_")  
    202 Editorialist: [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang")
    203 
    204 **Idea**
    205 
    206 Define:
    207 
    208 * $d(n)$ as the set of all divisors of $n$;
    209 * $\phi(x)$ as the [euler totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function) of $x$; and
    210 * $d(a, b)$ as the set of all divisors of both $a$ and $b$; or equivalently, $d(\gcd(a, b))$.
    211 
    212 Observe that $\sum_{x \in d(n)}\phi(x) = n$. This implies $\sum_{x \in d(a, b)}\phi(x) = \gcd(a,b)$
    213 
    214 $ \sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j) \cdot \gcd(a_i, a_j)\\ \sum_{i = 1}^n \sum_{j = 1}^n \left(\left(\sum_{x \in d(i,j)} \phi(x)\right) \cdot \gcd(a_i, a_j))\right)\\ \sum_{x=1}^n \phi(x) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} \gcd(a_{ix}, a_{jx})\\ \sum_{x=1}^n \phi(x) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{y \in d(a_{ix}, a_{jx})} \phi(y)\\ \sum_{x=1}^n \phi(x) \sum_{y} \phi(y) \left(\sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{ix} \bmod y = 0] \right)^2 $
    215 
    216 If we only iterate $y$ where $y$ is a divisor of one of $a_{ix}$, we can compute the above summation in $O(n \log n \max_{i=1}^n(|d(a_i)|))$.
    217 
    218 ## [1575H. Holiday Wall Ornaments](https://codeforces.com/contest/1575/problem/H)
    219 
    220 Author: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
    221 Developer: [Sakamoto](/profile/Sakamoto "Эксперт Sakamoto"), [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
    222 Editorialist: [kiwii](/profile/kiwii "Кандидат в мастера kiwii"), [rama_pang](/profile/rama_pang "Международный гроссмейстер rama_pang")
    223 
    224 **Idea**
    225 
    226 Do a dynamic programming with three states:
    227 
    228 * Position in $s$
    229 * Position in $t$
    230 * How many matches left.
    231 
    232 define the dynamic programming of $dp[a][b][rem]$ as the minimum cost of having the string $p = s[1..a]$, $rem$ matches left, and the longest prefix match between $s$ and $t$ is at $b$. The answer will be at $dp[n][c][0]$ for any arbitrary $c$.
    233 
    234 The transition can first be precomputed with brute force in $O(n^3)$ or with Aho-Corasick.
    235 
    236 Time complexity: $O(n^3)$  
    237 Space complexity: $O(n^2)$
    238 
    239 ## [1575I. Illusions of the Desert](https://codeforces.com/contest/1575/problem/I)
    240 
    241 Author: [JulianFernando](/profile/JulianFernando "Кандидат в мастера JulianFernando")  
    242 Developer: [JulianFernando](/profile/JulianFernando "Кандидат в мастера JulianFernando"), [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
    243 Editorialist: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")
    244 
    245 **Idea**
    246 
    247 Note that $\max(|a_x + a_y|, |a_x - a_y|) = |a_x| + |a_y|$.
    248 
    249 Now the problem can be reduced to updating a vertex's value and querying the sum of values of vertices in a path.
    250 
    251 This can be done in several ways. One can use euler tour tree flattening method, as described in [Euler Tour Magic by brdy blog](https://codeforces.com/blog/entry/63020), or use heavy-light decomposition.
    252 
    253 Time complexity : $O((q + n) \log^2 n)$ or $O((q + n) \log n)$
    254 
    255 ## [1575J. Jeopardy of Dropped Balls](https://codeforces.com/contest/1575/problem/J)
    256 
    257 Author: [richiesenlia](/profile/richiesenlia "Специалист richiesenlia")  
    258 Developer: [richiesenlia](/profile/richiesenlia "Специалист richiesenlia")  
    259 Editorialist: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")
    260 
    261 **Idea**
    262 
    263 Naively simulating the ball's path is enough, and runs in $O(nm + nk)$. Note that if we visit a non-$2$ cell, then the path length of the current ball is increased by $1$, and then the cell turns into $2$. So the total length of all paths can be increased by at most $O(nm)$ times. In addition, each ball needs at least $O(n)$ moves to travel, so we get $O(nm + nk)$.
    264 
    265 We can improve this further. You can speed up each drops by storing consecutive $2$-cell segments in the downwards direction for each column. Using a Disjoint-Set Union data structure, for each cell $a_{x,y} = 2$, join it with its bottom cell if $a_{x + 1, y} = 2$.
    266 
    267 Time complexity: $O(k + rc\cdot\alpha(rc))$
    268 
    269 ## [1575K. Knitting Batik](https://codeforces.com/contest/1575/problem/K)
    270 
    271 Author: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
    272 Developer: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")  
    273 Editorialist: [kiwii](/profile/kiwii "Кандидат в мастера kiwii")
    274 
    275 **Fun fact**
    276 
    277 October the 2nd is the National Batik Day of Indonesia
    278 
    279 **Idea**
    280 
    281 Observe that only some several non-intersecting part of $nm - rc$ that is independent in the grid. Simple casework shows that the answer is $k^{nm}$ if $a = b$, and $k^{nm - rc}$ otherwise.
    282 
    283 Time complexity: $O(\log nm)$
    284 
    285 ## [1575L. Longest Array Deconstruction](https://codeforces.com/contest/1575/problem/L)
    286 
    287 Author: [tzaph_](/profile/tzaph_ "Мастер tzaph_")  
    288 Developer: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")  
    289 Editorialist: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")
    290 
    291 **Idea**
    292 
    293 Define $a'$ as the array we get after removing some elements in $a$ and valid element as $a'_i$ that satisfy $a'_i = i$.
    294 
    295 We can try to find combination of indices ${c_1, c_2, \dots c_m}$ such that $a_{c_i} = a'_{p_i} = p_i$ for a certain set ${p_1, p_2, \dots p_m}$. In other words, we want to find all indices ${c_1, c_2, \dots c_m}$ such that $a_{c_i}$ will be a valid element in the $a'$.
    296 
    297 Observe that each element in $c$ and every pair $i$ and $j$ ($i \lt j$) must satisfy:  
    298 1. $c_i \lt c_j$  
    299 2. $a_{c_i} \lt a_{c_j}$  
    300 3. $c_i - a_{c_i} \leq c_j - a_{c_j}$, the element you need to remove to adjust $a_{c_i}$ to it's location is smaller than $a_{c_j}$.
    301 
    302 Therefore, we can convert each index into $(c_i, a_{c_i}, c_i - a_{c_i})$ and find the longest sequence of those tuples that satisfy the conditions. This is sufficient with divide and conquer in $O(n\log n\log n)$.
    303 
    304 But the solution can be improved further. Notice that if $(2) \land (3) \implies (1)$. Hence we can solve problem by finding the longest sequence of pairs ($a_{c_i}, c_i - a_{c_i}$) with any standard LIS algorithm.
    305 
    306 Time complexity: $O(n\log n)$
    307 
    308 ## [1575M. Managing Telephone Poles](https://codeforces.com/contest/1575/problem/M)
    309 
    310 Author: [tzaph_](/profile/tzaph_ "Мастер tzaph_")  
    311 Developer: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")  
    312 Editorialist: [steven.novaryo](/profile/steven.novaryo "Кандидат в мастера steven.novaryo")
    313 
    314 **Fun fact**
    315 
    316 Interestingly, if you generate the Voronoi Diagram and transcribe it to a grid, then the same connected area in the Voronoi Diagram is not necessarily in the same 8-connected component in the grid. This is why most Dijkstra solutions will get WA.
    317 
    318 **Idea**
    319 
    320 We can use convex hull trick to solve this problem.
    321 
    322 Suppose that we only need to calculate $\sum_{x = 0}^{m} {S(x, y)}$ for a certain $y$. For a fixed $y$ axis and a pole located in point $(x_i, y_i)$, define $f(x) = (x - x_i)^2 + (y - y_i)^2 = - 2xx_i + x^2 - x_i^2 + (y - y_i)^2$, which is the euclidean distance of point $(x, y)$ and pole $(x_i, y_i)$.
    323 
    324 Notice that, for a fixed pole $i$ and axis $y$, $f(x)$ is a line equation, thus we can maintain it with convex hull trick.
    325 
    326 Additionally, for a certain $y$, there are only $m$ poles that we need to consider. More specifically, pole $(x_i, y_i)$ is called considerable if there is no other pole $(x_j, y_j)$ such that $x_i = x_j$ and $|y_i - y| \lt |y_j - y|$.
    327 
    328 Hence we can find the $\sum_{x = 0}^{m} {S(x, y)}$ for a certain $y$ in $O(m)$ or $O(m \log m)$. Calculating $\sum_{x = 0}^{m} {S(x, y)}$ for all $y$ will result in $O(nm)$ or $O(nm \log m)$ time complexity.