2107.md (28262B)
1 Source: https://codeforces.com/blog/entry/142642 2 3 Hope you enjoyed the round! 4 5 [2107A - LRC and VIP](/contest/2107/problem/A "Codeforces Round 1023 (Div. 2)") 6 7 **Solution** 8 9 When all the elements of the array are equal, the solution is trivially impossible since the $\gcd$ of any subset will always be equal to $a_1$. 10 11 That is infact the only $\texttt{No}$ case. We show a construction otherwise. 12 13 Let $\operatorname{mx} = \max(a)$. Put all the elements equal to $\operatorname{mx}$ in one set, and all the other elements in the other set. Then, the $\gcd$ of the first set is $\operatorname{mx}$ while the other set will have a strictly smaller $\gcd$ (because $\gcd(a, b) \le \min(a, b)$) 14 15 Time complexity is $O(n)$. 16 17 **Code** 18 19 ``` 20 #include <bits/stdc++.h> 21 using namespace std; 22 23 int main(){ 24 int t; cin >> t; 25 26 while (t--){ 27 int n; cin >> n; 28 vector <int> a(n); 29 for (int i = 0; i < n; i++){ 30 cin >> a[i]; 31 } 32 int mn = *min_element(a.begin(), a.end()); 33 int mx = *max_element(a.begin(), a.end()); 34 if (mn == mx){ 35 cout << "No\n"; 36 continue; 37 } 38 cout << "Yes\n"; 39 for (int i = 0; i < n; i++){ 40 cout << (1 + (a[i] == mx)) << " \n"[i + 1 == n]; 41 } 42 } 43 return 0; 44 } 45 ``` 46 47 [2107B - Apples in Boxes](/contest/2107/problem/B "Codeforces Round 1023 (Div. 2)") 48 49 **Solution** 50 51 Suppose $\max(a) - \min(a) \le k$ holds, and there is at least one $a_i \ge 1$. Then, infact it is possible to take one apple while still keeping the condition of $\max(a) - \min(a) \le k$. 52 53 **Proof** 54 55 We will subtract from the maximum element. Then $\min(a)$ does not change except when $a_1 = a_2 = \ldots = a_n$. In that special case, you can check that the move is valid as $\max(a) - \min(a)$ becomes $1$. 56 57 In any other case, $\max(a)$ reduces by $0$ or $1$, so $\max(a) - min(a)$ only decreases, and thus $\max(a) - \min(a) \le k$ clearly holds. 58 59 Thus, for an array with $\max(a) - \min(a) \le k$, the only way for a player to lose is when all $a_i = 0$. But this happens exactly after the $\sum(a_i)$-th turn because each turn reduces $\sum(a_i)$ by $1$. 60 61 --- 62 63 It may be possible that a first move itself is not possible. For example, in the case that $a = [4, 1], k = 1$. We should check that after subtracting the maximum element, the array has the property that $\max(a) - \min(a) \le k$ and immediately print $\texttt{Jerry}$ otherwise. 64 65 In the other case, we can simply print $\texttt{Tom}$ when $\sum(a_i)$ is odd, and $\texttt{Jerry}$ when $\sum(a_i)$ is even. This is because when $\sum (a_i)$ is odd, Tom will be the last person to make a move since he went first and the total number of turns is odd, and vice versa. 66 67 Time complexity is $O(n)$. 68 69 **Code** 70 71 ``` 72 #include <bits/stdc++.h> 73 using namespace std; 74 75 int main(){ 76 int t; cin >> t; 77 78 while (t--){ 79 int n, k; cin >> n >> k; 80 81 vector <int> a(n); 82 for (auto &x : a) cin >> x; 83 84 long long sum = accumulate(a.begin(), a.end(), 0LL); 85 86 sort(a.begin(), a.end()); 87 a[n - 1]--; 88 sort(a.begin(), a.end()); 89 90 if (a[n - 1] - a[0] > k || sum % 2 == 0){ 91 cout << "Jerry\n"; 92 continue; 93 } 94 cout << "Tom\n"; 95 } 96 return 0; 97 } 98 ``` 99 100 [2107C - Maximum Subarray Sum](/contest/2107/problem/C "Codeforces Round 1023 (Div. 2)") 101 102 **Solution** 103 104 We assume that there is at least one $s_i = 0$ (unfilled position). In the other case that all $s_i = 1$, we can easily check if the maximum subarray sum is $k$ or not. 105 106 Let us first figure out when the answer is impossible. Replace all $a_i = -\texttt{INF}$ such that $s_i = 0$. If the maximum subarray sum is still $ \gt k$, then the answer is clearly impossible. 107 108 In every other case, the answer is infact possible! All positions with $s_i = 0$ will be kept $-\texttt{INF}$ except for $1$. Choose that position arbitrarily, let's call it $pos$. 109 110 **Solution 1 (Linear)** 111 112 Let $b =$ max prefix sum in the subarray $[a_{pos + 1}, a_{pos + 2}, \ldots, a_n]$. Let $c =$ max suffix sum in the subarray $[a_1, a_2, \ldots, a_{pos - 1}]$. Here we will allow the empty prefix and suffix too. 113 114 Suppose the value of $a_{pos} = x$. Then, the maximum subarray sum including $pos$ will be $x + b + c$. 115 116 And the maximum subarray not including $pos$ will be $\le k$, because thats equivalent to replacing $a_{pos}$ with $-\texttt{INF}$. 117 118 Thus, we can simply replace $x$ with $k - b - c$ and it will satisfy the conditions. 119 120 **Solution 2 (Binary Search)** 121 122 Let $f(x)$ be defined as the maximum subarray sum when we replace $a_{pos}$ with $x$. 123 124 Note the following properties of $f(x)$: 125 126 * $f(-\texttt{INF}) \le k$: Because this is the assumption for the non-impossible case. 127 * $f(k) \ge k$: Because the subarray $[a_{pos}]$ itself has a sum of $k$, so the maximum subarray sum must be greater. 128 * $f(x + 1) \ge f(x)$ : Because increasing an element cannot reduce the maximum subarray sum. 129 * $f(x + 1) \le f(x) + 1$: Because by increasing $a_{pos}$, each subarray increases by $0$ or $1$ depending on whether it includes $pos$. Thus, there is no way for the function calculating maximum subarray sum to increase by more than $1$. 130 131 With these observations, we can infact binary search on the first $x$ such that $f(x) = k$. 132 133 This is because, $f$ becomes continuous on the set of integers by the third and fourth property, and hence it will take all values in the range $[f(a), f(b)]$ for $a \le b$, and we have shown that $k \in [f(-\texttt{INF}), f(k)]$ by the first and second property. 134 135 In both solutions, be careful to avoid overflow. One simple way is to have $\texttt{INF} = 10^{13}$, as that is sufficient for our purposes (prevents overflow, but still larger than $k + \sum{a_i}$). 136 137 Time complexity: $O(n)$ or $O(n \cdot \log(A))$. 138 139 **Code** 140 141 ``` 142 #include <bits/stdc++.h> 143 using namespace std; 144 145 int main(){ 146 int t; cin >> t; 147 while (t--){ 148 int n; 149 long long k; 150 cin >> n >> k; 151 string s; cin >> s; 152 vector <long long> a(n); 153 for (auto &x : a) cin >> x; 154 155 int pos = -1; 156 for (int i = 0; i < n; i++){ 157 if (s[i] == '0'){ 158 pos = i; 159 a[i] = -1e13; 160 } 161 } 162 163 long long mx = 0; 164 long long curr = 0; 165 for (int i = 0; i < n; i++){ 166 curr = max(curr + a[i], a[i]); 167 mx = max(mx, curr); 168 } 169 if (mx > k || (mx != k && pos == -1)){ 170 cout << "No\n"; 171 continue; 172 } 173 if (pos != -1){ 174 mx = 0, curr = 0; 175 long long L, R; 176 177 for (int i = pos + 1; i < n; i++){ 178 curr += a[i]; 179 mx = max(mx, curr); 180 } 181 L = mx; 182 mx = 0; 183 curr = 0; 184 for (int i = pos - 1; i >= 0; i--){ 185 curr += a[i]; 186 mx = max(mx, curr); 187 } 188 R = mx; 189 190 a[pos] = k - L - R; 191 } 192 193 cout << "Yes\n"; 194 for (int i = 0; i < n; i++){ 195 cout << a[i] << " \n"[i + 1 == n]; 196 } 197 } 198 return 0; 199 } 200 ``` 201 202 [2107D - Apple Tree Traversing](/contest/2107/problem/D "Codeforces Round 1023 (Div. 2)") 203 204 **Solution** 205 206 Note that the problem has a simple $O(n^2)$ solution by greedily finding the largest diameter in the current forest (set of disjoint trees) at every step, tiebreaking by the lexicographic order of the endpoints, then removing the diameter and continuing this process while at least $1$ node remains. 207 208 **Property $1$**: $2$ diameters always share at least one node. 209 210 **Proof** 211 212 With some background theory about diameters, this becomes trivial as when diameter length (in terms of nodes) is odd, they share a common central node; and when even, they share an edge (which shares $2$ nodes). Nevertheless, we provide an elementary proof. 213 214 Let $a_1, a_2, \ldots a_d$ and $b_1, b_2, \ldots b_d$ be $2$ distinct diameters that do not share any node. 215 216 Consider the closest pair of $2$ points in these $2$ paths, say $a_i$ and $b_j$ are closest. Then, the path $(a_i, b_j)$ cannot contain any other $a_k$ or any other $b_k$ because otherwise it would be a contradiction to the fact that they are closest. 217 218 Now, the length of the path $(a_1, b_1)$ is $(i - 1) + \operatorname{dist}(a_i, b_j) + (j - 1)$, where $\operatorname{dist}(x, y)$ denotes the number of nodes on the path $(x, y)$. 219 220 Assume that $i, j \ge \frac{d + 1}{2}$, then $\operatorname{dist}(a_1, b_1)$ is strictly larger than $d$ (using $\operatorname{dist}(a_i, b_j) \ge 2$), contradicting that $d$ is the diameter. In the other cases of $i, j$ being smaller than $\frac{d + 1}{2}$, we can check the pairs $(a_1, b_d), (a_d, b_1)$ and $(a_d, b_d)$. It is easy to see at least one of them will be larger than $d$. 221 222 **Property $2$** : Let $(u, v)$ denote a diameter path, and $T$ denote the tree. Then $\operatorname{diam}(T \setminus (u, v)) \lt \operatorname{diam}(T)$ (strictly smaller). 223 224 **Proof** 225 226 This comes directly from the previous property. Since all diameters share at least one node, the new forest generated after removing path $(u, v)$ will have a strictly smaller diameter. 227 228 **Property $3$** : In any sequence of positive numbers such that $a_1 + a_2 + \ldots + a_k \le n$ such that $a_i \lt a_j$ for all $1 \le i \lt j \le k$, $k$ is at most $O(\sqrt{n})$. 229 230 **Proof** 231 232 This is a classical property. 233 234 Note that $a_i \ge i$ for all $1 \le i \le k$ by induction. And thus, $a_1 + a_2 + \ldots + a_k \ge 1 + 2 + \ldots + k = \dfrac{k \cdot (k + 1)}{2}$. 235 236 But, $a_1 + a_2 + \ldots + a_k \le n$ implies $\dfrac{k \cdot (k + 1)}{2} \le n$, and so $k \le 2 \cdot \sqrt{n}$. 237 238 With these $3$ properties, we can now solve the problem. We describe the algorithm below: 239 240 * Maintain a collection of subtrees (of nodes which have apples). Initially, the whole tree is there as one component. 241 * For every subtree, find it's lexicographically largest triplet of $(d, u, v)$ using a BFS/DFS. 242 * Remove the nodes on the diameter path for each subtree. This divides the component into several smaller subtrees. Add them to our collection. 243 * Repeat steps $2$ and $3$ while our collection is non-empty. 244 * Finally, sort (in descending order) the list of $(d, u, v)$ collected throughout all the steps, and output. 245 246 It is not hard to see that the above approach produces the correct answer. And it runs in $O(n \cdot \sqrt{n})$ time because steps $2$ and $3$ are repeated only $O(\sqrt{n})$ times. 247 248 **Proof** 249 250 Every smaller tree is formed from a larger "parent" tree. The diameter of the smaller tree is smaller than the diameter of the larger tree using Property $2$. 251 252 Suppose that there is some tree that is formed at $k$-th step. Then, consider the sequence of parent trees of this tree, and their diameters. Their diameters form a strictly increasing sequence, but their sum must be bounded by $n$ since we remove that many nodes, and total removed nodes is $n$. Thus, using Property $3$, we get $k \le \sqrt{2 \cdot n}$. 253 254 There are several correct ways to implement Step $2$. One of the neatest way is as follows: Find the furthest node from $1$, tie breaking lexicographically, say we got $x$. Find the furthest node from $x$, again tie breaking lexicopgraphically, say we got $y$. Then $(\max(x, y), \min(x, y))$ is the required diameter. To prove that these $2$ traversals are enough, you can use the fact mentioned in proof of property $1$, i.e. diameters share a central node or an edge (depending on parity). To find the furthest node, we can use BFS or DFS both fairly easily. 255 256 For step $3$, we can keep recursing to the parent of $y$ till we reach $x$, assuming we have calculated the parents of all vertices with a dfs from $x$. You may refer to the code. 257 258 **Code** 259 260 ``` 261 #include <bits/stdc++.h> 262 using namespace std; 263 264 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 265 266 int main() 267 { 268 int t; cin >> t; 269 while (t--){ 270 int n; cin >> n; 271 272 vector<vector<int>> adj(n + 1); 273 for (int i = 1; i < n; i++){ 274 int u, v; cin >> u >> v; 275 276 adj[u].push_back(v); 277 adj[v].push_back(u); 278 } 279 280 vector <bool> used(n + 1, false), seen(n + 1, false); 281 vector <array<int, 3>> ans; 282 vector <int> p(n + 1, -1); 283 284 while (true){ 285 if (count(used.begin() + 1, used.end(), false) == 0){ 286 break; 287 } 288 seen.assign(n + 1, false); 289 290 auto dfs = [&](auto self, int u, int par) -> pair<int, int>{ 291 pair <int, int> ans = {1, u}; 292 p[u] = par; 293 seen[u] = true; 294 295 for (int v : adj[u]){ 296 if (v != par && !used[v]){ 297 auto pi = self(self, v, u); 298 pi.first += 1; 299 ans = max(ans, pi); 300 } 301 } 302 303 return ans; 304 }; 305 306 for (int i = 1; i <= n; i++) if (!used[i] && !seen[i]){ 307 auto [d1, j] = dfs(dfs, i, -1); 308 auto [d2, k] = dfs(dfs, j, -1); 309 ans.push_back({d2, max(j, k), min(j, k)}); 310 311 while (k != -1){ 312 used[k] = true; 313 k = p[k]; 314 } 315 } 316 } 317 318 sort(ans.begin(), ans.end(), greater<array<int, 3>>()); 319 for (auto [x, y, z] : ans){ 320 cout << x << " " << y << " " << z << " "; 321 } 322 cout << '\n'; 323 } 324 return 0; 325 } 326 ``` 327 328 **Bonus 1** 329 330 Solve the problem in $O(n \cdot \log(n))$. 331 332 **Solution** 333 334 Let $f_i,g_i$ be the longest and second longest path from $i$ in $i$'s subtree, the diameter will be $\max \limits_{i=1}^n {f_i+g_i}$. 335 336 When we find a diameter $(u,v)$, let update $f_u,g_u$ for all $u$ on the path $(\operatorname{lca}(u,v),\text{root})$. Note that the path $(\operatorname{lca}(u,v),\text{root})$ will be always shorter than the diameter, so the total update times will be $\mathcal O(n)$. 337 338 Use a `std::set` to find $f_u,g_u$ for every node $u$ and a `std::priority_queue` to maintain the maximum $f_i + g_i$, the total complexity is $\mathcal O(n \log n)$. 339 340 **Code** 341 342 ``` 343 #include<bits/stdc++.h> 344 #ifdef DEBUG_LOCAL 345 #include <mydebug/debug.h> 346 #endif 347 using ll = long long; 348 const int N = 5e5+5; 349 using namespace std; 350 using pi = pair<int,int>; 351 using ti = tuple<int,int,int,int>; 352 int T,n,u,v,del[N],fa[N],ct; vector<int> g[N]; set<pi> t[N]; 353 void dfs(int u,int f){ 354 t[u].emplace(0,u),fa[u] = f; 355 for(int v : g[u]) if(v != f){ 356 dfs(v,u); auto [x,y] = *--t[v].end(); 357 t[u].emplace(x+1,y); 358 } 359 }ti gt(int u){ 360 assert(t[u].size() >= 1); 361 if(t[u].size() == 1) return {0,u,u,u}; 362 auto [x,y] = *--t[u].end(); 363 auto [p,q] = *--(--t[u].end()); 364 return {x + p,max(y,q),min(y,q),u}; 365 }void los(){ 366 cin >> n; 367 for(int i = 1;i <= n;i ++) g[i].clear(),del[i] = 0,t[i].clear(); 368 for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u); 369 ct = 0,dfs(1,0); priority_queue<ti> q; 370 for(int i = 1;i <= n;i ++) q.emplace(gt(i)); 371 while(q.size()){ 372 auto [di,u,v,d] = q.top(); q.pop(); 373 if(del[d] || ti{di,u,v,d} != gt(d)) continue; 374 cout << di + 1 << " " << u << " " << v << " "; 375 while(u != d) del[u] = 1,u = fa[u]; 376 while(v != d) del[v] = 1,v = fa[v]; 377 del[d] = 1; 378 auto [x,y] = *--t[d].end(); 379 while(fa[d] && !del[fa[d]]){ 380 d = fa[d]; 381 if(t[d].count({++x,y})) t[d].erase({x,y}); 382 q.emplace(gt(d)); 383 if(fa[d]){ 384 auto [a,b] = *--t[d].end(); 385 t[fa[d]].emplace(a+1,b); 386 } 387 } 388 }cout << "\n"; 389 }int main(){ 390 ios::sync_with_stdio(0),cin.tie(0); 391 for(cin >> T;T --;) los(); 392 } 393 ``` 394 395 **Bonus 2** 396 397 Compute provably the exact worst case, and construct a tree that obtains it. 398 399 **Best Bound** 400 401 It can be proven that diameter decreases by $2$ each iteration and not just $1$, and it is possible to obtain this as we show later. So the best bound is $d$ where $1 + 3 + 5 + \ldots + (2 \cdot d - 1) \le n$, which comes out to be $\sqrt{n}$. 402 403 **Construction** 404 405 Let $L = \sqrt{n}$. Make $P_1, P_2, \ldots, P_L$ where $P_i$ is a line graph of size $2 \cdot i - 1$. Now, connect the central nodes of $P_i$ and $P_{i - 1}$ for all $i$. Refer to [Wuhudsm comment](https://codeforces.com/blog/entry/142642?#comment-1273076) for a picture. 406 407 [2107E - Ain and Apple Tree](/contest/2107/problem/E "Codeforces Round 1023 (Div. 2)") 408 409 **Solution** 410 411 Let $C(n, k)$ denote $\frac{n!}{k! \cdot (n - k)!}$. 412 413 We first start from the maximum possible value of $k$, and the tree that achieves it, i.e. a straight line path rooted at $1$. It is not too hard to see that this tree has the largest weight, and the weight of this tree is $C(n, 3)$. Thus, for $k \gt C(n, 3) + 1$, we answer $\texttt{No}$. We can prove the largest weight point by proving each node should have exactly $1$ child. Suppose instead some node $u$ has $\ge 2$ children, $c_1$ and $c_2$, but then if we attached $c_1$ to $c_2$ and broke the $c_1$ and $u$ edge, it increases the weight. 414 415 Now, infact the answer is possible for all $0 \le k \le C(n, 3) + 1$. We try to modify the line graph to give a valid construction. First of all, replace $k$ with $C(n, 3) - k$ and view the problem as reducing the weight of the line graph instead. 416 417 Suppose we broke the edge $(n - 1) - n$ and added the edge $x - n$, then the weight decreases by $C(n - x, 2)$. This is because the depth of LCA with nodes $n - 1$, $n - 2, \ldots, x$ change and they decrease by $n - x - 1, n - x - 2, \ldots 1$ respectively. Suppose, after this step, we further broke the edge $(n - 2) - (n - 1)$, and added the edge $y - (n - 1)$. It is tempting to say that the weight again decreases by $C(n - 1 - y, 2)$ but this is only true when $y \ge x$. 418 419 If we generalize the above, and break the edges $(i - 1) - i$ and add the edge $a_i - i$ ($a_i \lt i$), then the weight will decrease by $C(i - a_i, 2)$ as long as the sequence $a$ is decreasing (or $a_i = i - 1$, i.e. we do not change the parent). Because $a$ must be decreasing, that means that $i - a_i$ can only contain distinct elements (or $i - a_i = 1$). 420 421 This reduces the problem to **Find sum of distinct elements of $C(i, 2)$ ($0 \le i \le n - 1$)at most $1$ from k**. 422 423 Infact the greedy algorithm solves this problem, i.e. take the largest (untaken) value of $C(i, 2) \le k$ at each step. 424 425 **Proof** 426 427 We prove by induction. For $n \le 5$, it can be verified through bruteforce for all cases. 428 429 For $n \ge 6$, if $k$ is $\le C(n - 1, 3)$, just set $n = n - 1$ and by induction it is solvable. If $C(n - 1, 3) \lt k \le C(n, 3)$, then we set $k = k - C(n - 1, 2)$ and use induction. It can be verified that $0 \le k \le C(n - 1, 3)$ after this modification and so it is valid. 430 431 **Code** 432 433 ``` 434 #include <bits/stdc++.h> 435 using namespace std; 436 437 int main(){ 438 int t; cin >> t; 439 while (t--){ 440 int n; cin >> n; 441 long long k; cin >> k; 442 443 long long mx = 1LL * n * (n - 1) * (n - 2) / 6; 444 if (k > mx + 1){ 445 cout << "No\n"; 446 continue; 447 } 448 cout << "Yes\n"; 449 k = mx - min(k, mx); 450 451 int p = n - 1; 452 for (int i = n; i >= 2; i--){ 453 while (1LL * p * (p - 1) / 2 > k){ 454 p--; 455 } 456 k -= 1LL * p * (p - 1) / 2; 457 458 cout << (i - p) << " " << i << "\n"; 459 if (p != 1) p--; 460 } 461 } 462 return 0; 463 } 464 ``` 465 466 [2107F1 - Cycling (Easy Version)](/contest/2107/problem/F1 "Codeforces Round 1023 (Div. 2)") 467 468 **Solution** 469 470 Let us try to figure out the optimal strategy. We want to use small values for the "overtake" operation, and we will use "swap" operations to make the overtakes less costly. 471 472 Suppose $p = $ **first position of minima element**. We should over take cyclists $1, 2, \ldots, p$ for the cost of $a_p$, swapping $p$ till first. This is because all $a_i (1 \le i \lt p)$ is $\ge a_p + 1$, and so the swap + overtake can't be worse. And obviously, if we are using $a_q (q \gt p)$, it is less costly in terms of swaps to use $p$ since the overtake cost cannot be worse. 473 474 Now, we might use the value $a_p$ for overtakes in the suffix as well, i.e. there exists some $q \ge p$ such that we overtake cyclists $1, 2, \ldots, q$ using $a_p$. This reduces the problem to the subproblem $a[q + 1, n]$, and thus we can use Dynamic Programming! But why are the problems independent in $a[q + 1, n]$ and the rest of the array? Suppose that we took some $a_i (i \le q)$ to be used for swaps in the suffix $a[q + 1, n]$, but we could then instead set up the swaps such that first $p$ reaches $q$, and then $p$ is taken for these suffix swaps. This won't add any additional swaps, and may only reduce the cost. 475 476 Let $dp_i$ be the answer for the suffix $a[i, n]$. Then, we compute $p = $ position of minima in $a[i, n]$, iterate on partition index $j$ such that we will take $p$ to $j$ using it for swaps $1, 2 \ldots, j$, value computed as $dp_{j + 1} + a_p \cdot (j - i) + S$, where $S$ denotes the total swaps made ($S = 2 \cdot (j - p) + (p - i - 1)$). 477 478 This solves the problem in $O(n^2)$. 479 480 **Code** 481 482 ``` 483 #include <bits/stdc++.h> 484 using namespace std; 485 486 int main(){ 487 int t; cin >> t; 488 while (t--){ 489 int n; cin >> n; 490 491 vector <int> a(n + 1); 492 for (int i = 1; i <= n; i++){ 493 cin >> a[i]; 494 } 495 496 vector <long long> dp(n + 1, 1e18); 497 dp[n] = 0; 498 499 for (int i = n - 1; i >= 0; i--){ 500 int p = i + 1; 501 for (int j = i + 1; j <= n; j++) if (a[j] < a[p]){ 502 p = j; 503 } 504 505 for (int j = p; j <= n; j++){ 506 dp[i] = min(dp[i], dp[j] + 2 * (j - p) + 1LL * (j - i) * a[p] + (p - i - 1)); 507 } 508 } 509 510 cout << dp[0] << "\n"; 511 } 512 return 0; 513 } 514 ``` 515 516 [2107F2 - Cycling (Hard Version)](/contest/2107/problem/F2 "Codeforces Round 1023 (Div. 2)") 517 518 **Solution** 519 520 Read the editorial for F1 first. We considered the positions that we would take $p$ to, which we assumed was $q$ and iterated $q = p, p + 1, \ldots, n$, finding the cost for each. 521 522 **Property** : Optimal $q$ is only $q = p$ or $q = n$. 523 524 **Proof** 525 526 Suppose $q \ne p$, i.e. we use $a_p$ for overtaking $p + 1$, and we used $a_i$ for overtaking $q + 1$. Then, if $a_p + 2 \le a_i$, it is not less optimal to overtake $q + 1$ using $a_p$ as well, and if $a_i \le a_p + 1$, it is not less optimal to overtake $q$ using $a_i$. 527 528 Thus, $q$ is only ever the "edges" of the ranges , i.e. $p$ or $n$. 529 530 Now, let $p_1$ be the **first minima** in $a[1, n]$, then $p_2$ be the first minima in $a[p_1 + 1, n]$, $p_3$ be the first minima in $a[p_2 + 1, n]$, and so on. Let $q_i = $ where $p_i$ is taken to for each $i$. Due to the above property, we can see that the optimal strategy is : for some $x$, $q_x = n$ and $q_i = p_i$ for $i \lt x$, i.e. choose to take some index $p_x$ to $n$, and the previous indices do not move. 531 532 We get a $O(n)$ solution for a single array by trying all values of $x$. But, we need to answer prefix queries. 533 534 Note that each option of $x$ gives a linear equation in the length of the array. And appending an element to the end of the array adds at most $1$ extra option for $x$. We can maintain all the linear equations in a CHT/Lichao tree and find the minimum each time. 535 536 **Extra** 537 538 It can be proven that only $min(a) \le a_i \le min(a) + 20$ need to be considered, and we will never overtake using a larger value. This property gives us simpler solutions in $O(n \cdot 20)$ with $0$ data structures. 539 540 **Proof** 541 542 Assume $min(a) = 1$. Let $L_i$ denote the number of overtakes using the value $i$, and we use values $1, 2 \ldots, k$. Then, it is easy to see the indices $1, 2, \ldots, L_1$ will be overtaken with $1$, after that $L_1 + 1, L_1 + 2, \ldots, L_2$ will be overtaken with $2$ and so on. 543 544 It should not be more optimal to take the value $i$ to cover the entire suffix, and so this gives us additional constraints of the form (by calculating the difference of costs in the current way, and the modified way) $2 \cdot (L_{i + 1} + L_{i + 2} + \ldots + L_k) \gt L_{i + 1} \cdot 1 + L_{i + 2} \cdot 2 + L_{i + 3} \cdot 3 + \ldots$. This simplies to $L_{i + 1} \ge L_{i + 3} + 2 \cdot L_{i + 4} + \ldots$. 545 546 Because of $L_{i + 1} \ge 2 \cdot L_{i + 4}$, we get a bound of $3 \cdot log_2(n)$, but the exact bound can be computed by a greedy approach. 547 548 **Code** 549 550 ``` 551 #include <bits/stdc++.h> 552 using namespace std; 553 #define int long long 554 #define INF (int)1e18 555 556 #define inf 1e18 557 #define ld long double 558 559 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 560 561 562 struct chtDynamicMin { 563 struct line { 564 int m, b; ld x; 565 int om, ob; 566 int val; bool isQuery; 567 line(int _m = 0, int _b = 0, int _om = 0, int _ob = 0) { 568 m = _m; 569 b = _b; 570 om = _om; 571 ob = _ob; 572 val = 0; 573 x = -inf; 574 isQuery = false; 575 } 576 577 578 int eval(int x) const { return m * x + b; } 579 bool parallel(const line &l) const { return m == l.m; } 580 ld intersect(const line &l) const { 581 return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m); 582 } 583 bool operator < (const line &l) const { 584 if(l.isQuery) return x < l.val; 585 else return m < l.m; 586 } 587 }; 588 589 set<line> hull; 590 typedef set<line> :: iterator iter; 591 592 bool cPrev(iter it) { return it != hull.begin(); } 593 bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); } 594 595 bool bad(const line &l1, const line &l2, const line &l3) { 596 return l1.intersect(l3) <= l1.intersect(l2); 597 } 598 bool bad(iter it) { 599 return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it)); 600 } 601 602 iter update(iter it) { 603 if(!cPrev(it)) return it; 604 ld x = it -> intersect(*prev(it)); 605 line tmp(*it); tmp.x = x; 606 it = hull.erase(it); 607 return hull.insert(it, tmp); 608 } 609 610 void addLine(int m, int b) { 611 int om = m, ob = b; 612 m *= -1; 613 b *= -1; 614 line l(m, b, om, ob); 615 iter it = hull.lower_bound(l); 616 if(it != hull.end() && l.parallel(*it)) { 617 if(it -> b < b) it = hull.erase(it); 618 else return; 619 } 620 621 it = hull.insert(it, l); 622 if(bad(it)) return (void) hull.erase(it); 623 624 while(cPrev(it) && bad(prev(it))) hull.erase(prev(it)); 625 while(cNext(it) && bad(next(it))) hull.erase(next(it)); 626 627 it = update(it); 628 if(cPrev(it)) update(prev(it)); 629 if(cNext(it)) update(next(it)); 630 } 631 632 int query(int x) const { 633 if(hull.empty()) return inf; 634 line q; q.val = x, q.isQuery = 1; 635 iter it = --hull.lower_bound(q); 636 return - it -> eval(x); 637 } 638 }; 639 640 void Solve() 641 { 642 int n; cin >> n; 643 644 // insert lines and calculate CHT 645 chtDynamicMin cht; 646 647 vector <int> a(n + 1); 648 for (int i = 1; i <= n; i++){ 649 cin >> a[i]; 650 } 651 652 vector <int> pv(n + 1, 0); 653 // previous smaller 654 stack <pair<int, int>> st; 655 for (int i = n; i >= 1; i--){ 656 while (!st.empty() && st.top().first >= a[i]){ 657 pv[st.top().second] = i; 658 st.pop(); 659 } 660 661 st.push({a[i], i}); 662 } 663 664 vector <int> dp(n + 1, 0); 665 666 for (int i = 1; i <= n; i++){ 667 dp[i] = dp[pv[i]] + a[i] * (i - pv[i]) + (i - pv[i] - 1); 668 // slope is +2 + a[i] 669 // constant - slope * i 670 int m = 2 + a[i]; 671 int c = dp[i] - m * i; 672 cht.addLine(m, c); 673 674 int ans = cht.query(i); 675 cout << ans << " \n"[i == n]; 676 } 677 } 678 679 int32_t main() 680 { 681 auto begin = std::chrono::high_resolution_clock::now(); 682 ios_base::sync_with_stdio(0); 683 cin.tie(0); 684 int t = 1; 685 // freopen("in", "r", stdin); 686 // freopen("out", "w", stdout); 687 688 cin >> t; 689 for(int i = 1; i <= t; i++) 690 { 691 //cout << "Case #" << i << ": "; 692 Solve(); 693 } 694 auto end = std::chrono::high_resolution_clock::now(); 695 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); 696 cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 697 return 0; 698 } 699 ```