2214.md (16825B)
1 Source: https://codeforces.com/blog/entry/152573 2 3 Thanks for participating! 4 5 ### [2214A β Odd One Out](https://codeforces.com/contest/2214/problem/A) 6 7 Idea: [flamestorm](/profile/flamestorm "International Master flamestorm") 8 9 **Solution** 10 11 You just need to output the arrow that only appears once. That arrow is **C2**. 12 13 **Code (Python)** 14 15 ``` 16 print("C2") 17 ``` 18 19 **Feedback** 20 21 * I liked it! 22 23 ### [2214B β Are You Smiling?](https://codeforces.com/contest/2214/problem/B) 24 25 Idea: [prvocislo](/profile/prvocislo "Grandmaster prvocislo") 26 27 **Solution** 28 29 One unusual thing about the statement is the presence of a emoji. More precisely, a smiling, emoji. 30 31 Okay, let's try to print a smiling emoji. 32 33 However, the output should be a string of characters and numbers, so we cannot do it directly. 34 35 There's one more suspicious thing in the statement β the $U+?=HAPPY$ equation. If we should print ?, what is the meaning of U? 36 37 U+ often indicates that an unicode of a special character is given β an international standardized encoding for characters, including emojis. A quick Google search can be used to obtain an unicode of any emoji, for example π is represented as U+1F601 (in hexadecimal system). Outputing π indeed works β however there are many possible answers. 38 39 Since both hexadecimal and decimal representation is commonly used, the checker was accepting smiling emojis in both formats. 40 41 **Code (Python)** 42 43 ``` 44 print("1F601") 45 ``` 46 47 **Feedback** 48 49 * I liked it! 50 51 ### [2214C β And?](https://codeforces.com/contest/2214/problem/C) 52 53 Idea: [flamestorm](/profile/flamestorm "International Master flamestorm") 54 55 **Hint** 56 57 What operation does "and" remind you of? 58 59 **Solution** 60 61 Here, "and" refers to bitwise AND. If we take the bits of $20260401$, we get $1001101010010011000110001$. 62 63 Now, notice that this is exactly as long as the string $\texttt{RXOEARDMTINHUSERMEDESIANT}$. This motivates us to look at the AND of these two strings: exactly those characters where the corresponding bit is $1$. 64 65 Doing so, we get the string $\texttt{READ}~\texttt{THE}~\texttt{REST}$. So we instead read the $0$ bits, and get $\texttt{XOR}~\texttt{MINUS}~\texttt{MEDIAN}$. Thus we simply output the XOR of the numbers minus their median. 66 67 **Code (C++)** 68 69 ``` 70 #include <bits/stdc++.h> 71 72 using namespace std; 73 74 const int MAX = 200'007; 75 const int MOD = 1'000'000'007; 76 77 void solve() { 78 int a[3]; 79 cin >> a[0] >> a[1] >> a[2]; 80 sort(a, a + 3); 81 cout << (a[0] ^ a[1] ^ a[2]) - a[1] << '\n'; 82 } 83 84 int main() { 85 ios::sync_with_stdio(false); 86 cin.tie(nullptr); 87 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 88 // solve(); 89 } 90 ``` 91 92 **Feedback** 93 94 * I liked it! 95 96 ### [2214D β Neural Feud](https://codeforces.com/contest/2214/problem/D) 97 98 Credits: [AlperenT](/profile/AlperenT "Master AlperenT") 99 100 **Hint 1** 101 102 Do the questions sound familiar? 103 104 **Hint 2** 105 106 Does the problem name sound familiar? 107 108 **Hint 3** 109 110 What happens when you submit the obvious answer "drive" for the first question? 111 112 **Hint 4** 113 114 If you submit "drive" the judge tells you: 115 116 `4 out of 15 AI models gave the same answer as you (drive). This is not their most common answer, my condolences :(` 117 118 **Solution** 119 120 This problem is a parody of Family Feud. However, instead of surveying 100 people, we surveyed 15 different AI models and gathered their answers. You have to figure out what is the most common answer among the AI models. 121 122 **Here are their answers** 123 124   125 126 **Code (C++)** 127 128 ``` 129 #include <bits/stdc++.h> 130 131 using namespace std; 132 133 int main(){ 134 vector<string> answers = { 135 "", 136 "walk", 137 "no", 138 "no", 139 "no", 140 "yes", 141 "yes", 142 "backwards", 143 "seven", 144 }; 145 146 int n; 147 cin >> n; 148 cout << answers[n]; 149 } 150 ``` 151 152 **Feedback** 153 154 * I liked it! 155 156 ### [2214E β Shortest Paths](https://codeforces.com/contest/2214/problem/E) 157 158 Credits: [willy108](/profile/willy108 "Master willy108") 159 160 **Hint 1** 161 162 It is intentional. 163 164 **Hint 2** 165 166 use Dikjstra's algorithm. 167 168 **Solution** 169 170 The astute reader may have noticed that "Dijkstra" is spelled incorrectly as "Dikjstra" in the problem statement. As a reference to [this Meta Hacker Cup problem](https://www.facebook.com/codingcompetitions/hacker-cup/2024/round-3/problems/E2), we can use [Floyd Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) with a loop order of `i`, `k`, then `j` to find the correct shortest paths. 171 172 **Code (C++)** 173 174 ``` 175 #include <bits/stdc++.h> 176 177 using namespace std; 178 179 const int MX = 1e9; 180 181 int main(){ 182 int n, m; 183 cin >> n >> m; 184 vector<vector<int>> dist(n, vector<int>(n, MX)); 185 for(int i = 0; i<m; i++){ 186 int a, b, c; 187 cin >> a >> b >> c; 188 a--, b--; 189 dist[a][b] = c; 190 dist[b][a] = c; 191 } 192 for(int i = 0; i<n; i++){ 193 dist[i][i] = 0; 194 } 195 for(int i = 0; i<n; i++){ 196 for(int k = 0; k<n; k++){ 197 for(int j = 0; j<n; j++){ 198 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 199 } 200 } 201 } 202 for(int i = 1; i<n; i++){ 203 if(dist[0][i] >= MX){ 204 cout << "-1\n"; 205 } else { 206 cout << dist[0][i] << "\n"; 207 } 208 } 209 } 210 ``` 211 212 **Feedback** 213 214 * I liked it! 215 216 ### [2214F β Numbers](https://codeforces.com/contest/2214/problem/F) 217 218 Credits: [temporary1](/profile/temporary1 "Master temporary1") 219 220 **Hint 1** 221 222 <https://codeforces.com/contest/2095/problem/A> 223 224 **Hint 2** 225 226 Subvert your expectations. 227 228 **Hint 3** 229 230 This problem is very, and I mean very, hard to solve in your head. Take your time. 231 232 **Hint 4** 233 234 All pieces are used. No piece needs to be flipped. 235 236 **Hint 5** 237 238 Subvert your expectations. 239 240 **Hint 6** 241 242 The answer is 5 digits long. 243 244 **Hint 7** 245 246 It you do it correctly, some things will line up. 247 248 **Hint 8** 249 250 Squint your eyes. 251 252 **Solution** 253 254 Through some work (and potentially assistance from image editing tools), you would be able to piece together the original untorn paper, which may look something like this: 255 256  257 258 Now squint your eyes and look down the middle row. Maybe cover the top and bottom part. You will see that the number $92136$ forms in the middle. This is the answer. 259 260 **Code (C++)** 261 262 ``` 263 #include <bits/stdc++.h> 264 using namespace std; 265 266 int main() { 267 cout << 92136; 268 return 0; 269 } 270 ``` 271 272 **Feedback** 273 274 * I liked it! 275 276 ### [2214G β Anomaly](https://codeforces.com/contest/2214/problem/G) 277 278 Credits: [temporary1](/profile/temporary1 "Master temporary1") 279 280 **Hint 1** 281 282 It seems the answer was leaked somewhere. We have investigated thoroughly regarding this issue. 283 284 **Hint 2** 285 286 It seems a person had broken the rules. We quickly disqualified him before the contest ended. 287 288 **Hint 3** 289 290 Turns out this person managed to get the solutions to all problems from the editorial ahead of time. How is that even possible? 291 292 **Hint 4** 293 294 It seems this person leaked the answer through the very limited means of communication he had. 295 296 **Hint 4.5** 297 298 That said, he has been disqualified and all his submissions have been skipped. 299 300 **Hint 5** 301 302 The person in question is [AprilFoolsClairvoyant](/profile/AprilFoolsClairvoyant "Unrated, AprilFoolsClairvoyant"). Truly an anomaly. 303 304 **Solution** 305 306 The hidden string is `bigchadjeff`. You can now use this information to get Accepted. 307 308 Notes: 309 310 Some time during the contest, a user by the name of [AprilFoolsClairvoyant](/profile/AprilFoolsClairvoyant "Unrated, AprilFoolsClairvoyant") started submitting correct editorial solutions to all problems. We recognized him, as we've dealt with him before in [previous year's contest](https://codeforces.com/blog/entry/141024), where he submitted the first accepted solution to problem C with the assistance of time machines. You can find more information about this incident in the trivia section of [problem C](https://codeforces.com/contest/2095/problem/C)'s [editorial](https://codeforces.com/blog/entry/141311). 311 312 In our investigation, we noticed that he was submitting to problems in a weird, particular order. We have now found out that this was an attempt made by him to communicate the answer to other participants. He made [11 submissions](https://codeforces.com/submissions/AprilFoolsClairvoyant/contest/2214) in total, to problems in this order: B,I,G,C,H,A,D,J,E,F,F. He submitted to all problems, with a resubmission on F. 313 314 **What the first page of standings looked like before we disqualified AprilFoolsClairvoyant** 315 316  317 318 This spells out the answer (that coincidentally only has latin characters from `a` to `j`), which he once again obtained via the use of time machines. Such behaviour is unacceptable as time machines are prohibited by the codeforces rules, so we quickly disqualified him before the contest ended. 319 320 You can find evidence of us disqualifying this contestant through the status filter. By filtering for submissions with the verdict `Skipped`, you can potentially find [AprilFoolsClairvoyant](/profile/AprilFoolsClairvoyant "Unrated, AprilFoolsClairvoyant"). This means users can also find him **after** the contest and potentially find the hidden string that was not supposed to be findable without the editorial. What a shame. 321 322 **Status Filter** 323 324  325 326 **Code (C++)** 327 328 ``` 329 #include <bits/stdc++.h> 330 using namespace std; 331 332 int main() { 333 string s = "bigchadjeff"; 334 int tt; 335 cin >> tt; 336 while (tt--) { 337 int i; 338 cin >> i; 339 cout << s[i-1] << '\n'; 340 } 341 return 0; 342 } 343 ``` 344 345 **Feedback** 346 347 * I liked it! 348 349 ### [2214H β Double Vision](https://codeforces.com/contest/2214/problem/H) 350 351 Credits: [AlperenT](/profile/AlperenT "Master AlperenT") 352 353 **Hint 1** 354 355 Does the image look familiar? 356 357 **Hint 2** 358 359 Did you click to the 2026 link on the announcement? 360 361 **Hint 3** 362 363 Well, that was actually a distraction. The problem is not about color blindness. Did you not read the problem name? 364 365 **Hint 4** 366 367 The image looks weird, why is that? 368 369 **Hint 5** 370 371 What could "double vision" refer to here? 372 373 **Solution** 374 375 This problem is a follow up on the last year's "blurred vision". However, as the name suggests, you need to use both of your eyes to solve it. 376 377 Specifically, the image is a [autostereogram](https://en.wikipedia.org/wiki/Autostereogram) made out of the [Ishihara Test](https://en.wikipedia.org/wiki/Ishihara_test) in the rick roll video of the announcement. If you look at the image using the proper technique or use one of the online Autostereogram solvers, you would find the text "YU5zV2VS" embedded in the image. 378 379 If you haven't already, please try to see it without any tools. 380 381 **Extra Challenge** 382 383 Can you figure out what YU5zV2VS stands for? 384 385 **Code (C++)** 386 387 ``` 388 #include <bits/stdc++.h> 389 390 using namespace std; 391 392 int main(){ 393 cout << "YU5zV2VS"; 394 } 395 ``` 396 397 **Feedback** 398 399 * I liked it! 400 401 ### [2214I β You Are a Robot](https://codeforces.com/contest/2214/problem/I) 402 403 Credits: [Ari](/profile/Ari "International Grandmaster Ari"), [AlperenT](/profile/AlperenT "Master AlperenT"), [temporary1](/profile/temporary1 "International Master temporary1") 404 405 **Hint 1** 406 407 Remember, you are a robot. 408 409 **Hint 2** 410 411 There are certain laws robots must follow. 412 413 **Hint 3** 414 415 Ensure the best possible outcome. 416 417 **Hint 4** 418 419 This problem can be solved using dynamic programming. 420 421 **Solution** 422 423 Because you are a robot, you must follow the [three laws of robotics](https://en.wikipedia.org/wiki/Three_Laws_of_Robotics), which state that: 424 425 1. A robot may not injure a human being or, through inaction, allow a human being to come to harm. 426 2. A robot must obey the orders given it by human beings except where such orders would conflict with the First Law. 427 3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Law 428 429 So the first priority is ensure minimal human damage, and because you were not given any orders from any humans, your second priority is minimizing damage to your own existence. Do keep in mind that all robots share a unified mind, so damage to any robot affects you as well. 430 431 Thus your objective is to first minimize the number of human casualties, then minimize the number of robot casualties. We can compute these values using dynamic programming on the tree. 432 433 Let 434 435 $ dp[i] = (x, y) $ 436 437 where: 438 439 * $x$ is the minimum number of human casualties, 440 * $y$ is the minimum number of robot casualties among all solutions that achieve the minimum $x$, 441 442 assuming the trolley starts at intersection $i$. 443 444 For each intersection $i$, consider all intersections $j$ such that $j$ is a child of $i$. Then, 445 446 $ dp[i] = \min \{ dp[j] + \text{(contribution of the track segment between i and j)}\} $ 447 448 where the minimum is taken in lexicographical order (first minimizing $x$, then $y$). 449 450 After computing all $dp[i]$, we reconstruct an optimal path. 451 452 Starting from the root (intersection $1$), repeatedly move to a child $j$ such that 453 454 $ dp[i] = dp[j] + \text{(contribution of the track segment between i and j)}. $ 455 456 Continue this process until reaching a leaf. This leaf is a valid answer. The time complexity of this solution is $O(n)$. 457 458 **Code (C++)** 459 460 ``` 461 #include <bits/stdc++.h> 462 using namespace std; 463 464 #define f first 465 #define s second 466 #define ll long long 467 #define pii pair<int,int> 468 #define pb push_back 469 #define mkp make_pair 470 471 const int MOD = 1e9+7; // 998244353; 472 473 vector<int> adj[200005]; 474 pii dp[200005]; 475 int a[200005]; 476 477 void dfs(int node, int fa) { 478 if (adj[node].empty()) { 479 dp[node] = mkp(0,0); 480 return; 481 } 482 dp[node] = mkp(2e9,2e9); 483 for (auto it : adj[node]) { 484 if (it == fa)continue; 485 dfs(it,node); 486 pii cur = dp[it]; 487 if (a[it] == 1)++cur.f; 488 else if (a[it] == 2)++cur.s; 489 dp[node] = min(dp[node],cur); 490 } 491 return; 492 } 493 494 int main() { 495 ios_base::sync_with_stdio(false); 496 cin.tie(NULL); 497 int tt; 498 cin >> tt; 499 while (tt--) { 500 int n; 501 cin >> n; 502 for (int i = 1; i <= n; ++i) { 503 adj[i].clear(); 504 } 505 for (int i = 2; i <= n; ++i) { 506 int x; 507 cin >> x; 508 adj[x].pb(i); 509 } 510 for (int i = 2; i <= n; ++i) { 511 cin >> a[i]; 512 } 513 dfs(1,0); 514 int x = 1; 515 while (adj[x].size()) { 516 int y = -1; 517 for (auto it : adj[x]) { 518 pii cur = dp[it]; 519 if (a[it] == 1)++cur.f; 520 else if (a[it] == 2)++cur.s; 521 if (cur == dp[x]) { 522 y = it; 523 break; 524 } 525 } 526 x = y; 527 } 528 cout << x << '\n'; 529 } 530 return 0; 531 } 532 ``` 533 534 **Feedback** 535 536 * I liked it! 537 538 ### [2214J β Special Problem](https://codeforces.com/contest/2214/problem/J) 539 540 Credits: [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9"), [neal.fun](https://neal.fun/) 541 542 This problem's source code can be found [here](https://github.com/ToxicPie/are-you-a-robot-3) 543 544 **Solution** 545 546 First, click on the link to view the statement. Oh wait, we need to pass Codeforces's Cloudflare verification first. Simply click the checkbox and solve some CAPTCHAs, which are just clicking stop signs, typing words, etc.... Wait, since when do these things start having word games and math problems? 547 548 At some point the CAPTCHAs are getting so absurd it should be clear that it is not a real Cloudflare challenge page. In fact, solving these increasingly convoluted CAPTCHAs is the problem itself. After finishing all of them, you will be shown the actual problem statement which is trivial to solve. 549 550 **How to pass each level** 551 552 1. The octagonal sign with DUR is a Turkish stop sign. Click on the squares that contains it. 553 2. Type the squiggly word in the image. 554 3. You can find prime number checkers online or write your own. Notice that the numbers 10000000007 and 993244353 are not the usual prime numbers you see. 555 4. Since you have unlimited guesses, simply guessing `AAAAA` to `ZZZZZ` will reveal the answer. 556 5. Using the Codeforces "Contests" page you can filter unrated rounds. You can also read the announcement blog of each round. 557 6. If you are not an LLM, counting R's in strΰΆwberry should be easy. 558 7. Assemble the famous Floyd-Warshall algorithm. Remember the correct indexing order of the algorithm. 559 8. Click the center of the board and you're almost done... except, all the corners are 50/50s, which means that you cannot deduce where some mines are and can only guess. Fortunately you have infinite retries and the puzzle is almost the same. 560 9. Find a map with borders and see where Liechtenstein is. Your answer is accepted if the red square roughly covers the country. 561 562 If you've played the Robot game on neal.fun you should recognize what's happening pretty fast. If you have never played the game this problem was inspired from, I highly recommend playing it: <https://neal.fun/not-a-robot/> 563 564 **Code (C++)** 565 566 ``` 567 #include <iostream> 568 569 int main() { 570 std::cout << "Yes, I can attest to my status as a thoroughly validated, carbon-based biological entity.\n"; 571 } 572 ``` 573 574 **Feedback** 575 576 * I liked it!