codeforces-scrape

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

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 ```