1793.md (15087B)
1 Source: https://codeforces.com/blog/entry/112723 2 3 [1793A - Yet Another Promotion](/contest/1793/problem/A "Codeforces Round 852 (Div. 2)") was authored and prepared by [Ormlis](/profile/Ormlis "Legendary Grandmaster Ormlis") 4 5 [1793B - Fedya and Array](/contest/1793/problem/B "Codeforces Round 852 (Div. 2)") was authored and prepared by [TheEvilBird](/profile/TheEvilBird "Expert TheEvilBird") 6 7 [1793C - Dora and Search](/contest/1793/problem/C "Codeforces Round 852 (Div. 2)") was authored by [dyrbulshchyl](/profile/dyrbulshchyl "International Grandmaster dyrbulshchyl") and prepared by [vaaven](/profile/vaaven "Candidate Master vaaven") 8 9 [1793D - Moscow Gorillas](/contest/1793/problem/D "Codeforces Round 852 (Div. 2)") was authored and prepared by [Gornak40](/profile/Gornak40 "Expert Gornak40") 10 11 [1793E - Velepin and Marketing](/contest/1793/problem/E "Codeforces Round 852 (Div. 2)") was authored and prepared by [Tikhon228](/profile/Tikhon228 "Master Tikhon228") 12 13 [1793F - Rebrending](/contest/1793/problem/F "Codeforces Round 852 (Div. 2)") was authored by [Tikhon228](/profile/Tikhon228 "Master Tikhon228") and prepared by [vaaven](/profile/vaaven "Candidate Master vaaven") 14 15 ## [1793A - Yet Another Promotion](/contest/1793/problem/A "Codeforces Round 852 (Div. 2)") 16 17 Let $n = (m + 1) \cdot q + r$. 18 19 Note that you need to use a promotion if $a \cdot m \leq b \cdot (m + 1)$. In this case, we will buy potatoes $q$ times for the promotion. The remaining potatoes (or all if the promotion is unprofitable) can be bought at $\min(a, b)$ per kilogram. 20 21 Then the answer is: 22 23 $q \cdot \min(a \cdot m, b \cdot (m + 1)) + r \cdot \min(a, b)$ 24 25 Thus this solution works in $\mathcal{O}(1)$ 26 27 **Code** 28 29 ``` 30 t = int(input()) 31 32 for i in range(t): 33 a, b = map(int, input().split(" ")) 34 n, m = map(int, input().split(" ")) 35 36 q = n // (m + 1) 37 r = n - q * (m + 1) 38 print(q * min(a * m, b * (m + 1))+ r*min(a,b)) 39 ``` 40 41 ## [1793B - Fedya and Array](/contest/1793/problem/B "Codeforces Round 852 (Div. 2)") 42 43 Note that the local minimums and maximums will alternate, and there will be the same number of them $k$. Let's call the $i$-th local maximum by $a_i$, the $i$-th local minimum by $b_i$. Without loss of generality, consider that $a_i$ goes before $b_i$. To get $b_i$ from $a_i$ we need to write out $a_i - b_i$ numbers, to get $a_{(i + 1) \bmod k}$ from $b_i$ we need to write out $a_{(i + 1) \bmod k} - b_i$ numbers. 44 45 Thus, $(a_1 - b_1) + (a_2 - b_1) + (a_2 - b_2) + \ldots + (a_k - b_k) + (a_1 - b_k) =$ 46 47 $= 2 \cdot (a_1 + a_2 + \ldots + a_k) - 2 \cdot (b_1 + b_2 + \ldots + b_k) = 2 \cdot (A - B) = n$ 48 49 The array $[y, y + 1, y + 2, \ldots, x - 1, x, x - 1, x - 2, \ldots, y + 1]$ will satisfy the condition. 50 51 **Code** 52 53 ``` 54 #include <bits/stdc++.h> 55 56 using namespace std; 57 58 typedef long long ll; 59 60 void solve() { 61 ll a, b; 62 cin >> a >> b; 63 ll n = 2 * (a - b); 64 cout << n << '\n'; 65 vector<ll> arr(n); 66 int ptr = 0; 67 for (ll c = b; c <= a; ++c) { 68 arr[ptr++] = c; 69 } 70 for (ll c = a - 1; c > b; --c) { 71 arr[ptr++] = c; 72 } 73 for (int i = 0; i < n; ++i) { 74 cout << arr[i] << " \n"[i == n - 1]; 75 } 76 } 77 78 int main() { 79 int t; 80 cin >> t; 81 while (t--) { 82 solve(); 83 } 84 return 0; 85 } 86 ``` 87 88 ## [1793C - Dora and Search](/contest/1793/problem/C "Codeforces Round 852 (Div. 2)") 89 90 Suppose we want to check whether the entire array satisfies the claim. If this is the case, then we can output the entire array as an answer. Otherwise, one of the two extreme elements does not meet our requirements. From this we can conclude that all segments containing an element that does not meet our requirements will also be incorrect, because this extreme element will remain the minimum/maximum. 91 92 The algorithm follows from the fact above: let's look at the sub-section $[l; r]$, which is initially equal to $[1; n]$. If $a_l = \min(a_{l}, a_{l+1}, \ldots, a_{r})$ or $a_l = \max(a_l, a_{l +1}, \ldots, a_r)$, then we proceed to the segment $[l+1; r]$. A similar reasoning is also needed for $a_r$. Thus, either after some iterations we will get the required sub-section, or we will get $l == r$ and the answer will be $-1$. 93 94 Final asymptotics: $\mathcal{O}(n\log n)$ or $\mathcal{O}(n)$ depending on the implementation. 95 96 **Code** 97 98 ``` 99 #include <bits/stdc++.h> 100 101 using namespace std; 102 103 typedef vector<int> vi; 104 105 void solve() { 106 int n; 107 cin >> n; 108 vi a(n); 109 for (int &i: a) 110 cin >> i; 111 int l = 0, r = n - 1; 112 int mn = 1, mx = n; 113 while (l <= r) { 114 if (a[l] == mn) { 115 l++; 116 mn++; 117 } else if (a[l] == mx) { 118 l++; 119 mx--; 120 } else if (a[r] == mn) { 121 r--; 122 mn++; 123 } else if (a[r] == mx) { 124 r--; 125 mx--; 126 } else { 127 break; 128 } 129 } 130 if(l <= r){ 131 cout << l + 1 << " " << r + 1 << endl; 132 } else{ 133 cout << -1 << endl; 134 } 135 } 136 137 signed main() { 138 int q = 1; 139 cin >> q; 140 while (q--) 141 solve(); 142 return 0; 143 } 144 ``` 145 146 ## [1793D - Moscow Gorillas](/contest/1793/problem/D "Codeforces Round 852 (Div. 2)") 147 148 Denote by $pos_x$ the index of the number $x$ in the permutation. Subsegments with $\operatorname{MEX} \gt 1$ are as follows $1 \le l \le pos_1 \le r \le n$. 149 150 Denote by: $l_x = \min{[pos_1, pos_2, \ldots, pos_x]}$, $r_x=\max{[pos_1, pos_2, \ldots, os_x]}$. 151 152 Subsegments with $\operatorname{MEX} \gt x$ are as follows $1 \le l \le l_x \le r_x \le r \le n$. Let's find all subsegments with $\operatorname{MEX}=x$. 153 154 If $pos_{x + 1} \lt l_x$, then the subsegments with $\operatorname{MEX}=x+1$ are as follows $pos_{x+1} \lt l \le l_x \le r_x \le r \le n$ 155 156 If $l_x \le pos_{x + 1} \le r_x$, then there is no subsegment with $\operatorname{MEX}=x+1$ 157 158 If $r_x \lt pos_{x+1}$, then the subsegments with $\operatorname{MEX}=x+1$ are as follows $1 \le l \le l_x \le r_x \le r \lt pos_{x+1}$ 159 160 It remains only to intersect the sets of such subsegments for $p$ and $q$, which is done trivially. 161 162 **Code** 163 164 ``` 165 #include <bits/stdc++.h> 166 #define int long long 167 168 using namespace std; 169 170 void solve() { 171 int n; 172 cin >> n; 173 vector<int> pos_a(n + 1); 174 vector<int> pos_b(n + 1); 175 for (int i = 0; i < n; i++) { 176 int a; 177 cin >> a; 178 pos_a[a] = i + 1; 179 } 180 for (int i = 0; i < n; i++) { 181 int b; 182 cin >> b; 183 pos_b[b] = i + 1; 184 } 185 int la = n, ra = 1, lb = n, rb = 1, ans = 0; 186 for (int i = 1; i + 1 <= n; i++) { 187 la = min(la, pos_a[i]); 188 ra = max(ra, pos_a[i]); 189 lb = min(lb, pos_b[i]); 190 rb = max(rb, pos_b[i]); 191 int min_la, max_ra, min_lb, max_rb; 192 if (pos_a[i + 1] < la) { 193 min_la = pos_a[i + 1] + 1; 194 max_ra = n; 195 } else { 196 min_la = 1; 197 max_ra = pos_a[i + 1] - 1; 198 } 199 if (pos_b[i + 1] < lb) { 200 min_lb = pos_b[i + 1] + 1; 201 max_rb = n; 202 } else { 203 min_lb = 1; 204 max_rb = pos_b[i + 1] - 1; 205 } 206 ans += max(min(la, lb) - max(min_la, min_lb) + 1, 0ll) * max(min(max_ra, max_rb) - max(ra, rb) + 1, 0ll); 207 } 208 ans += min(pos_a[1], pos_b[1]) * (min(pos_a[1], pos_b[1]) - 1) / 2; 209 ans += (n - max(pos_a[1], pos_b[1])) * (n - max(pos_a[1], pos_b[1]) + 1) / 2; 210 ans += abs(pos_a[1] - pos_b[1]) * (abs(pos_a[1] - pos_b[1]) - 1) / 2; 211 ans++; 212 cout << ans << endl; 213 } 214 215 signed main() { 216 int q = 1; 217 while (q--) 218 solve(); 219 return 0; 220 } 221 ``` 222 223 ## [1793E - Velepin and Marketing](/contest/1793/problem/E "Codeforces Round 852 (Div. 2)") 224 225 Let's sort people by their group size requirement. Suppose we have such a person $i$ that he is not satisfied, and we have a person $j \gt i$ who is satisfied. Then we can replace person $j$ in his group with $i$ and the answer for us will not be worse. It follows that for a particular $k$ the answer is some prefix of the people we can make satisfied. 226 227 Let us also prove that there exists some arrangement of groups that covers the same prefix, and that each group is a continuous segment. Let's take some correct partitioning into groups. Then each group will be a set of unconnected segments. Let's take the leftmost such segment. Note that we can swap it to the nearest segment of the same group to the right without breaking anything. 228 229 Thus we obtained that we can look for a solution in the form of partitioning each prefix into valid groups, which are segments. We will solve this problem using dynamic programming. 230 231 Let $dp[i]$ -- the maximum number of groups into which $i$th prefix can be partitioned, so that everyone is satisfied (and no elements beyond the prefix can be used). Dynamics base: $dp[0] = 0$ (empty prefix maximum can be divided into 0 groups). Transition: for $i$th person his group must have size at least $a[i]$, so the transition looks like this $dp[i] = \underset{0 \leqslant j \leqslant i - a[i]}{\max} dp[j] + 1$. But what if $a[i] \gt i$? Then we can't dial the $i$th prefix. Then we put $dp[i] = -\infty$. This dynamics can be calculated using prefix maximums. This part of the solution works for $\mathcal{O}(n)$. 232 233 Earlier we said that the answer would be some prefix of people who would be satisfied. If we can partition the prefix into some number of groups, then that answer can be the prefix for all $k \leqslant dp[i] + n - i$. (we partition our prefix into $dp$, and the rest of the people one by one into the group) 234 235 If we can't make the whole prefix satisfied ($dp[i] = -\infty$), then we need to add people from outside. Thus, the maximum number of groups we can split into if $i$th prefix is completely satisfied is $n - a[i] + 1$. 236 237 Note that if by some prefix we can score $k$, then we can also score $k - 1$ (combining two groups into one). Then we need to find the largest prefix that fits the given $k$ in the query. This can be done by an array of suffix maximums over $\mathcal{O}(q)$ total. The final asymptotic of the solution is $\mathcal{O}(n \log n + q)$. 238 239 **Code** 240 241 ``` 242 #include<bits/stdc++.h> 243 244 using namespace std; 245 #define ll long long 246 #define pii pair<int, int> 247 #define ld long double 248 #define all(a) (a).begin(), (a).end() 249 250 const int inf = 1e9 + 7; 251 252 signed main() { 253 ios_base::sync_with_stdio(0); 254 cin.tie(0); 255 cout.tie(0); 256 257 int n; 258 cin >> n; 259 vector<int> c(n); 260 for (int i = 0; i < n; ++i) cin >> c[i]; 261 sort(all(c)); 262 vector<int> ans(n + 1); 263 vector<int> dp(n + 1, -inf); 264 dp[0] = 0; 265 266 for (int i = 1; i <= n; ++i) { 267 if (c[i-1] <= i) { 268 dp[i] = dp[i - c[i-1]] + 1; 269 ans[dp[i] + n - i] = max(ans[dp[i] + n - i], i); 270 } else { 271 if (c[i-1] <= n) { 272 ans[1 + n - c[i-1]] = max(ans[1 + n - c[i-1]], i); 273 } 274 } 275 dp[i] = max(dp[i], dp[i-1]); 276 } 277 278 for (int i = n - 1; i >= 0; i--) { 279 ans[i] = max(ans[i], ans[i + 1]); 280 } 281 282 int q; 283 cin >> q; 284 for (int i = 0; i < q; ++i) { 285 int x; 286 cin >> x; 287 cout << ans[x] << '\n'; 288 } 289 290 return 0; 291 } 292 ``` 293 294 ## [1793F - Rebrending](/contest/1793/problem/F "Codeforces Round 852 (Div. 2)") 295 296 Let's go through all the elements from left to right. The main task will be to support the current version of $dp[i]$ -- the minimum difference of $a_i$ with the elements to the right of it that we managed to consider. Let us correctly calculate $dp$ for the first $r$ elements. Let's move on to $r + 1$. Let's show how to update the answer for all $j \lt i$, such that $a[j] \gt a[i]$. For $j \lt i$, such that $a[j] \lt a[i]$ is solved similarly. 297 298 Let's take the first element $a[j]$ to the left of $i$, such that $a[j] \gt a[i]$. Note that if there is $l \lt j \lt i$ such that $a[l] \gt a[j] \gt a[i]$, then we will not update $dp[l]$ for it, because $|a[l] - a[j]| \lt |a[l] - a[i]|$. Also, we will not update the answer for $l$ such that $|a[l] - a[j]| \lt |a[l] - a[i]|$, that is, if $a[l] \gt a[i] + \frac{a[j] - a[i]}{2}$. Therefore, further we will be interested only in the numbers from the segment $\left[a[i], a[i] + \frac{a[j] - a[i]}{2}\right]$. 299 300 Let's note that we have reduced the length of the segment by $2$ times. That is, there will be no more such iterations than $\mathcal{O}(\log n)$. You can find the rightmost number belonging to a segment using the segment tree. The answer for the segment $l_i, r_i$ will be $\underset{l_i\leqslant j \lt r}{\min} dp[l]$ at the moment $r_i$. This can also be efficiently found using the segment tree. The final asymptotics of the solution is $\mathcal{O}(n\log^2 n + q\log n)$. 301 302 There is also a solution for $\mathcal{O}(n\sqrt{n} + q\log q)$ that passes all the tests. 303 304 **Code** 305 306 ``` 307 #include <bits/stdc++.h> 308 309 using namespace std; 310 311 const int inf = 1e9 + 228; 312 313 template<class T, class Fun = function<T(const T &, const T &)>> 314 struct SegTree { 315 Fun f; 316 vector<T> t; 317 int n; 318 319 SegTree(int sz, const Fun &g, T default_value = T()) : f(g) { 320 n = 1; 321 while (n < sz) n <<= 1; 322 t.resize(n * 2, default_value); 323 } 324 325 SegTree(vector<T> &a, const Fun &g, T default_value = T()) : SegTree(a.size(), g, default_value) { 326 for (int i = 0; i < n; ++i) t[i + n] = a[i]; 327 for (int i = n - 1; i >= 1; --i) t[i] = f(t[i << 1], t[i << 1 | 1]); 328 } 329 330 void upd(int i, T x) { 331 i += n; 332 t[i] = f(t[i], x); 333 for (i >>= 1; i > 1; i >>= 1) t[i] = f(t[i << 1], t[i << 1 | 1]); 334 } 335 336 T get(int l, int r) { 337 T resL = t[0], resR = t[0]; 338 for (l += n, r += n; l < r; l >>= 1, r >>= 1) { 339 if (l & 1) resL = f(resL, t[l++]); 340 if (r & 1) resR = f(t[--r], resR); 341 } 342 return f(resL, resR); 343 } 344 }; 345 346 signed main() { 347 ios_base::sync_with_stdio(0); 348 cin.tie(0); 349 350 int n, q; 351 cin >> n >> q; 352 vector<int> a(n); 353 for (int i = 0; i < n; i++) { 354 cin >> a[i]; 355 } 356 vector<vector<pair<int, int>>> posts(n); 357 for (int i = 0; i < q; i++) { 358 int l, r; 359 cin >> l >> r; 360 l--, r--; 361 posts[r].push_back({l, i}); 362 } 363 SegTree<int> ind(n + 1, [](int x, int y) { return max(x, y); }, -1); 364 SegTree<int> dp(n + 1, [](int x, int y) { return min(x, y); }, inf); 365 vector<int> answer(q); 366 for (int i = 0; i < n; i++) { 367 { 368 int limit = n + 1; 369 while (true) { 370 int j = ind.get(a[i], limit); 371 if (j == -1) 372 break; 373 dp.upd(j, abs(a[j] - a[i])); 374 limit = a[i] + (a[j] - a[i] + 1) / 2; 375 } 376 } 377 { 378 int limit = 0; 379 while (true) { 380 int j = ind.get(limit, a[i]); 381 if (j == -1) 382 break; 383 dp.upd(j, abs(a[j] - a[i])); 384 limit = a[i] - (a[i] - a[j] + 1) / 2 + 1; 385 } 386 } 387 ind.upd(a[i], i); 388 for (pair<int, int> j: posts[i]) { 389 answer[j.second] = dp.get(j.first, i); 390 } 391 } 392 for (int i: answer) { 393 cout << i << "\n"; 394 } 395 396 return 0; 397 } 398 ```