1281.md (12057B)
1 Source: https://codeforces.com/blog/entry/72212 2 3 I hope you enjoyed the problems! Thanks to the onsite teams and coaches who gave feedback; I'm glad the reception was positive. 4 5 Interestingly, in the onsite ICPC round, while "Kirchhoff" got several accepted solutions, "Miss Punyverse" got no accepted submissions at all! It is the reverse here. (Kirchhoff even has a trickier output format in the onsite round compared to the version presented in Codeforces.) It seems the ICPC scoreboard really affects the results greatly; what the top few teams are working on influences what everyone else will be working on. 6 7 I am planning on releasing the full, untouched ICPC Manila 2019 problem set in the gym sometime in the future, so you can see which problems you missed. The Intergalactic Sliding Puzzle is *not* the hardest problem in the round! 8 9 [1281A - Suffix Three](/contest/1281/problem/A "Codeforces Round 607 (Div. 2)") 10 11 **Solution Sketch** 12 13 Tutorial is loading... 14 15 **Accepted Code** 16 17 ``` 18 for cas in range(int(input())): print({'o': "FILIPINO", 'a': "KOREAN", 'u': "JAPANESE"}[input()[-1]]) 19 ``` 20 21 Accepted Submission: [67015948](/contest/1281/submission/67015948 "Submission 67015948 by kevinsogo") 22 23 [1281B - Azamon Web Services](/contest/1281/problem/B "Codeforces Round 607 (Div. 2)") 24 25 **Solution Sketch** 26 27 Tutorial is loading... 28 29 **Accepted Code** 30 31 ``` 32 def solve(s, t): 33 mns = list(s) 34 for i in range(len(s)-2,-1,-1): mns[i] = min(mns[i], mns[i + 1]) 35 for i in range(len(s)): 36 if s[i] != mns[i]: 37 j = max(j for j, v in enumerate(s[i:], i) if v == mns[i]) 38 s = s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:] 39 break 40 return s if s < t else '---' 41 42 for cas in range(int(input())): 43 print(solve(*input().split())) 44 ``` 45 46 Accepted Submission: [67049609](/contest/1281/submission/67049609 "Submission 67049609 by kevinsogo") 47 48 [1281C - Cut and Paste](/contest/1281/problem/C "Codeforces Round 607 (Div. 2)") 49 50 **Solution Sketch** 51 52 Tutorial is loading... 53 54 **Accepted Code** 55 56 ``` 57 #include <bits/stdc++.h> 58 using namespace std; 59 using ll = long long; 60 constexpr ll mod = 1'000'000'007; //' 61 constexpr int N = 1111; 62 63 char _s[N]; 64 ll solve() { 65 int x; 66 scanf("%d%s", &x, _s); 67 ll ls = strlen(_s); 68 vector<char> s(_s, _s + ls); 69 for (int i = 1; i <= x; i++) { 70 int v = s[i - 1] - '1'; 71 if (s.size() < x) { 72 vector<char> sub(s.begin() + i, s.end()); 73 for (int it = 0; it < v; it++) s.insert(s.end(), sub.begin(), sub.end()); 74 } 75 ls = (ls + (ls - i) * v) % mod; 76 } 77 return ls; 78 } 79 80 int main() { 81 int z; 82 for (scanf("%d", &z); z--; printf("%lld\n", (solve() % mod + mod) % mod)); 83 } 84 ``` 85 86 Accepted Submission: [67016113](/contest/1280/submission/67016113 "Submission 67016113 by kevinsogo") 87 88 [1281D - Beingawesomeism](/contest/1281/problem/D "Codeforces Round 607 (Div. 2)") 89 90 **Solution Sketch** 91 92 Tutorial is loading... 93 94 **Accepted Code** 95 96 ``` 97 #include <bits/stdc++.h> 98 using namespace std; 99 100 int solve(int r, int c, vector<string> grid) { 101 vector<int> rows(r), cols(c); 102 int total = 0; 103 for (int i = 0; i < r; i++) { 104 for (int j = 0; j < c; j++) { 105 if (grid[i][j] == 'A') rows[i]++, cols[j]++, total++; 106 } 107 } 108 if (total == r * c) return 0; 109 if (total == 0) return -1; 110 111 if (rows[0] == c || rows.back() == c || cols[0] == r || cols.back() == r) return 1; 112 if (grid[0][0] == 'A' || grid[0].back() == 'A' || grid.back()[0] == 'A' || grid.back().back() == 'A') return 2; 113 if (*max_element(rows.begin(), rows.end()) == c || *max_element(cols.begin(), cols.end()) == r) return 2; 114 if (rows[0] || rows.back() || cols[0] || cols.back()) return 3; 115 return 4; 116 } 117 118 int main() { 119 int z; 120 for (cin >> z; z--;) { 121 int r, c; 122 cin >> r >> c; 123 vector<string> grid(r); 124 for (int i = 0; i < r; i++) cin >> grid[i]; 125 int res = solve(r, c, grid); 126 (~res ? cout << res : cout << "MORTAL") << '\n'; 127 } 128 } 129 ``` 130 131 Accepted Submission: [67016167](/contest/1280/submission/67016167 "Submission 67016167 by kevinsogo") 132 133 [1281E - Jeremy Bearimy](/contest/1281/problem/E "Codeforces Round 607 (Div. 2)") 134 135 **Solution Sketch** 136 137 Tutorial is loading... 138 139 **Accepted Code** 140 141 ``` 142 #include <bits/stdc++.h> 143 using namespace std; 144 using ll = long long; 145 146 void solve() { 147 int n; 148 cin >> n; 149 n <<= 1; 150 vector<vector<pair<int,ll>>> adj(n); 151 for (int i = 0; i < n - 1; i++) { 152 int a, b; ll c; 153 cin >> a >> b >> c; 154 a--, b--; 155 adj[a].emplace_back(b, c); 156 adj[b].emplace_back(a, c); 157 } 158 159 vector<int> parent(n, -1), que(1, 0); 160 vector<ll> parent_cost(n); 161 parent[0] = 0; 162 for (int f = 0; f < que.size(); f++) { 163 int i = que[f]; 164 for (auto [j, c]: adj[i]) { 165 if (parent[j] == -1) { 166 parent[j] = i; 167 parent_cost[j] = c; 168 que.push_back(j); 169 } 170 } 171 } 172 vector<int> size(n, 1); 173 ll mn = 0, mx = 0; 174 reverse(que.begin(), que.end()); 175 for (int i : que) { 176 size[parent[i]] += size[i]; 177 mx += parent_cost[i] * min(size[i], n - size[i]); 178 mn += parent_cost[i] * (size[i] & 1); 179 } 180 cout << mn << " " << mx << '\n'; 181 } 182 183 int main() { 184 ios_base::sync_with_stdio(false); 185 cin.tie(NULL); 186 int z; 187 for (cin >> z; z--; solve()); 188 } 189 ``` 190 191 Accepted Submission: [67020743](/contest/1280/submission/67020743 "Submission 67020743 by kevinsogo") 192 193 [1281F - Miss Punyverse](/contest/1281/problem/F "Codeforces Round 607 (Div. 2)") 194 195 **Solution Sketch** 196 197 Tutorial is loading... 198 199 **Accepted Code** 200 201 ``` 202 #include <bits/stdc++.h> 203 using namespace std; 204 using ll = long long; 205 206 struct Group { 207 int win; ll adv; 208 Group(int win = -1, ll adv = 0): win(win), adv(adv) {} 209 Group operator+(const Group& o) const { 210 return Group(win + o.win, adv + o.adv); 211 } 212 Group operator+() const { 213 return Group(win + (adv > 0)); 214 } 215 bool operator<(const Group& o) const { 216 return win < o.win || win == o.win && adv < o.adv; 217 } 218 }; 219 220 vector<Group> convolve(const vector<Group>& fa, const vector<Group>& fb) { 221 vector<Group> fi(fa.size() + fb.size()); 222 for (int a = 0; a < fa.size(); a++) { 223 for (int b = 0; b < fb.size(); b++) { 224 fi[a + b ] = max(fi[a + b ], fa[a] + fb[b]); 225 fi[a + b + 1] = max(fi[a + b + 1], fa[a] + +fb[b]); 226 } 227 } 228 return fi; 229 } 230 231 vector<vector<Group>> f; 232 vector<vector<int>> adj; 233 void convolve_tree(int i, int p = -1) { 234 for (int j : adj[i]) { 235 if (j == p) continue; 236 convolve_tree(j, i); 237 f[i] = convolve(f[i], f[j]); 238 } 239 } 240 241 int solve() { 242 int n, m; 243 scanf("%d%d", &n, &m); 244 f = vector<vector<Group>>(n, vector<Group>(1, Group(0))); 245 for (int i = 0, b; i < n; i++) { 246 scanf("%d", &b); 247 f[i][0].adv -= b; 248 } 249 for (int i = 0, w; i < n; i++) { 250 scanf("%d", &w); 251 f[i][0].adv += w; 252 } 253 adj = vector<vector<int>>(n); 254 for (int i = 1; i < n; i++) { 255 int x, y; 256 scanf("%d%d", &x, &y); 257 x--, y--; 258 adj[x].push_back(y); 259 adj[y].push_back(x); 260 } 261 convolve_tree(0); 262 return (+f[0][m - 1]).win; 263 } 264 265 int main() { 266 int z; 267 for (scanf("%d", &z); z--; printf("%d\n", solve())); 268 } 269 ``` 270 271 Accepted Submission: [67016189](/contest/1280/submission/67016189 "Submission 67016189 by kevinsogo") 272 273 [1280E - Kirchhoff's Current Loss](/contest/1280/problem/E "Codeforces Round 607 (Div. 1)") 274 275 **Solution Sketch** 276 277 Tutorial is loading... 278 279 **Accepted Code** 280 281 ``` 282 #include <bits/stdc++.h> 283 using namespace std; 284 using ll = long long; 285 const ll INF = 1LL << 60; 286 287 class Circuit { 288 public: 289 ll w = -1; 290 ll width() { 291 if (w == -1) compute_width(); 292 return w; 293 } 294 virtual void compute_width() {} 295 virtual void assign(ll value) {} 296 virtual ostream& write_to(ostream& os) const { return os; } 297 void assign_minimal(ll value) { assign(value * width()); } 298 friend ostream& operator<<(ostream& os, const Circuit& circuit); 299 }; 300 301 ostream& operator<<(ostream& os, const Circuit& circuit) { 302 return circuit.write_to(os); 303 } 304 305 class Resistor: public Circuit { 306 public: 307 ll value = -1; 308 Resistor() {} 309 void compute_width() override { 310 w = 1; 311 } 312 void assign(ll value) override { 313 this->value = value; 314 } 315 ostream& write_to(ostream& os) const override { 316 return os << ' ' << value; 317 } 318 }; 319 320 class Join: public Circuit { 321 public: 322 char typ; 323 vector<Circuit*> children; 324 Join() {} 325 void compute_width() override { 326 w = typ == 'S' ? INF : 0; 327 for (auto child: children) { 328 ll ww = child->width(); 329 w = typ == 'S' ? min(w, ww) : w + ww; 330 } 331 } 332 void assign(ll value) override { 333 for (auto child: children) { 334 if (typ == 'S') { 335 if (child->width() == width()) { 336 child->assign(value); 337 value = 0; 338 } else { 339 child->assign(0); 340 } 341 } else { 342 child->assign(value); 343 } 344 } 345 } 346 ostream& write_to(ostream& os) const override { 347 for (auto child: children) os << *child; 348 return os; 349 } 350 }; 351 352 class CircuitParser { 353 const string& s; 354 int i = 0; 355 CircuitParser(const string& s): s(s) {} 356 Circuit *parse() { 357 if (s[i++] == '(') { 358 Join *j = new Join(); 359 while (true) { 360 j->children.push_back(parse()); 361 if (s[i++] == ')') break; 362 j->typ = s[i++]; 363 i++; 364 } 365 return j; 366 } else { 367 return new Resistor(); 368 } 369 } 370 public: 371 static Circuit *parse(const string& s) { 372 return CircuitParser(s).parse(); 373 } 374 }; 375 376 void solve(ll a, const string& s) { 377 Circuit *c = CircuitParser::parse(s); 378 c->assign_minimal(a); 379 cout << "REVOLTING" << *c << '\n'; 380 } 381 382 int main() { 383 ios_base::sync_with_stdio(false); 384 cin.tie(NULL); 385 int z; 386 for (cin >> z; z--;) { 387 ll a; 388 string s; 389 cin >> a; 390 getline(cin, s); 391 assert(s[0] == ' '); 392 solve(a, s.substr(1)); 393 } 394 } 395 ``` 396 397 Accepted Submission: [67016199](/contest/1280/submission/67016199 "Submission 67016199 by kevinsogo") 398 399 [1280F - Intergalactic Sliding Puzzle](/contest/1280/problem/F "Codeforces Round 607 (Div. 1)") 400 401 **Solution Sketch** 402 403 Tutorial is loading... 404 405 **Accepted Code** 406 407 ``` 408 def solve(k, grid): 409 seek = *range(2*k + 2), *range(4*k + 1, 2*k + 1, -1) 410 flat = [seek[v] for v in grid[0] + grid[1][::-1] if v] 411 412 m = { 413 'L': 'l'*2*k + 'u' + 'r'*2*k + 'd', 414 'R': 'u' + 'l'*2*k + 'd' + 'r'*2*k, 415 'C': 'l'*k + 'u' + 'r'*k + 'd', 416 'D': 'CC' + 'R'*(2*k + 1) + 'CC' + 'R'*(2*k + 2), 417 'F': 'R'*(k - 1) + 'DD' + 'R'*(2*k + 1) + 'D' + 'L'*2*k + 'DD' + 'L'*k, 418 'G': 'FF', 419 } 420 421 [(i, j)] = [(i, j) for i in range(2) for j in range(2*k + 1) if grid[i][j] == 0] 422 st = 'r'*(2*k - j) + 'd'*(1 - i) 423 424 for v in range(2, 4*k + 2): 425 ct = flat.index(v) 426 427 if ct >= 2: 428 st += 'L'*(ct - 2) + 'GR'*(ct - 2) + 'G' 429 flat = flat[ct - 1: ct + 1] + flat[:ct - 1] + flat[ct + 1:] 430 431 if ct >= 1: 432 st += 'G' 433 flat = flat[1:3] + flat[:1] + flat[3:] 434 435 st += 'L' 436 flat = flat[1:] + flat[:1] 437 438 if flat[0] == 1: return st, m 439 440 def main(): 441 def get_line(): 442 return [0 if x == 'E' else int(x) for x in input().split()] 443 444 for cas in range(int(input())): 445 res = solve(int(input()), [get_line() for i in range(2)]) 446 if res is None: 447 print('SURGERY FAILED') 448 else: 449 print('SURGERY COMPLETE') 450 st, m = res 451 print(st) 452 for shortcut in m.items(): print(*shortcut) 453 print('DONE') 454 455 main() 456 ``` 457 458 Accepted Submission: [67026155](/contest/1280/submission/67026155 "Submission 67026155 by kevinsogo")