1985.md (20005B)
1 Source: https://codeforces.com/blog/entry/129620 2 3 This was our first time setting a Div.4 contest. We sincerely hope you enjoyed the problems! 4 5 ##### [1985A - Creating Words](/contest/1985/problem/A "Codeforces Round 952 (Div. 4)") 6 7 Problem Credits: [cry](/profile/cry "Master cry") 8 Analysis: [cry](/profile/cry "Master cry") 9 10 **Solution** 11 12 To swap the first character of the strings, you can use the built-in method std::swap in C++, or for each string, separate the first character from the rest of the string and concatenate it with the other string. 13 14 **Code (C++)** 15 16 ``` 17 #include <bits/stdc++.h> 18 using namespace std; 19 20 int main(){ 21 int t; cin >> t; 22 while(t--){ 23 string a, b; cin >> a >> b; 24 swap(a[0], b[0]); 25 cout << a << " " << b << endl; 26 } 27 } 28 ``` 29 30 ##### [1985B - Maximum Multiple Sum](/contest/1985/problem/B "Codeforces Round 952 (Div. 4)") 31 32 Problem Credits: [cry](/profile/cry "Master cry") 33 Analysis: [cry](/profile/cry "Master cry") 34 35 **Solution** 36 37 To maximize the number of multiples of $x$ less than $n$, it optimal to choose a small $x$, in this case, $2$. The only exception is $n = 3$, where it is optimal to choose $3$ instead, since both $2$ and $3$ have only one multiple less than $3$. 38 39 **Code (C++)** 40 41 ``` 42 #include <bits/stdc++.h> 43 using namespace std; 44 45 int main(){ 46 int t; cin >> t; 47 while(t--){ 48 int n; cin >> n; 49 cout << (n == 3 ? 3 : 2) << endl; 50 } 51 } 52 ``` 53 54 ##### [1985C - Good Prefixes](/contest/1985/problem/C "Codeforces Round 952 (Div. 4)") 55 56 Problem Credits: [sum](/profile/sum "Master sum") 57 Analysis: [cry](/profile/cry "Master cry") 58 59 **Solution** 60 61 The only element that can be the sum of all other elements is the maximum element, since all elements are positive. Therefore, for each prefix $i$ from $1$ to $n$, check if $sum(a_1, a_2, ..., a_i) - max(a_1, a_2, ..., a_i) = max(a_1, a_2, ..., a_i)$. The sum and max of prefixes can be tracked with variables outside the loop. 62 63 **Code (C++)** 64 65 ``` 66 #include <iostream> 67 using namespace std; 68 69 int main(){ 70 int t; cin >> t; 71 while(t--){ 72 int n; cin >> n; 73 int a[n]; 74 for(int i = 0; i < n; i++) 75 cin >> a[i]; 76 long long sum = 0; 77 int mx = 0, ans = 0;; 78 for(int i = 0; i < n; i++){ 79 sum += a[i]; 80 mx = max(mx, a[i]); 81 if(sum - mx == mx) 82 ans++; 83 } 84 cout << ans << endl; 85 } 86 } 87 ``` 88 89 ##### [1985D - Manhattan Circle](/contest/1985/problem/D "Codeforces Round 952 (Div. 4)") 90 91 Problem Credits: [cry](/profile/cry "Master cry") 92 Analysis: [cry](/profile/cry "Master cry") 93 94 **Solution** 95 96 Note that the manhattan circle is always in a diamond shape, symmetric from the center. Let's take notice of some special characteristics that can help us. One way is to find the top and bottom points of the circle. Note that these points will have columns at the center of the circle, so here we can acquire the value of $k$. To find $h$, since the circle is symmetric, it is just the middle of the rows of the top and bottom points. 97 98 Note that we never needed to find the value of $r$. 99 100 **Code (C++)** 101 102 ``` 103 #include <bits/stdc++.h> 104 using namespace std; 105 const int INF = 1e9; 106 107 int main(){ 108 int t; cin >> t; 109 while(t--){ 110 int n, m; cin >> n >> m; 111 vector<vector<char>> g(n, vector<char>(m)); 112 for(int i = 0; i < n; i++){ 113 for(int j = 0; j < m; j++){ 114 cin >> g[i][j]; 115 } 116 } 117 pair<int, int> top = {INF, INF}, bottom = {-INF, -INF}; 118 for(int i = 0; i < n; i++){ 119 for(int j = 0; j < m; j++){ 120 if(g[i][j] == '#'){ 121 top = min(top, {i, j}); 122 bottom = max(bottom, {i, j}); 123 } 124 } 125 } 126 assert(top.second == bottom.second); 127 cout << (top.first + bottom.first) / 2 + 1 << " " << top.second + 1 << endl; 128 } 129 } 130 ``` 131 132 ##### [1985E - Secret Box](/contest/1985/problem/E "Codeforces Round 952 (Div. 4)") 133 134 Problem Credits: [cry](/profile/cry "Master cry") 135 Analysis: [cry](/profile/cry "Master cry") 136 137 **Solution** 138 139 Since the side lengths of $S$ has to multiply to $k$, all three side lengths of $S$ has to be divisors of $k$. Let's denote the side lengths of $S$ along the $x$, $y$, and $z$ axes as $a$, $b$, and $c$ respectively. For $S$ to fit in $B$ , $a \leq x$, $b \leq y$, and $c \leq z$ must hold. Because of the low constraints, we can afford to loop through all possible values of $a$ and $b$, and deduce that $c=\frac{k}{a \cdot b}$ (make sure $c \leq z$ and $c$ is an integer). To get the amount of ways we can place $S$, we can just multiply the amount of shifting space along each axes, and that just comes down to $(x−a+1) \cdot (y−b+1) \cdot (z−c+1)$. The answer is the maximum among all possible values of $a$, $b$, and $c$ . 140 141 The time complexity is $\mathcal{O}(n^2)$ where $n$ is at most $2000$. 142 143 **Code (C++)** 144 145 ``` 146 #include <iostream> 147 using namespace std; 148 using ll = long long; 149 150 int main(){ 151 int t; cin >> t; 152 while(t--){ 153 ll x, y, z, k; cin >> x >> y >> z >> k; 154 ll ans = 0; 155 for(int a = 1; a <= x; a++){ 156 for(int b = 1; b <= y; b++){ 157 if(k % (a * b)) continue; 158 ll c = k / (a * b); 159 if(c > z) continue; 160 ll ways = (ll)(x - a + 1) * (y - b + 1) * (z - c + 1); 161 ans = max(ans, ways); 162 } 163 } 164 cout << ans << "\n"; 165 } 166 } 167 ``` 168 169 ##### [1985F - Final Boss](/contest/1985/problem/F "Codeforces Round 952 (Div. 4)") 170 171 Problem Credits: [cry](/profile/cry "Master cry"), [sum](/profile/sum "Master sum") 172 Analysis: [cry](/profile/cry "Master cry"), [sum](/profile/sum "Master sum") 173 174 **About Hacks** 175 176 Unfortunately, there was a lot of hacks on this problem, and we're sorry for it. Since our intended solution is not binary search, we didn't really take overflow using binary search seriously. I ([cry](/profile/cry "Master cry")) prepared this problem and I only took into account about overflow with big cooldown, but I forgot overflow can happen on attacks as well. I apologize and we will do better next time! 177 178 **Solution** 179 180 Since the sum of $h$ is bounded by $2 \cdot 10^5$, and each attack deals at least $1$ damage. If we assume every turn we can make at least one attack, the sum of turns to kill the boss in every test case is bounded by $2 \cdot 10^5$. This means that we can afford to simulate each turn where we make at least one attack. 181 182 But what if we cannot make an attack on this turn? Since the cooldown for each attack can be big, we cannot increment turns one by one. We must jump to the next turn we can make an attack. This can be done by retrieving the first element of a sorted set, where the set stores pairs {$t$, $i$} which means {next available turn you can use this attack, index of this attack} for all $i$. Here, we can set the current turn to $t$ and use all attacks in the set with first element in the pair equal to $t$. Remember to insert the pair to {$c_i + t$, $i$} back into the set after processing the attacks. 183 184 The time complexity is $\mathcal{O}(h \log n)$. 185 186 **Code (C++)** 187 188 ``` 189 #include <bits/stdc++.h> 190 using namespace std; 191 192 int main(){ 193 int t; cin >> t; 194 while(t--){ 195 int h, n; cin >> h >> n; 196 vector<int> a(n), c(n); 197 for(int& i: a) cin >> i; 198 for(int& i: c) cin >> i; 199 set<pair<long long, int>> S; 200 for(int i = 0; i < n; i++){ 201 S.insert({1, i}); 202 } 203 long long last_turn = 1; 204 while(h > 0){ 205 auto [turn, i] = *S.begin(); 206 S.erase(S.begin()); 207 last_turn = turn; 208 h -= a[i]; 209 S.insert({turn + c[i], i}); 210 } 211 cout << last_turn << "\n"; 212 } 213 } 214 215 // comment "tomato" if you see this comment 216 ``` 217 218 **Bonus** 219 220 Try to solve this if $1 \le h \le 10^9$. 221 222 **Solution** 223 224 We can do this by binary searching for the answer. For some time $t$, we know that we can perform an attack of cooldown $c$ exactly $\lfloor \frac{t - 1}{c} \rfloor + 1$ times. The total damage we will do in time $t$ will be: 225 226 $ \displaystyle \sum_{i=1}^{n}{a_i\left( \lfloor\frac{t - 1}{c_i}\rfloor + 1 \right)} $ 227 228 So we binary search for the first $t$ such that the total damage we do in time $t$ is greater than or equal to $h$. This runs in $\mathcal{O(n \log {(h \cdot \max c_i)})}$. Be careful of long long overflow! 229 230 **Code (C++)** 231 232 ``` 233 #include <bits/stdc++.h> 234 using namespace std; 235 236 #define ll long long 237 238 void solve(){ 239 ll h, n; 240 cin >> h >> n; 241 242 vector<ll> A(n), C(n); 243 244 for (ll &i : A) 245 cin >> i; 246 for (ll &i : C) 247 cin >> i; 248 249 auto chk = [&](ll t){ 250 ll dmg = 0; 251 for (int i = 0; i < n and dmg < h; i++){ 252 ll cnt = (t - 1) / C[i] + 1; 253 254 if (cnt >= h) 255 return true; 256 257 dmg += cnt * A[i]; 258 } 259 return dmg >= h; 260 }; 261 262 ll L = 1, H = 1e12; 263 264 while (L < H){ 265 ll M = (L + H) / 2; 266 chk(M) ? H = M : L = M + 1; 267 } 268 cout << L << "\n"; 269 } 270 271 int main(){ 272 ios_base::sync_with_stdio(0); cin.tie(0); 273 int tc; 274 cin >> tc; 275 276 while (tc--) 277 solve(); 278 } 279 ``` 280 281 ##### [1985G - D-Function](/contest/1985/problem/G "Codeforces Round 952 (Div. 4)") 282 283 Problem Credits: [cry](/profile/cry "Master cry") 284 Analysis: [cry](/profile/cry "Master cry") 285 286 **Solution** 287 288 To satisfy $D(k \cdot n) = k \cdot D(n)$, each digit $d$ in $n$ must become $k \cdot d$ after multiplying $n$ by $k$. In other words, none of $n$'s digits can carry over to the next digit upon multiplication. From this, we can deduce that each digit in $n$ must be less than or equal to $\lfloor \frac{9}{k} \rfloor$. Only thing left is to count all such numbers in the range of $10^l$ inclusive and $10^r$ exclusive. 289 290 Every number below ${10}^r$ has $r$ or less digits. For numbers with less than $r$ digits, let's pad the beginning with zeroes until it becomes a $r$ digit number (for example, if $r = 5$, then $69$ becomes $00069$). This allows us to consider numbers with less than $r$ digits the same way as numbers with exactly $r$ digits. For each digit, we have $\lfloor \frac{9}{k} \rfloor + 1$ choices (including zero), and there are $r$ digits, so the total number of numbers that satisfies the constraint below ${10}^r$ is $(\lfloor \frac{9}{k} \rfloor + 1)^r$. 291 292 To get the count of numbers in range, it suffices to subtract all valid numbers less than $10^l$. Therefore, the answer is $(\lfloor \frac{9}{k} \rfloor + 1)^r - (\lfloor \frac{9}{k} \rfloor + 1)^l$. To exponentiate fast, we can use [modular exponentiation](https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/). 293 294 **Code (Python)** 295 296 ``` 297 MOD = int(1e9+7) 298 t = int(input()) 299 for _ in range(t): 300 l, r, k = map(int, input().split()) 301 print((pow(9 // k + 1, r, MOD) - pow(9 // k + 1, l, MOD) + MOD) % MOD) 302 ``` 303 304 ##### [1985H1 - Maximize the Largest Component (Easy Version)](/contest/1985/problem/H1 "Codeforces Round 952 (Div. 4)") 305 306 Problem Credits: [sum](/profile/sum "Master sum") 307 Analysis: [sum](/profile/sum "Master sum") 308 309 **Solution** 310 311 Let's first solve the problem if we can only select and fill **rows**. Columns can be handled in the exact same way. 312 313 For each row $r$, we need to find the size of the component formed by filling row $r$ (i.e. the size of the component **containing** row $r$ if we set all cells in row $r$ to be $\texttt{#}$). 314 315 The size of the component **containing** row $r$ if we set all cells in row $r$ to be $\texttt{#}$ will be the **sum** of: 316 317 1. The number of $\texttt{.}$ in row $r$ since these cells will be set to $\texttt{#}$. Let $F_r$ denote this value for some row $r$. 318 2. The sum of sizes of components containing a cell in either row $r-1$, $r$, or $r+1$ (i.e. components that are touching row $r$). This is since these components will be part of the component containing row $r$. Let $R_r$ denote this value for some row $r$. 319 320 The challenge is computing the second term quickly. For some component, let $s$ be the size of the component and let $r_{min}$ and $r_{max}$ denote the minimum and maximum row of a cell in the component. This means that the component will contain cells with rows $r_{min},r_{min+1},...,r_{max}$. Note that we can find these values with a dfs. Since the component will contribute $s$ to rows in $[r_{min}-1,r_{min},\ldots r_{max}+1]$, we add $s$ to $R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$. This can be done naively or with prefix sums. 321 322 We find the maximum $F_r+R_r$ and then handle columns in the same way. This solution runs in $\mathcal{O}(nm)$ time. 323 324 **Code (C++)** 325 326 ``` 327 #include <bits/stdc++.h> 328 using namespace std; 329 330 int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 331 vector<vector<bool>> vis; vector<vector<char>> A; 332 333 void dfs(int i, int j){ 334 if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.') 335 return; 336 337 vis[i][j] = true; 338 339 sz++; 340 minR = min(minR, i); 341 maxR = max(maxR, i); 342 minC = min(minC, j); 343 maxC = max(maxC, j); 344 345 dfs(i - 1, j); 346 dfs(i + 1, j); 347 dfs(i, j - 1); 348 dfs(i, j + 1); 349 } 350 351 void solve(){ 352 cin >> n >> m; 353 354 R.assign(n + 5, 0); 355 C.assign(m + 5, 0); 356 freeR.assign(n + 5, 0); 357 freeC.assign(m + 5, 0); 358 vis.assign(n + 5, vector<bool>(m + 5, false)); 359 A.assign(n + 5, vector<char>(m + 5, ' ')); 360 361 for (int i = 1; i <= n; i++){ 362 for (int j = 1; j <= m; j++){ 363 cin >> A[i][j]; 364 365 if (A[i][j] == '.'){ 366 freeR[i]++; 367 freeC[j]++; 368 } 369 } 370 } 371 372 for (int i = 1; i <= n; i++){ 373 for (int j = 1; j <= m; j++){ 374 if (vis[i][j] or A[i][j] == '.') 375 continue; 376 377 // Reset 378 sz = 0; 379 minR = 1e9; 380 maxR = -1e9; 381 minC = 1e9; 382 maxC = -1e9; 383 384 dfs(i, j); 385 386 // Expand by 1 since adjacent cells also connect 387 minR = max(minR - 1, 1); 388 maxR = min(maxR + 1, n); 389 minC = max(minC - 1, 1); 390 maxC = min(maxC + 1, m); 391 392 // Update prefix sums 393 R[minR] += sz; 394 R[maxR + 1] -= sz; 395 396 C[minC] += sz; 397 C[maxC + 1] -= sz; 398 } 399 } 400 401 ans = 0; 402 403 for (int i = 1; i <= n; i++){ 404 R[i] += R[i - 1]; 405 ans = max(ans, freeR[i] + R[i]); 406 } 407 for (int i = 1; i <= m; i++){ 408 C[i] += C[i - 1]; 409 ans = max(ans, freeC[i] + C[i]); 410 } 411 412 cout << ans << "\n"; 413 } 414 415 int main(){ 416 ios_base::sync_with_stdio(0); cin.tie(0); 417 int tc; 418 cin >> tc; 419 420 while (tc--) 421 solve(); 422 } 423 ``` 424 425 ##### [1985H2 - Maximize the Largest Component (Hard Version)](/contest/1985/problem/H2 "Codeforces Round 952 (Div. 4)") 426 427 Problem Credits: [sum](/profile/sum "Master sum") 428 Analysis: [sum](/profile/sum "Master sum") 429 430 **Solution** 431 432 For each row $r$ and column $c$, we need to find the size of the component formed by filling both row $r$ and column $c$ (i.e. the size of the component **containing** row $r$ and column $c$ if we set all cells in both row $r$ and column $c$ to be $\texttt{#}$). 433 434 Extending the reasoning in H1, for some row $r$ and column $c$, consider the sum of: 435 436 1. The number of $\texttt{.}$ in row $r$ or column $c$ since these cells will be set to $\texttt{#}$. Let $F_{r,c}$ denote this value for some row $r$ and column $c$. 437 2. The sum of sizes of components containing a cell in either row $r-1$, $r$, or $r+1$ (i.e. components that are touching row $r$). This is since these components will be part of the component containing row $r$ and column $c$. Let $R_r$ denote this value for some row $r$. 438 3. The sum of sizes of components containing a cell in either column $c-1$, $c$, or $c+1$ (i.e. components that are touching column $c$). This is since these components will be part of the component containing row $r$ and column $c$. Let $C_c$ denote this value for some column $c$. 439 440 However, components that contain a cell in either row $r-1$, $r$, or $r+1$ as well as in either column $c-1$, $c$, or $c+1$ will be **overcounted** (since it will be counted in both terms $2$ and $3$) (you can think of it as components touching both row $r$ and column $c$). Thus, we need to subtract the sum of sizes of components that contain a cell in either row $r-1$, $r$, or $r+1$ as well as in either column $c-1$, $c$, or $c+1$. Let $B_{r,c}$ denote this for some row $r$ and column $c$. 441 442 Then the size of the component formed by filling both row $r$ and column $c$ will be $F_{r,c}+R_r+C_c-B_{r,c}$ and we want to find the maximum value of this. 443 444 Let's try to calculate these values efficiently. Consider some component. 445 446 1. Let $s$ be its size. 447 2. Let $r_{min}$ and $r_{max}$ denote the minimum and maximum row of a cell in the component. This means that the component contains cells with rows $r_{min},r_{min+1},...,r_{max}$. 448 3. Let $c_{min}$ and $c_{max}$ denote the minimum and maximum column of a cell in the component. This means that the component contains cells with columns $c_{min},c_{min+1},...,c_{max}$. 449 450 All these values can be found with a dfs. We then do the following updates: 451 452 1. Add $s$ to $R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$. This can be done naively or with prefix sums. 453 2. Add $s$ to $C_{c_{min}-1},C_{c_{min}},\ldots,C_{c_{max}+1}$. This can be done naively or with prefix sums. 454 3. Add $s$ to the subrectangle of $B$ with top left at ($r_{min}-1,c_{min}-1$) and bottom right at ($r_{max}+1,c_{max}+1$). This can be done with 2D prefix sums. (Note that doing this naively will pass because of low constant factor and the fact that we could not cut this solution without cutting slow correct solutions.) 455 456 We do this for each component. Also, calculating $F_{r,c}$ can be done by looking at the number of $\texttt{.}$ in row $r$, column $c$, and checking whether we overcounted a $\texttt{.}$ at ($r,c$). In all, this solution runs in $\mathcal{O}(nm)$ time. 457 458 **Code (C++)** 459 460 ``` 461 #include <bits/stdc++.h> 462 using namespace std; 463 464 int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 465 vector<vector<int>> RC; vector<vector<bool>> vis; vector<vector<char>> A; 466 467 void dfs(int i, int j){ 468 if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.') 469 return; 470 471 vis[i][j] = true; 472 473 sz++; 474 minR = min(minR, i); 475 maxR = max(maxR, i); 476 minC = min(minC, j); 477 maxC = max(maxC, j); 478 479 dfs(i - 1, j); 480 dfs(i + 1, j); 481 dfs(i, j - 1); 482 dfs(i, j + 1); 483 } 484 485 void solve(){ 486 cin >> n >> m; 487 488 R.assign(n + 5, 0); 489 C.assign(m + 5, 0); 490 freeR.assign(n + 5, 0); 491 freeC.assign(m + 5, 0); 492 RC.assign(n + 5, vector<int>(m + 5, 0)); 493 vis.assign(n + 5, vector<bool>(m + 5, false)); 494 A.assign(n + 5, vector<char>(m + 5, ' ')); 495 496 for (int i = 1; i <= n; i++){ 497 for (int j = 1; j <= m; j++){ 498 cin >> A[i][j]; 499 500 if (A[i][j] == '.'){ 501 freeR[i]++; 502 freeC[j]++; 503 } 504 } 505 } 506 507 for (int i = 1; i <= n; i++){ 508 for (int j = 1; j <= m; j++){ 509 if (vis[i][j] or A[i][j] == '.') 510 continue; 511 512 // Reset 513 sz = 0; 514 minR = 1e9; 515 maxR = -1e9; 516 minC = 1e9; 517 maxC = -1e9; 518 519 dfs(i, j); 520 521 // Expand by 1 since adjacent cells also connect 522 minR = max(minR - 1, 1); 523 maxR = min(maxR + 1, n); 524 minC = max(minC - 1, 1); 525 maxC = min(maxC + 1, m); 526 527 // Update prefix sums 528 R[minR] += sz; 529 R[maxR + 1] -= sz; 530 531 C[minC] += sz; 532 C[maxC + 1] -= sz; 533 534 RC[minR][minC] += sz; 535 RC[maxR + 1][minC] -= sz; 536 RC[minR][maxC + 1] -= sz; 537 RC[maxR + 1][maxC + 1] += sz; 538 } 539 } 540 541 for (int i = 1; i <= n; i++) 542 R[i] += R[i - 1]; 543 544 for (int i = 1; i <= m; i++) 545 C[i] += C[i - 1]; 546 547 for (int i = 1; i <= n; i++) 548 for (int j = 1; j <= m; j++) 549 RC[i][j] += RC[i - 1][j] + RC[i][j - 1] - RC[i - 1][j - 1]; 550 551 ans = 0; 552 553 for (int i = 1; i <= n; i++) 554 for (int j = 1; j <= m; j++) 555 ans = max(ans, (R[i] + C[j] - RC[i][j]) + (freeR[i] + freeC[j] - (A[i][j] == '.'))); 556 557 cout << ans << "\n"; 558 } 559 560 int main(){ 561 ios_base::sync_with_stdio(0); cin.tie(0); 562 int tc; 563 cin >> tc; 564 565 while (tc--) 566 solve(); 567 } 568 ```