1358.md (13953B)
1 Source: https://codeforces.com/blog/entry/77869 2 3 This is our first contest for the three of us ([Alexdat2000](/profile/Alexdat2000 "Candidate Master Alexdat2000"), [crazyilian](/profile/crazyilian "Candidate Master crazyilian"), [sevlll777](/profile/sevlll777 "Master sevlll777")), so we would like to share our impressions of creating this contest. Check it if you want to! 4 5 **ROUND LOG** 6 7 First problem — task rejections. [300iq](/profile/300iq "Legendary Grandmaster 300iq") rejected about 13 problems, 6 of which were supposed to be problem D. In the end, we came up with E, and the old E moved to D. 8 9 These are the verdicts with which the problems were rejected: 10 11 1. The idea is very simple here and the implementation is very simple too, this problem is definitely not D1C-D and definitely not interesting. 12 2. Not an interesting problem, too standard, without new ideas. 13 3. This is a known problem which is solved quite simply by a compressed tree. 14 4. Unfortunately, it seems to me that this problem does not fit D1B. It is a funny construct but it is too technical (not interesting enough) for this position and too simple for the next ones. 15 5. This problem is solved very simply by taking a close look at the sequence, so it is not very interesting. 16 6. It seems to me that this problem is too standard. It is as if in the condition it is written, which dp should be written. 17 7. The idea of 4 consecutive numbers is known. 18 8. It's a known problem. 19 9. It's a known problem. 20 10. It's too standard. 21 11. There's some greed in there. Is that the right thing to do? 22 12. Well, first of all, it's doubtful you have any proof. Second of all, isn't that on oeis? 23 13. It doesn't make her any better, it's a known problem. 24 25 When the problems were already formed, their creation began. In some problems, it was necessary to lower the constraints, which made it impossible to cut off some non-deterministic or not optimal solutions. 26 27 Otherwise, everything was fine until the last 18 hours before the contest began... 28 29 * Mike [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Mirzayanov sent 7 issues to problem A. It was necessary to redo all the tests in the problem and much more. 30 * While we were correcting them, coordinator Ildar [300iq](/profile/300iq "Legendary Grandmaster 300iq") Gainullin told us to remove all the illustrations for the problem (memes and just cool pictures at the bottom of the notes). We did not like it *very* much, we wanted the pictures to be included in the contest. 31 * We finished fixing problem A, and went to bed. At that time Ildar (thank him very much) was polishing the conditions of all the other problems. Unfortunately, at that moment he removed the pictures. He also suddenly renamed problem F and city in the English version of problem D. 32 * 4 hours before the beginning. Mikhail Mirzayanov started sending issues to other problems. 33 * We had to redo almost all the tests for problems B, C and D. 34 * Heroically won the limits in E 2 hours before the contest start. 35 36 A total of 475 commits to the Polygon were made. 37 38 During the round there were many of the same type, but also some funny clares. For example: 39 40 * Problem C. *i cant solve it* 41 * Problem E. *When will a COVID 19 vaccine come out???* 42 43 Thanks to everyone who upvotes this editorial! 44 45 And, of course, here's the tutorial of the round. 46 47 [1358A - Park Lighting](/contest/1358/problem/A "Codeforces Round 645 (Div. 2)") 48 Idea: [Alexdat2000](/profile/Alexdat2000 "Candidate Master Alexdat2000") 49 50 **Picture** 51 52  53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution** 59 60 ``` 61 #include <iostream> 62 63 using namespace std; 64 65 int main() { 66 int t, n, m; 67 cin >> t; 68 while (t--) { 69 cin >> n >> m; 70 cout << (n * m + 1) / 2 << '\n'; 71 } 72 } 73 ``` 74 75 [1358B - Maria Breaks the Self-isolation](/contest/1358/problem/B "Codeforces Round 645 (Div. 2)") 76 Idea: [crazyilian](/profile/crazyilian "Candidate Master crazyilian") 77 78 **Picture** 79 80  81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution** 87 88 ``` 89 #include <iostream> 90 #include <vector> 91 #include <algorithm> 92 93 using namespace std; 94 95 void solve() { 96 int n; 97 cin >> n; 98 vector<int> arr(n); 99 for (int &el : arr) 100 cin >> el; 101 sort(arr.begin(), arr.end()); 102 for (int i = n - 1; i >= 0; i--) { 103 if (arr[i] <= i + 1) { 104 cout << i + 2 << '\n'; 105 return; 106 } 107 } 108 cout << 1 << '\n'; 109 } 110 111 int main() { 112 int t; 113 cin >> t; 114 while (t--) 115 solve(); 116 } 117 ``` 118 119 [1358C - Celex Update](/contest/1358/problem/C "Codeforces Round 645 (Div. 2)") 120 Idea: [crazyilian](/profile/crazyilian "Candidate Master crazyilian") 121 122 **Picture** 123 124  125 126 **Tutorial** 127 128 Tutorial is loading... 129 130 **Solution** 131 132 ``` 133 #include <iostream> 134 135 using namespace std; 136 137 int main() { 138 int t; 139 cin >> t; 140 while (t--) { 141 long long a, b, c, d; 142 cin >> a >> b >> c >> d; 143 cout << (c - a) * (d - b) + 1 << '\n'; 144 } 145 } 146 ``` 147 148 [1358D - The Best Vacation](/contest/1358/problem/D "Codeforces Round 645 (Div. 2)") 149 Idea: [sevlll777](/profile/sevlll777 "Master sevlll777") 150 151 **Picture** 152 153  154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution** 160 161 ``` 162 #include <iostream> 163 #include <algorithm> 164 #include <vector> 165 166 #define int long long 167 168 using namespace std; 169 170 signed main() { 171 int n, len; 172 cin >> n >> len; 173 vector<int> A(2 * n); 174 for (int i = 0; i < n; i++) { 175 cin >> A[i]; 176 A[n + i] = A[i]; 177 } 178 n *= 2; 179 180 vector<int> B = {0}, C = {0}; 181 for (int i = 0; i < n; i++) 182 B.push_back(B.back() + A[i]); 183 for (int i = 0; i < n; i++) 184 C.push_back(C.back() + (A[i] * (A[i] + 1)) / 2); 185 int ans = 0; 186 for (int i = 0; i < n; i++) { 187 if (B[i + 1] >= len) { 188 int z = upper_bound(B.begin(), B.end(), B[i + 1] - len) - B.begin(); 189 int cnt = C[i + 1] - C[z]; 190 int days = B[i + 1] - B[z]; 191 int too = len - days; 192 cnt += ((A[z - 1] * (A[z - 1] + 1)) / 2); 193 cnt -= (((A[z - 1] - too) * (A[z - 1] - too + 1)) / 2); 194 ans = max(ans, cnt); 195 } 196 } 197 cout << ans; 198 } 199 ``` 200 201 [1358E - Are You Fired?](/contest/1358/problem/E "Codeforces Round 645 (Div. 2)") 202 Idea: [sevlll777](/profile/sevlll777 "Master sevlll777") и [crazyilian](/profile/crazyilian "Candidate Master crazyilian") 203 204 **Picture** 205 206  207 208 **Tutorial** 209 210 Tutorial is loading... 211 212 **Solution** 213 214 ``` 215 #include <iostream> 216 #include <vector> 217 218 using namespace std; 219 220 #define int long long 221 222 signed main() { 223 int n; 224 cin >> n; 225 int N = (n + 1) / 2; 226 vector<int> a(N); 227 for (int &el : a) 228 cin >> el; 229 int Ax; 230 cin >> Ax; 231 vector<int> m(N + 1, 0); 232 int Pprefsm = 0; 233 for (int i = 1; i < N + 1; ++i) { 234 Pprefsm += Ax - a[i - 1]; 235 m[i] = min(m[i - 1], Pprefsm); 236 } 237 int Aprefsm = 0; 238 for (int k = 1; k <= N; ++k) 239 Aprefsm += a[k - 1]; 240 for (int k = N; k <= n; ++k) { 241 if (Aprefsm + m[n - k] > 0) 242 return cout << k, 0; 243 Aprefsm += Ax; 244 } 245 cout << -1; 246 } 247 ``` 248 249 [1358F - Tasty Cookie](/contest/1358/problem/F "Codeforces Round 645 (Div. 2)") 250 Idea: [sevlll777](/profile/sevlll777 "Master sevlll777") и [crazyilian](/profile/crazyilian "Candidate Master crazyilian") 251 252 **Picture** 253 254  255 256 **Tutorial** 257 258 Tutorial is loading... 259 260 **Solution by Alexdat2000** 261 262 ``` 263 #include <bits/stdc++.h> 264 265 using namespace std; 266 267 #define int long long 268 const int LIM = 2e5; 269 270 bool is_increasing(const vector<int> &vec) { 271 for (int i = 0; i < vec.size() - 1; i++) { 272 if (vec[i] >= vec[i + 1]) 273 return false; 274 } 275 return true; 276 } 277 278 bool is_decreasing(const vector<int> &vec) { 279 for (int i = 0; i < vec.size() - 1; i++) { 280 if (vec[i] <= vec[i + 1]) 281 return false; 282 } 283 return true; 284 } 285 286 vector<int> rollback(const vector<int> &vec) { 287 vector<int> ans(vec.size()); 288 ans[0] = vec[0]; 289 for (int i = 1; i < vec.size(); i++) 290 ans[i] = vec[i] - vec[i - 1]; 291 return ans; 292 } 293 294 signed main() { 295 int n; 296 cin >> n; 297 vector<int> a(n), b(n); 298 for (int &i : a) 299 cin >> i; 300 for (int &i : b) 301 cin >> i; 302 vector<int> a_rev = a; 303 reverse(a_rev.begin(), a_rev.end()); 304 305 if (n == 1) { 306 if (a == b) 307 cout << "SMALL" << '\n' << 0 << '\n'; 308 else 309 cout << "IMPOSSIBLE" << '\n'; 310 return 0; 311 } 312 313 int sum_a = accumulate(a.begin(), a.end(), 0LL); 314 int sum_b = accumulate(b.begin(), b.end(), 0LL); 315 int rollback_cnt = 0; 316 317 if (n == 2) { 318 vector<int> ans; // -1 = R, X = PPP..PP (x times) 319 int move_cnt = 0, roll_cnt = 0; // both types 320 321 bool rev = a[0] > a[1]; 322 if (rev) 323 swap(a[0], a[1]); 324 325 if (b[0] > b[1]) { 326 swap(b[0], b[1]); 327 ans.push_back(-1); 328 move_cnt++; 329 } 330 while (true) { 331 if (sum_a > sum_b) { 332 cout << "IMPOSSIBLE" << '\n'; 333 return 0; 334 } 335 336 if (sum_a == sum_b) { 337 if (a != b) { 338 cout << "IMPOSSIBLE" << '\n'; 339 return 0; 340 } 341 342 if (rev) { 343 ans.push_back(-1); 344 move_cnt++; 345 } 346 347 if (rollback_cnt > LIM) { 348 cout << "BIG" << '\n' << rollback_cnt << '\n'; 349 return 0; 350 } else { 351 cout << "SMALL" << '\n' << move_cnt << '\n'; 352 reverse(ans.begin(), ans.end()); 353 for (auto i : ans) { 354 if (i == -1) 355 cout << "R"; 356 else { 357 for (int _ = 0; _ < i; _++) 358 cout << "P"; 359 } 360 } 361 cout << '\n'; 362 return 0; 363 } 364 } 365 366 if (a[0] == b[0]) { 367 if ((b[1] - a[1]) % b[0] == 0) { 368 roll_cnt = (b[1] - a[1]) / b[0]; 369 ans.push_back(roll_cnt); 370 move_cnt += roll_cnt, rollback_cnt += roll_cnt; 371 b = a; 372 sum_b = b[0] + b[1]; 373 } else { 374 cout << "IMPOSSIBLE" << '\n'; 375 return 0; 376 } 377 } else { 378 roll_cnt = b[1] / b[0]; 379 ans.push_back(roll_cnt); 380 move_cnt += roll_cnt, rollback_cnt += roll_cnt; 381 382 ans.push_back(-1); 383 move_cnt++; 384 swap(b[0], b[1]); 385 b[0] %= b[1]; 386 sum_b = b[0] + b[1]; 387 } 388 } 389 } 390 391 string ans; 392 393 while (true) { 394 if (sum_a == sum_b) { 395 if (a_rev == b) { 396 ans.push_back('R'); 397 reverse(b.begin(), b.end()); 398 } 399 if (a == b) { 400 reverse(ans.begin(), ans.end()); 401 if (rollback_cnt > LIM) 402 cout << "BIG" << '\n' << rollback_cnt << '\n'; 403 else 404 cout << "SMALL" << '\n' << ans.size() << '\n' << ans << '\n'; 405 } else 406 cout << "IMPOSSIBLE" << '\n'; 407 return 0; 408 } else if (is_increasing(b)) { 409 b = rollback(b); 410 sum_b = accumulate(b.begin(), b.end(), 0LL); 411 ans += 'P'; 412 rollback_cnt++; 413 } else if (is_decreasing(b)) { 414 reverse(b.begin(), b.end()); 415 ans += 'R'; 416 } else { 417 cout << "IMPOSSIBLE" << '\n'; 418 return 0; 419 } 420 } 421 } 422 ``` 423 424 **Solution by Alivk06 (much shorter)** 425 426 ``` 427 #include <bits/stdc++.h> 428 429 using namespace std; 430 #define int long long 431 432 signed main() { 433 int n; 434 cin >> n; 435 vector<int> a(n), b(n); 436 for (int i = 0; i < n; ++i) cin >> a[i]; 437 for (int i = 0; i < n; ++i) cin >> b[i]; 438 if (n == 1) { 439 if (a[0] == b[0]) cout << "SMALL\n" << 0; 440 else cout << "IMPOSSIBLE"; 441 return 0; 442 } 443 if (n == 2) { 444 vector<pair<int, bool>> res; 445 int kol = 0; 446 while (true) { 447 if (b[0] == 0 || b[1] == 0) { 448 cout << "IMPOSSIBLE"; 449 return 0; 450 } 451 if (a == b) break; 452 if (a[0] == b[1] && a[1] == b[0]) { 453 res.emplace_back(1, false); 454 break; 455 } 456 if (b[0] == b[1]) { 457 cout << "IMPOSSIBLE"; 458 return 0; 459 } 460 if (b[0] > b[1]) { 461 res.emplace_back(1, false); 462 swap(b[0], b[1]); 463 } 464 if (a[0] == b[0] && a[1] < b[1] && a[1] % b[0] == b[1] % b[0]) { 465 res.emplace_back((b[1] - a[1]) / b[0], true); 466 kol += res.back().first; 467 break; 468 } 469 if (a[1] == b[0] && a[0] < b[1] && a[0] % b[0] == b[1] % b[0]) { 470 res.emplace_back((b[1] - a[0]) / b[0], true); 471 kol += res.back().first; 472 res.emplace_back(1, false); 473 break; 474 } 475 kol += b[1] / b[0]; 476 res.emplace_back(b[1] / b[0], true); 477 b[1] %= b[0]; 478 } 479 if (kol > 2e5) { 480 cout << "BIG\n"; 481 cout << kol; 482 } else { 483 cout << "SMALL\n"; 484 int flex = 0; 485 for (auto i : res) flex += i.first; 486 cout << flex << "\n"; 487 for (int i = res.size() - 1; i >= 0; --i) { 488 for (int j = 0; j < res[i].first; ++j) { 489 if (res[i].second) cout << "P"; 490 else cout << "R"; 491 } 492 } 493 } 494 return 0; 495 } 496 vector<bool> ans; 497 int kol = 0; 498 while (true) { 499 if (a == b) break; 500 reverse(b.begin(), b.end()); 501 if (a == b) { 502 ans.push_back(false); 503 break; 504 } 505 reverse(b.begin(), b.end()); 506 bool vozr = false, ub = false, r = false; 507 for (int i = 1; i < n; ++i) { 508 if (b[i] > b[i - 1]) vozr = true; 509 else if (b[i] < b[i - 1]) ub = true; 510 else r = true; 511 } 512 if (r || (vozr && ub)) { 513 cout << "IMPOSSIBLE"; 514 return 0; 515 } 516 vector<int> c(n); 517 if (ub) { 518 ans.push_back(false); 519 reverse(b.begin(), b.end()); 520 } 521 c[0] = b[0]; 522 for (int i = 1; i < n; ++i) { 523 c[i] = b[i] - b[i - 1]; 524 } 525 ans.push_back(true); 526 b = c; 527 ++kol; 528 } 529 if (kol > 2e5) { 530 cout << "BIG\n" << kol; 531 } else { 532 cout << "SMALL\n" << ans.size() << "\n"; 533 for (int i = ans.size() - 1; i >= 0; --i) { 534 if (ans[i]) cout << "P"; 535 else cout << "R"; 536 } 537 } 538 } 539 ``` 540 541 Thank you, everyone, for participating in the round! We hope you've raised your rating! And if you haven't, don't be sad, you'll do it!