1928.md (20496B)
1 Source: https://codeforces.com/blog/entry/125740 2 3 ## [1928A - Rectangle Cutting](/contest/1928/problem/A "Codeforces Round 924 (Div. 2)") 4 5 **Solution** 6 7 Let $a \le b$. Let's consider several cases: 8 9 * If $a$ is even, then we can cut the rectangle into two rectangles of size $\frac{a}{2} \times b$ and combine them into a rectangle of size $\frac{a}{2} \times 2b$, which is definitely different from $a \times b$. 10 * If $b$ is even and $b \ne 2a$, then we can cut the rectangle into two rectangles of size $a \times \frac{b}{2}$ and combine them into a rectangle of size $2a \times \frac{b}{2}$. Note that here we use the fact that $b \ne 2a$, because if $b = 2a$, then we will get the same rectangle of size $b \times a$. 11 * If $a$ and $b$ are both odd, or $b = 2a$ and $a$ is odd, then the rectangle is not interesting. It is easy to understand that if we cut the rectangle of size $a \times b$ into two rectangles of size $a \times c$ and $a \times d$, where $c \ne d$, then we can always only combine the original rectangle (similarly if we cut it into rectangles $c \times b$ and $d \times b$). And from here it follows that we must divide one of the sides of the rectangle in half, so at least one side must be even. 12 13 **Code** 14 15 ``` 16 #include <vector> 17 #include <iostream> 18 #include <numeric> 19 #include <algorithm> 20 #include <cassert> 21 #include <map> 22 23 using namespace std; 24 25 int main() { 26 ios_base::sync_with_stdio(false); 27 cin.tie(0); 28 cout.tie(0); 29 int t; 30 cin >> t; 31 while (t--) { 32 int a, b; 33 cin >> a >> b; 34 if (a > b) { 35 swap(a, b); 36 } 37 if (((a % 2 == 1) && (b % 2 == 1)) || ((a % 2 == 1) && (b == 2 * a))) { 38 cout << "No\n"; 39 } else { 40 cout << "Yes\n"; 41 } 42 } 43 44 return 0; 45 } 46 ``` 47 48 ## [1928B - Equalize](/contest/1928/problem/B "Codeforces Round 924 (Div. 2)") 49 50 **Solution** 51 52 Suppose we already know the permutation that needs to be added. Let's consider the elements that will become equal after the addition. Notice that among them there cannot be equal elements, because among the numbers we are adding, there are no duplicates. Thus, only a set of numbers among which there are no equal ones, and the difference between the maximum and minimum does not exceed $n - 1$, can become equal. It is easy to see that any set of numbers satisfying these conditions can be equalized, and any set of numbers that became equal after adding the permutation satisfies these constraints. 53 54 So let's sort the array, remove the equal elements from it. After that, we can use two pointers to find the maximum length subarray where the difference between the maximum and minimum does not exceed $n - 1$. The answer will be the length of such a subarray. The complexity of the solution is $O(n \log n)$. 55 56 **Code** 57 58 ``` 59 #include <bits/stdc++.h> 60 61 using namespace std; 62 63 void solve() { 64 int n; 65 cin >> n; 66 vector<int> a(n); 67 for (int i = 0; i < n; i++) { 68 cin >> a[i]; 69 } 70 sort(a.begin(), a.end()); 71 a.resize(unique(a.begin(), a.end()) - a.begin()); 72 int pnt = 0, ans = 0; 73 for (int i = 0; i < a.size(); i++) { 74 while(a[i] - a[pnt] >= n) { 75 pnt++; 76 } 77 ans = max(ans, i - pnt + 1); 78 } 79 cout << ans << endl; 80 } 81 82 signed main() { 83 int t = 1; 84 cin >> t; 85 for (int i = 0; i < t; ++i) { 86 solve(); 87 } 88 return 0; 89 } 90 ``` 91 92 ## [1928C - Physical Education Lesson](/contest/1928/problem/C "Codeforces Round 924 (Div. 2)") 93 94 **Solution** 95 96 All numbers repeat every $2k - 2$ positions. If the boy Vasya's number is calculated to be $x$, then it can be at positions of the form $(2k - 2) \cdot t + x$, or $(2k - 2) \cdot t + k + k - x$, for some non-negative $t$. This is true for all $x$, except for $x = 1$ and $x = k$ ~--- for these values, there is only one option left. 97 98 Let's fix one of the options, the second one will be analogous. We need to find how many different values of $k$ satisfy the equation $(2k - 2) \cdot t + x = n$, for some non-negative $t$. It is not difficult to see that this holds if and only if $n - x$ is divisible by $2k - 2$. Therefore, it is necessary to find the number of \textbf{even} divisors of the number $n - x$. To consider the second case, it is necessary to proceed similarly with the number $n + x - 2$. The solution's complexity: $O(\sqrt{n})$ 99 100 **Code** 101 102 ``` 103 #include <iostream> 104 #include <unordered_set> 105 106 using namespace std; 107 108 unordered_set<int> solve(int a) { 109 unordered_set<int> candidates; 110 for (int i = 1; i * i <= a; i++) { 111 if (a % i == 0) { 112 if (i % 2 == 0) // segment len should be even 113 candidates.insert(i); 114 if ((a / i) % 2 == 0) 115 candidates.insert(a / i); 116 } 117 } 118 unordered_set<int> answer; 119 for (int i : candidates) { 120 answer.insert(1 + i / 2); 121 } 122 return answer; 123 } 124 125 int main() { 126 int t; 127 cin >> t; 128 for (int _ = 1; _ <= t; _++) { 129 int n, pos; 130 cin >> n >> pos; 131 unordered_set<int> candidates = solve(n - pos); // bug2 132 for (int i : solve(n + pos - 2)) { // bug1 133 candidates.insert(i); 134 } 135 int answer = 0; 136 for (int i : candidates) { 137 if (i >= pos) { 138 answer++; 139 } 140 } 141 cout << answer << endl; 142 } 143 } 144 ``` 145 146 ## [1928D - Lonely Mountain Dungeons](/contest/1928/problem/D "Codeforces Round 924 (Div. 2)") 147 148 **Solution** 149 150 Let's learn how to solve the problem when $n = 1$. Suppose there is only one race and the number of its representatives is $c$. Notice that for a fixed $k$, it is advantageous for us to divide the representatives of the race almost evenly into squads. 151 152 If $c$ is divisible by $k$, then it is advantageous for us to take exactly $y = \frac{c}{k}$ beings in each squad. Then the total number of pairs of beings in different squads is equal to $\frac{k(k-1)}{2} \cdot y^2$ (there are a total of $\frac{k(k-1)}{2}$ pairs of squads, and for each pair of squads there are $y^2$ pairs of beings from different squads). 153 154 In the general case, when $c$ may not be divisible by $k$, let's denote $y = \left\lfloor \frac{c}{k} \right\rfloor$ and $y' = \left\lceil \frac{c}{k} \right\rceil$. Then it is advantageous for us to make squads of size $y$ and $y'$, where the number of squads of size $y'$ is equal to $c \bmod k$ (we essentially make all squads of size $y$, and then add 1 to some squads from the remaining part). In this case, the total number of pairs of beings in different squads is equal to $C_{k - c \bmod k}^2 \cdot y^2 + C_{c \bmod k}^2 \cdot y'^2 + (k - c \bmod k) \cdot (c \bmod k) \cdot y \cdot y'$. It remains to notice that it makes no sense to have $k \gt c$, so we can simply iterate through $k$ from $1$ to $c$ and choose the optimal one. 155 156 When $n \gt 1$, we can notice that for a fixed $k$, we can solve the problem independently for each race. Let the number of representatives of the $i$-th race be $c_i$. Then we will iterate through $k$ from $1$ to $c_i$ for it and add the maximum total strength to the value of $cnt_k$ (the array $cnt$ is common for all races). Also, notice that for $k \gt c_i$, we will get the same total strength as for $k = c_i$. Then in the additional array $add$ (again, common for all races), we will add the maximum total strength for $k = c_i$ to $add_{c_i}$. 157 158 We get the following solution: first, calculate the described arrays $cnt$ and $add$. After that, iterate through $k$ from $1$ to the maximum $c_i$. The maximum total strength of the squads for a fixed $k$ will be equal to $(cnt_k + (\text{sum of values } add_i \text{ for } i \lt k)) \cdot b - (k - 1) \cdot X$. From these values, we need to choose the maximum. 159 160 **Code** 161 162 ``` 163 #include <iostream> 164 #include <vector> 165 166 using namespace std; 167 using ll = long long; 168 169 ll pairs(ll n, ll k){ 170 if (n == 0 || k == 0){ 171 return 0; 172 } 173 ll x = n / k; 174 ll l = n % k; 175 ll r = k - l; 176 ll L = (x + 1) * l, R = x * r; 177 return R * L + (R - x) * R / 2 + L * (L - x - 1) / 2; 178 } 179 180 void solve(){ 181 int m; 182 long long c, b; 183 cin >> m >> b >> c; 184 185 int n = 0; 186 vector<int> cnt(m); 187 for (int i = 0; i < m; ++i) { 188 cin >> cnt[i]; 189 n = max(n, cnt[i]); 190 } 191 192 vector<long long> pair(n + 1); 193 vector<long long> add(n + 1); 194 for (int i = 0; i < m; ++i) { 195 for (int j = 1; j <= cnt[i]; ++j) { 196 pair[j] += pairs(cnt[i], j); 197 } 198 add[cnt[i]] += pairs(cnt[i], cnt[i]); 199 } 200 201 long long ans = 0; 202 long long other = 0; 203 for (int i = 1; i <= n; ++i) { 204 ans = max(ans, b * (pair[i] + other) - c * (i - 1)); 205 other += add[i]; 206 } 207 cout << ans << endl; 208 } 209 210 int main(){ 211 int t; 212 cin >> t; 213 while (t--){ 214 solve(); 215 } 216 } 217 ``` 218 219 ## [1928E - Modular Sequence](/contest/1928/problem/E "Codeforces Round 924 (Div. 2)") 220 221 **Solution** 222 223 Let's see what the answer will look like: first, there will be a prefix of the form $x, x + y, \ldots, x + k\cdot y$, and then there will be some number of blocks of the form $x \bmod y, x \bmod y + y, \ldots, x \bmod y + k \cdot y$. 224 225 We can subtract the number $x \bmod y$ from all the elements of the sequence, and then divide all the elements by $y$ (all the elements will be divisible by $y$, since they initially had a remainder of $x \bmod y$). Let $b_1 = \frac{x - x \bmod y}{y}$. Then our sequence will start with $b_1, b_1 + 1, \ldots, b_1 + k_1$, and then there will be blocks of the form $0, 1, \ldots, k_i$. 226 227 Let's calculate these values: $dp_i$~--- the minimum length of a sequence of blocks of the form $0, 1, \ldots, k_j$ with a sum of $i$. This value can be calculated for all numbers from $0$ to $s$ using dynamic programming. If we have processed all values from $0$ to $k-1$, then for $k$ we have calculated the minimum length, and we can update the value of $dp$ for $k + 1, k + 1 + 2, \ldots$~--- a total of $O(\sqrt{s})$ values not exceeding $s$. In this same $dp$, we can store through which values we were recalculated, for the restoration of the answer. 228 229 Now, we can iterate over the length of the first block of the form $b_1, b_1 + 1, \ldots, b_1 + k_1$. Then we know the sum of the remaining blocks, and using the precalculated $dp$, we can determine whether the desired sequence can be formed or not. 230 231 **Code** 232 233 ``` 234 #include <cassert> 235 #include <initializer_list> 236 #include <numeric> 237 #include <vector> 238 #include <iostream> 239 #include <utility> 240 #include <stack> 241 #include <queue> 242 #include <set> 243 #include <map> 244 #include <algorithm> 245 #include <math.h> 246 247 using namespace std; 248 249 #define pii pair<int, int> 250 #define mp make_pair 251 #define fi first 252 #define se second 253 #define all(x) (x).begin(), (x).end() 254 #define ll long long 255 #define pb emplace_back 256 257 const int INF = 1e9 + 10; 258 const ll INFLL = 1e18; 259 260 void solve() { 261 int n, x, y, S; 262 cin >> n >> x >> y >> S; 263 vector<int> dp(S + 1, INF); 264 dp[0] = 0; 265 for (int k = 1; k <= S; k++) { 266 for (int l = 2; (l * (l - 1)) / 2 <= k; l++) { // just 0 is never optimal 267 dp[k] = min(dp[k], dp[k - (l * (l - 1)) / 2] + l); 268 } 269 assert(dp[k] <= 2 * k); 270 } 271 for (ll k = 0; k < n; k++) { 272 ll prevSum = (k + 1) * x + (k * (k + 1)) / 2 * y; 273 if (prevSum > S) { 274 continue; 275 } 276 ll needSum = S - prevSum; 277 needSum -= (n - k - 1) * (x % y); 278 if (needSum < 0) { 279 continue; 280 } 281 if (needSum % y != 0) { 282 continue; 283 } 284 needSum /= y; 285 assert(needSum <= S); 286 if (dp[needSum] <= n - k - 1) { // we found the answer 287 vector<int> a(n); 288 a[0] = x; 289 for (int i = 1; i <= k; i++) { // construct prefix 290 a[i] = a[i - 1] + y; 291 } 292 for (int i = k + 1; i <= k + (n - k - 1) - dp[needSum]; 293 i++) { // fill the rest like 0 0 0 ... 294 a[i] = x % y; 295 } 296 int i = k + (n - k - 1) - dp[needSum] + 1; // first free index 297 vector<int> lens; // recover lengths of the segments 298 while (needSum != 0) { 299 for (int l = 2; (l * (l - 1)) / 2 <= needSum; l++) { 300 if (dp[needSum] == dp[needSum - (l * (l - 1)) / 2] + l) { 301 lens.pb(l); 302 needSum -= (l * (l - 1)) / 2; 303 break; 304 } 305 } 306 } 307 for (auto &len : lens) { 308 for (int j = 0; j < len; j++) { 309 a[i] = (x % y) + y * j; 310 i++; 311 } 312 } 313 cout << "YES\n"; 314 for (auto &c : a) { 315 cout << c << " "; 316 } 317 cout << "\n"; 318 return; 319 } 320 } 321 cout << "NO\n"; 322 } 323 324 int main() { 325 cin.tie(0); 326 cout.tie(0); 327 ios_base::sync_with_stdio(0); 328 int t = 1; 329 cin >> t; 330 while (t--) { 331 solve(); 332 } 333 return 0; 334 } 335 ``` 336 337 ## [1928F - Digital Patterns](/contest/1928/problem/F "Codeforces Round 924 (Div. 2)") 338 339 **Solution** 340 341 Let's assume that $a_i = a_{i+1}$ for some $1 \le i \lt n$, then for any $1 \le j \le m$, the cells $(i, j)$ and $(i+1, j)$ will have the same transparency. A similar statement can be made if there is an index $j$: $b_j = b_{j+1}$. 342 343 Then the positions $a_i = a_{i+1}$ divide the array $a$ into \textit{blocks}, in each of which all neighboring pairs are not equal to each other. It is clear that if there is a square $(x, y, d)$ consisting of cells $(i, j)$ such that $x \le i \lt x+d$ and $y \le j \lt y+d$, then the segment $[x, x+d-1]$ is entirely contained in one of these \textit{blocks} of the array $a$. Similarly, the array $b$ can also be divided into blocks, and then the segment $[y, y+d-1]$ will also be entirely contained in one of the blocks. 344 345 Let's try to solve the problem in $O(1)$ time, if there are no neighboring elements with the same values in the arrays $a$ and $b$ (also assuming that $n \le m$): 346 347 $ f(n, m) = \sum \limits_{k=1}^{n} (n-k+1)(m-k+1) = \sum_{k=1}^n \left( k^2 + (m-n)k \right) \\ f(n, m) = \frac{n(n + 1)(2n + 1)}6 + (m - n) \cdot \frac{n(n+1)}2 \\ $ 348 349 This formula can be further transformed by introducing a quadruple of numbers for each natural number $n$: $a_n = 1$, $b_n = n$, $c_n = \frac12 n(n+1)$, $d_n = \frac16 n(n+1)(2n+1) - \frac12n^2(n+1)$. Then $f(n, m) = d_n a_m + c_n b_m$, if $n \le m$ and $f(n, m) = a_n d_m + b_n c_m$, if $n \gt m$. 350 351 But if there are neighboring identical elements in the arrays $a$ and $b$, then this means that they are somehow divided into blocks. If these are blocks of lengths $n_1, \ldots, n_k$ in the array $a$ and blocks of lengths $m_1, \ldots, m_l$ in the array $b$, then the answer to the problem is 352 353 $ \textrm{ans} = \sum_{i=1}^k \sum_{j=1}^l f(n_i, m_j) $ 354 355 Let's learn how to quickly calculate sums of the form $f(x, m_1) + \ldots + f(x, m_l)$. To do this, we will create 4 segment trees to quickly calculate the sums $\sum a_y$, $\sum b_y$, $\sum c_y$, $\sum d_y$ over segments of $y$, taking into account the multiplicity of $y$ in the array $m_1, \ldots, m_l$. Now the calculation of $f(x, m_1) + \ldots + f(x, m_k)$ is reduced to $4$ segment tree queries: 356 357 $ f(x, m_1) + \ldots + f(x, m_l) = a_x \cdot \sum_{m_i \lt x} d_{m_i} + b_x \cdot \sum_{m_i \lt x} c_{m_i} + c_x \cdot \sum_{m_i \ge x} b_{m_i} + d_x \cdot \sum_{m_i \ge x} a_{m_i} $ 358 359 The sum $f(n_1, y) + \ldots + f(n_k, y)$ is calculated similarly. Now we just need to put our solution together. We will maintain the blocks of arrays $a$ and $b$ in an online mode. It is very convenient to do this by storing the positions $a_i = a_{i+1}$ in a data structure like std::set, and also by working with the differential array $a$ (i.e., maintaining not the array $a$ itself, but the array of differences between neighboring elements $c_i = a_{i+1} - a_i$). To recalculate the answer, we will count the number of squares that are involved in a specific block of the array $a$ or $b$, using the above result. As a result, we have a solution in $O((n+q) (\log n + \log m))$. 360 361 P.S. A solution in $O(q \sqrt n)$ will not work due to a large constant. I tried very hard to rule it out :D. 362 363 **Code** 364 365 ``` 366 #include <bits/stdc++.h> 367 368 using namespace std; 369 using ll = long long; 370 using pi = pair<int, int>; 371 372 struct SegmentTree { 373 int n; 374 vector<ll> t; 375 376 SegmentTree(int n) : n(n), t(2*n) { } 377 378 void Add(int i, ll x) { 379 for (i += n; i != 0; i >>= 1) t[i] += x; 380 } 381 382 ll Query(int l, int r) { 383 ll ans = 0; 384 385 for (l += n, r += n - 1; l <= r; l >>= 1, r >>= 1) { 386 if ((l&1) == 1) ans += t[l++]; 387 if ((r&1) == 0) ans += t[r--]; 388 } 389 return ans; 390 } 391 }; 392 393 struct SegmentContainer { 394 int side; 395 SegmentTree sgt_a, sgt_b, sgt_c, sgt_d; 396 int id; 397 // sgt_a: sum(1) 398 // sgt_b: sum(m) 399 // sgt_c: sum(m*(m+1)/2) 400 // sgt_d: sum(m*(m-1)*(2*m-1)/6 - m*(m-1)/2*m) 401 402 SegmentContainer(int side) : side(side), sgt_a(side), sgt_b(side), sgt_c(side), sgt_d(side) { 403 } 404 405 tuple<ll, ll, ll, ll> GetABCD(ll m) { 406 return make_tuple(1, m, m*(m+1)/2, m*(m-1)*(2*m-1)/6 - m*(m-1)/2*m); 407 } 408 409 void Insert(int m) { 410 auto [a, b, c, d] = GetABCD(m); 411 sgt_a.Add(m-1, +a); 412 sgt_b.Add(m-1, +b); 413 sgt_c.Add(m-1, +c); 414 sgt_d.Add(m-1, +d); 415 } 416 417 void Erase(int m) { 418 auto [a, b, c, d] = GetABCD(m); 419 sgt_a.Add(m-1, -a); 420 sgt_b.Add(m-1, -b); 421 sgt_c.Add(m-1, -c); 422 sgt_d.Add(m-1, -d); 423 } 424 425 ll SquaresCount(int n) { 426 const int mid = min(side, n); 427 auto sum_a = sgt_a.Query(mid, side); // m > n 428 auto sum_b = sgt_b.Query(mid, side); // m > n 429 auto sum_c = sgt_c.Query(0, mid); // m <= n 430 auto sum_d = sgt_d.Query(0, mid); // m <= n 431 auto [a, b, c, d] = GetABCD(n); 432 433 return d * sum_a + c * sum_b + b * sum_c + a * sum_d; 434 } 435 }; 436 437 struct SegmentMaintainer { 438 SegmentContainer& my; 439 SegmentContainer& other; 440 ll& ans; 441 442 set<int> pos_zero; 443 vector<ll> diff_array; 444 445 SegmentMaintainer(vector<int> a, 446 SegmentContainer& my, 447 SegmentContainer& other, 448 ll& ans) : 449 pos_zero(), diff_array(a.size()), my(my), other(other), ans(ans) { 450 pos_zero.insert(0); 451 for (int i = 1; i < a.size(); ++i) { 452 diff_array[i] = a[i] - a[i-1]; 453 if (diff_array[i] == 0) pos_zero.insert(i); 454 } 455 pos_zero.insert(a.size()); 456 457 for (auto it = pos_zero.begin(); *it != my.side; ++it) { 458 OnSegmentAppear(*next(it) - *it); 459 } 460 } 461 462 void OnSegmentAppear(int len) { 463 my.Insert(len); 464 ans += other.SquaresCount(len); 465 } 466 467 void OnSegmentDissapear(int len) { 468 my.Erase(len); 469 ans -= other.SquaresCount(len); 470 } 471 472 void ChangeBound(int pos, ll dx) { 473 if (pos == 0 || pos == my.side) return; 474 475 bool was_zero = diff_array[pos] == 0; 476 diff_array[pos] += dx; 477 bool now_zero = diff_array[pos] == 0; 478 479 if (was_zero && !now_zero) { 480 auto mid = pos_zero.find(pos); 481 auto prv = prev(mid), nxt = next(mid); 482 483 OnSegmentDissapear(*mid - *prv); 484 OnSegmentDissapear(*nxt - *mid); 485 OnSegmentAppear(*nxt - *prv); 486 487 pos_zero.erase(mid); 488 } 489 490 if (!was_zero && now_zero) { 491 auto mid = pos_zero.insert(pos).first; 492 auto prv = prev(mid), nxt = next(mid); 493 494 OnSegmentAppear(*mid - *prv); 495 OnSegmentAppear(*nxt - *mid); 496 OnSegmentDissapear(*nxt - *prv); 497 } 498 } 499 500 void RangeAdd(int l, int r, int x) { 501 ChangeBound(l, +x); 502 ChangeBound(r, -x); 503 } 504 }; 505 506 int main() { 507 ios::sync_with_stdio(0); cin.tie(0); 508 int n, m, q; cin >> n >> m >> q; 509 510 vector<int> a(n), b(m); 511 for (int& x : a) cin >> x; 512 for (int& x : b) cin >> x; 513 514 ll ans = 0; 515 SegmentContainer a_segments(n), b_segments(m); 516 517 a_segments.id = 1; 518 b_segments.id = 2; 519 520 SegmentMaintainer a_maintainer(a, a_segments, b_segments, ans); 521 SegmentMaintainer b_maintainer(b, b_segments, a_segments, ans); 522 523 cout << ans << '\n'; 524 while (q--) { 525 int t, l, r, x; cin >> t >> l >> r >> x; --l; 526 if (t == 1) a_maintainer.RangeAdd(l, r, x); 527 if (t == 2) b_maintainer.RangeAdd(l, r, x); 528 cout << ans << '\n'; 529 } 530 } 531 ```