codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![ ](/predownloaded/47/5c/475c116ddd6cc2ae0dc9cc348078f7dd5ccc40fd.png) ![ ](/predownloaded/f3/d3/f3d3c09c2f124b07d1d0b48d85c390d1f89474fa)
    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 ![ ](/predownloaded/1f/a4/1fa4d124e94f5b70e023c0ca1cb80a7b9c4771fc.jpg)
    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 ![ ](/predownloaded/26/ff/26ff71bd8d76e39cc0b8005109be649238dacf55.png)
    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 ![ ](/predownloaded/36/8c/368cbc850b403e4ae659ddb92c8ca716daf4657d.png)
    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!