1607.md (11230B)
1 Source: https://codeforces.com/blog/entry/96604 2 3 ### Short information 4 5 Sorry for another delayed editorial, I know I promised that it will come out sooner the previous time, but I wasn't feeling well today, so the work was slower than usual. 6 7 **About problem F:** 8 9 I am once again sorry for the inconveniences caused by tight ML in this problem. It was not the intended behavior since we relied too much on the main solution and didn't assume most of the solutions using DFS will fail. In this editorial I attach the code of the main solution that we expected from the beginning, it uses ~75MB of memory. 10 11 I guess, Div. 3 Rounds are not only for participants to learn but also can serve as educational for authors as well. I'll try not to repeat the same mistakes the next time :) Thanks to everyone for participating and hope to see you again! 12 13 ### The editorial 14 15 [1607A - Linear Keyboard](/contest/1607/problem/A "Codeforces Round 753 (Div. 3)") 16 17 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 18 19 **Tutorial** 20 21 Tutorial is loading... 22 23 **Solution** 24 25 ``` 26 t = int(input()) 27 for _ in range(t): 28 k, s = input(), input() 29 res = 0 30 for i in range(1, len(s)): 31 res += abs(k.index(s[i]) - k.index(s[i - 1])) 32 print(res) 33 ``` 34 35 [1607B - Odd Grasshopper](/contest/1607/problem/B "Codeforces Round 753 (Div. 3)") 36 37 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 t = int(input()) 47 maps = [ 48 lambda x: 0, 49 lambda x: x, 50 lambda x: -1, 51 lambda x: -x - 1 52 ] 53 54 for _ in range(t): 55 x0, n = map(int, input().split()) 56 d = maps[n % 4](n) 57 print(x0 - d if x0 % 2 == 0 else x0 + d) 58 ``` 59 60 [1607C - Minimum Extraction](/contest/1607/problem/C "Codeforces Round 753 (Div. 3)") 61 62 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution** 69 70 ``` 71 t = int(input()) 72 73 for _ in range(t): 74 n = int(input()) 75 a = sorted(list(map(int, input().split()))) 76 res = a[0] 77 for i in range(n - 1): 78 res = max(res, a[i + 1] - a[i]) 79 print(res) 80 ``` 81 82 [1607D - Blue-Red Permutation](/contest/1607/problem/D "Codeforces Round 753 (Div. 3)") 83 84 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution** 91 92 ``` 93 #include <bits/stdc++.h> 94 95 using namespace std; 96 97 #define forn(i, n) for (int i = 0; i < int(n); i++) 98 99 int main() { 100 int t; 101 cin >> t; 102 forn(tt, t) { 103 int n; 104 cin >> n; 105 vector<int> a(n); 106 forn(i, n) 107 cin >> a[i]; 108 109 string c; 110 cin >> c; 111 112 vector<int> l, r; 113 forn(i, n) 114 (c[i] == 'B' ? l : r).push_back(a[i]); 115 sort(l.begin(), l.end()); 116 sort(r.begin(), r.end(), greater<int>()); 117 118 bool ok = true; 119 forn(i, l.size()) 120 if (l[i] < i + 1) 121 ok = false; 122 forn(i, r.size()) 123 if (r[i] > n - i) 124 ok = false; 125 126 cout << (ok ? "YES" : "NO") << '\n'; 127 } 128 } 129 ``` 130 131 [1607E - Robot on the Board 1](/contest/1607/problem/E "Codeforces Round 753 (Div. 3)") 132 133 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 134 135 **Tutorial** 136 137 Tutorial is loading... 138 139 **Solution** 140 141 ``` 142 #include <bits/stdc++.h> 143 144 using namespace std; 145 146 int main() { 147 int t; 148 cin >> t; 149 while (t--) { 150 int n, m; 151 cin >> n >> m; 152 string s; 153 cin >> s; 154 155 int bx = 0, by = 0; 156 int min_bx = 0, max_bx = 0, min_by = 0, max_by = 0; 157 for (char c: s) { 158 if (c == 'L') min_by = min(min_by, --by); 159 else if (c == 'R') max_by = max(max_by, ++by); 160 else if (c == 'U') min_bx = min(min_bx, --bx); 161 else max_bx = max(max_bx, ++bx); 162 163 if (max_bx - min_bx >= n) { 164 if (bx == min_bx) min_bx++; 165 break; 166 } 167 if (max_by - min_by >= m) { 168 if (by == min_by) min_by++; 169 break; 170 } 171 } 172 173 cout << 1 - min_bx << ' ' << 1 - min_by << '\n'; 174 } 175 } 176 ``` 177 178 [1607F - Robot on the Board 2](/contest/1607/problem/F "Codeforces Round 753 (Div. 3)") 179 180 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 181 182 **Tutorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 using namespace std; 192 193 typedef vector<int> vi; 194 typedef pair<int, int> pii; 195 196 int main() { 197 int t; 198 cin >> t; 199 while (t--) { 200 int n, m; 201 cin >> n >> m; 202 vector<string> dir(n); 203 for (int i = 0; i < n; i++) 204 cin >> dir[i]; 205 206 vector<vi> res(n, vi(m, 0)); 207 int opt = 0, optr = 0, optc = 0; 208 for (int r = 0; r < n; r++) { 209 for (int c = 0; c < m; c++) { 210 if (res[r][c] > 0) 211 continue; 212 213 int nr = r, nc = c; 214 int depth = 0; 215 vector<pii> path; 216 auto ok = [&n, &m](int row, int col) { 217 return row > -1 && row < n && col > -1 && col < m; 218 }; 219 220 do { 221 res[nr][nc] = --depth; 222 path.emplace_back(nr, nc); 223 if (dir[nr][nc] == 'L') 224 nc--; 225 else if (dir[nr][nc] == 'R') 226 nc++; 227 else if (dir[nr][nc] == 'U') 228 nr--; 229 else 230 nr++; 231 } while (ok(nr, nc) && res[nr][nc] == 0); 232 233 int start = 1; 234 if (ok(nr, nc)) { 235 if (res[nr][nc] < 0) { 236 int cycle = res[nr][nc] - depth + 1; 237 for (int i = 0; i < cycle; i++) { 238 auto p = path.back(); 239 path.pop_back(); 240 res[p.first][p.second] = cycle; 241 } 242 } 243 start = res[nr][nc] + 1; 244 } 245 while (!path.empty()) { 246 auto p = path.back(); 247 path.pop_back(); 248 res[p.first][p.second] = start++; 249 } 250 251 if (res[r][c] > opt) { 252 opt = res[r][c]; 253 optr = r; 254 optc = c; 255 } 256 } 257 } 258 259 cout << optr + 1 << ' ' << optc + 1 << ' ' << opt << '\n'; 260 } 261 } 262 ``` 263 264 [1607G - Banquet Preparations 1](/contest/1607/problem/G "Codeforces Round 753 (Div. 3)") 265 266 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov") 267 268 **Tutorial** 269 270 Tutorial is loading... 271 272 **Solution** 273 274 ``` 275 #include <bits/stdc++.h> 276 277 using namespace std; 278 279 typedef pair<int, int> pii; 280 typedef long long ll; 281 282 int main() { 283 int t; 284 cin >> t; 285 while (t--) { 286 int n, m; 287 cin >> n >> m; 288 vector<pii> dishes(n); 289 ll balance = 0; 290 ll max_a = 0, max_b = 0; 291 ll total_eat = static_cast<long long>(n) * m; 292 293 for (int i = 0; i < n; i++) { 294 cin >> dishes[i].first >> dishes[i].second; 295 balance += dishes[i].first - dishes[i].second; 296 max_a += min(m, dishes[i].first); 297 max_b += min(m, dishes[i].second); 298 } 299 ll max_delta = 2 * max_a - total_eat, min_delta = total_eat - 2 * max_b; 300 ll min_a = total_eat - max_b; 301 302 ll eat_a; 303 if (balance < 0) { 304 eat_a = min_a; 305 if (balance - min_delta >= 0) 306 eat_a = min(max_a, (total_eat + balance + 1) / 2); 307 } else { 308 eat_a = max_a; 309 if (balance - max_delta <= 0) 310 eat_a = min(max_a, (total_eat + balance + 1) / 2); 311 } 312 ll ans = abs(balance - 2 * eat_a + total_eat); 313 314 cout << ans << '\n'; 315 ll rest_a = eat_a - min_a; 316 for (int i = 0; i < n; i++) { 317 ll cur_a = 0; 318 if (dishes[i].second < m) 319 cur_a += m - dishes[i].second; 320 ll add = min(rest_a, min(m - cur_a, dishes[i].first - cur_a)); 321 cur_a += add; 322 rest_a -= add; 323 cout << cur_a << ' ' << m - cur_a << '\n'; 324 } 325 } 326 } 327 ``` 328 329 [1607H - Banquet Preparations 2](/contest/1607/problem/H "Codeforces Round 753 (Div. 3)") 330 331 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 332 333 **Tutorial** 334 335 Tutorial is loading... 336 337 **Solution** 338 339 ``` 340 #include <bits/stdc++.h> 341 342 using namespace std; 343 344 #define forn(i, n) for (int i = 0; i < int(n); i++) 345 346 struct seg { 347 int a, b, m; 348 int index; 349 }; 350 351 int n, ans; 352 vector<seg> segments; 353 map<int, vector<seg>> diags; 354 355 void erase(multiset<pair<pair<int,int>, int>>& lr, int l, int r, int index) { 356 pair<pair<int,int>,int> plr = make_pair(make_pair(l, r), index); 357 auto i = lr.find(plr); 358 assert(i != lr.end()); 359 lr.erase(i); 360 } 361 362 void erase(multiset<pair<pair<int,int>, int>>& lr, multiset<pair<pair<int,int>, int>>& rl, int l, int r, int index) { 363 erase(lr, l, r, index); 364 erase(rl, r, l, index); 365 } 366 367 map<int, pair<int,int>> dd; 368 369 void setup_dd(int index, int value) { 370 assert(dd.count(index) == 0); 371 int x = segments[index].a - value; 372 int y = segments[index].m - x; 373 assert(segments[index].a - x >= 0); 374 assert(segments[index].b - y >= 0); 375 assert(x + y == segments[index].m); 376 dd[index] = make_pair(x, y); 377 } 378 379 int solve(vector<seg> s) { 380 int n = s.size(); 381 multiset<pair<pair<int,int>, int>> lr; 382 multiset<pair<pair<int,int>, int>> rl; 383 forn(i, n) { 384 int min_d = max(s[i].m - s[i].b, 0); 385 int max_d = min(s[i].a, s[i].m); 386 lr.insert(make_pair(make_pair(s[i].a - max_d, s[i].a - min_d), s[i].index)); 387 rl.insert(make_pair(make_pair(s[i].a - min_d, s[i].a - max_d), s[i].index)); 388 } 389 390 int result = 0; 391 while (!rl.empty()) { 392 result++; 393 auto min_r_iterator = rl.begin(); 394 int r = min_r_iterator->first.first; 395 int l = min_r_iterator->first.second; 396 int index = min_r_iterator->second; 397 erase(lr, rl, l, r, index); 398 setup_dd(index, r); 399 400 while (!lr.empty()) { 401 auto min_l_iterator = lr.begin(); 402 int ll = min_l_iterator->first.first; 403 int rr = min_l_iterator->first.second; 404 int ii = min_l_iterator->second; 405 if (ll <= r) { 406 erase(lr, rl, ll, rr, ii); 407 setup_dd(ii, r); 408 } else 409 break; 410 } 411 } 412 413 return result; 414 } 415 416 int main() { 417 int t; 418 cin >> t; 419 forn(tt, t) { 420 cin >> n; 421 diags.clear(); 422 dd.clear(); 423 segments = vector<seg>(n); 424 forn(i, n) { 425 seg s; 426 s.index = i; 427 cin >> s.a >> s.b >> s.m; 428 diags[s.a + s.b - s.m].push_back(s); 429 segments[i] = s; 430 } 431 int sum = 0; 432 for (auto p: diags) 433 sum += solve(p.second); 434 cout << sum << '\n'; 435 forn(i, n) 436 cout << dd[i].first << " " << dd[i].second << '\n'; 437 } 438 } 439 ```