codeforces-scrape

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

1952.md (12676B)


      1 Source: https://codeforces.com/blog/entry/127765
      2 
      3 Thank you for participating in our contest! We hope you enjoyed it.
      4 
      5 Please let us know what you thought of the problems by voting!
      6 
      7 [1952A - Are You a Robot, Again?](/contest/1952/problem/A "April Fools Day Contest 2024")
      8 
      9 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
     10 
     11 **Hint**
     12 
     13 Have you seen the "are you a robot" boxes on websites?
     14 
     15 **Solution**
     16 
     17 ## [1952A - Are You a Robot, Again?](/contest/1952/problem/A "April Fools Day Contest 2024")
     18 
     19 If you select all the squares with traffic lights and read the corresponding letters from left-to-right, top-to-bottom, you get the text "$\texttt{print safety}$". So all you need to do is print the word $\texttt{safety}$.
     20 
     21 **Feedback**
     22 
     23 * Based problem
     24 * Based problem
     25 * Based problem
     26 
     27 [1952B - Is it stated?](/contest/1952/problem/B "April Fools Day Contest 2024")
     28 
     29 Idea: [willy108](/profile/willy108 "Master willy108")
     30 
     31 **Hint**
     32 
     33 Can you interpret the question in the title another way?
     34 
     35 **Solution**
     36 
     37 ## [1952B - Is it stated?](/contest/1952/problem/B "April Fools Day Contest 2024")
     38 
     39 You just need to check if there is a substring $\texttt{it}$ in the string. (That is, the question is asking, "is $\texttt{it}$ stated?")
     40 
     41 **Feedback**
     42 
     43 * Based problem
     44 * Based problem
     45 * Based problem
     46 
     47 [1952C - They Have Fooled](/contest/1952/problem/C "April Fools Day Contest 2024")
     48 
     49 Idea: [AlperenT](/profile/AlperenT "Master AlperenT")
     50 
     51 **Hint 1**
     52 
     53 They have fooled? Who have fooled?
     54 
     55 **Hint 2**
     56 
     57 The image says April. Could it be about April Fools?
     58 
     59 **Hint 3**
     60 
     61 The problem has $n \leq 12$. Where did you see the number $12$ before?
     62 
     63 **Solution**
     64 
     65 ## [1952C - They Have Fooled](/contest/1952/problem/C "April Fools Day Contest 2024")
     66 
     67 Looking at the announcement blog, it can be seen that the first April Fools Day Contest was $12$ years ago.
     68 
     69 The problem asks for the problem count of the April Fools Day Contest that was $n$ years ago.
     70 
     71 The sample that has $n = 9$ is also given as a hint as there was not an April Fools Day Contest on $2015$.
     72 
     73 **Feedback**
     74 
     75 * Based problem
     76 * Based problem
     77 * Based problem
     78 
     79 [1952D - Are You a Procrastinator?](/contest/1952/problem/D "April Fools Day Contest 2024")
     80 
     81 Idea: [AlperenT](/profile/AlperenT "Master AlperenT")
     82 
     83 **Hint 1**
     84 
     85 Are you a procrastinator?
     86 
     87 **Hint 2**
     88 
     89 You should be.
     90 
     91 **Hint 3**
     92 
     93 What? The checker does not trust you after you say yes? How can you make it believe you?
     94 
     95 **Solution**
     96 
     97 ## [1952D - Are You a Procrastinator?](/contest/1952/problem/D "April Fools Day Contest 2024")
     98 
     99 The problem asks you if you are procrastinator or not. You should output "yes" (or any other confirmation word that the checker can understand) to solve the problem. However, it does not seem to be enough as the checker responds with "I have no reason to believe you."
    100 
    101 You should prove to the checker that you are a procrastinator. You can do this by submitting "yes" in the last $15$ mins of the contest.
    102 
    103 Furthermore, the checker can give different responses depending on your output. Feel free to share what funny responses you got (there are many of them).
    104 
    105 **Feedback**
    106 
    107 * Based problem
    108 * Based problem
    109 * Based problem
    110 
    111 [1952E - Sweep Line](/contest/1952/problem/E "April Fools Day Contest 2024")
    112 
    113 Idea: [AlperenT](/profile/AlperenT "Master AlperenT")
    114 
    115 **Hint 1**
    116 
    117 Almost everything in this problem is a hint.
    118 
    119 **Hint 2**
    120 
    121 The problem name is "Sweep Line". Does it sound familiar?
    122 
    123 **Hint 3**
    124 
    125 Look at the quote in the statement. When does a mistake force you to start all over again?
    126 
    127 **Hint 4**
    128 
    129 Why are the numbers in the note section are colored?
    130 
    131 **Hint 5**
    132 
    133 Why does the note section contain "I had to take a guess." and "I am literally going to explode."
    134 
    135 **Hint 6**
    136 
    137 Minesweeper. This is a slightly different version, since all cells are numbered. Why do the numbers only go up to $2$?
    138 
    139 **Solution**
    140 
    141 ## [1952E - Sweep Line](/contest/1952/problem/E "April Fools Day Contest 2024")
    142 
    143 The theme of the problem is [Minesweeper](https://w.wiki/5ZRi).
    144 
    145 In Minesweeper, the numbers represent the count of mines around them.
    146 
    147 The array given in the input represents a Minesweeper game that is only a line (hence the name **Sweep Line**). The problem asks you to output the number of possible mine placements that is consistent with the given array.
    148 
    149 Note that here each cell refers to the number of mines in the neighboring cells, but **not** including itself (since the input is only up to $2$).
    150 
    151 The modulo $20240401$ part is unnecessary as the answer can be at most $2$ (try to prove this).
    152 
    153 **Feedback**
    154 
    155 * Based problem
    156 * Based problem
    157 * Based problem
    158 
    159 [1952F - Grid](/contest/1952/problem/F "April Fools Day Contest 2024")
    160 
    161 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    162 
    163 **Hint 1**
    164 
    165 Can you convert a grid of 0s and 1s into a useful piece of data?
    166 
    167 **Hint 2**
    168 
    169 Look in the top-left, top-right, and bottom-left corners. What do you notice?
    170 
    171 **Hint 2.2**
    172 
    173 Namely, look at the the top-left, top-right, and bottom-left $7 \times 7$ subgrids. They form a pattern. Have you seen this pattern elsewhere? (It is well-known.)
    174 
    175 **Solution**
    176 
    177 ## [1952F - Grid](/contest/1952/problem/F "April Fools Day Contest 2024")
    178 
    179 Replace 0 with white and 1 with black to get this QR code:
    180 
    181 ![ ](/predownloaded/29/d6/29d61690013f7ec3b22fac22baf9aa764fc75204.png)
    182 
    183 Scanning it tells you that you need to find the $4 \times 4$ grid with the maximum sum.
    184 
    185 **Feedback**
    186 
    187 * Based problem
    188 * Based problem
    189 * Based problem
    190 
    191 [1952G - Mathematician Takeover](/contest/1952/problem/G "April Fools Day Contest 2024")
    192 
    193 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    194 
    195 **Hint 1**
    196 
    197 There is a function that has the same name but different definitions in math and computer science. What is it?
    198 
    199 **Hint 2**
    200 
    201 Try to fit a curve through the three points given in the problem. It can help you solve the previous question.
    202 
    203 **Solution**
    204 
    205 ## [1952G - Mathematician Takeover](/contest/1952/problem/G "April Fools Day Contest 2024")
    206 
    207 The problem is a joke about the function $\log$. For mathematicians, it means $\log_e$, but for computer scientists, it means $\log_2$. In particular, the samples all give the correct output for $\log_e(x)$, but we really want to output $\log_2(x)$.
    208 
    209 **Feedback**
    210 
    211 * Based problem
    212 * Based problem
    213 * Based problem
    214 
    215 [1952H - Palindrome](/contest/1952/problem/H "April Fools Day Contest 2024")
    216 
    217 Idea: [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9")
    218 
    219 **Hint 1**
    220 
    221 Why are there two examples when each one already has multiple test cases?
    222 
    223 **Hint 2**
    224 
    225 A change of perspective might help you solve the problem.
    226 
    227 **Solution**
    228 
    229 ## [1952H - Palindrome](/contest/1952/problem/H "April Fools Day Contest 2024")
    230 
    231 One obvious weird thing in the statement is that there are 2 sample tests despite the multi-test input format. This implies that the lines ("tests") in each input might not be independent tests and are related in some way.
    232 
    233 If we read very closely we might notice two weird things about the statement. First, instead of the usual "Each test case contains a line...", it says "The following t lines each contain...". This is because one line does not correspond to one test case. Another is the unusual definition of palindromes: "in both directions".
    234 
    235 This problem is solved by seeing it in a different direction. If we read the third and fourth columns, we may notice that they are palindromes — which read the same in both directions, up and down. The solution is to read $t$ strings, vertically, from the input and determine whether they are palindromes. Empty strings count as palindromes as you can see in sample 2.
    236 
    237 **Feedback**
    238 
    239 * Based problem
    240 * Based problem
    241 * Based problem
    242 
    243 [1952I - Dark Matter](/contest/1952/problem/I "April Fools Day Contest 2024")
    244 
    245 Idea: [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9")
    246 
    247 **Hint**
    248 
    249 Something looks off with the text (literally).
    250 
    251 **Solution**
    252 
    253 ## [1952I - Dark Matter](/contest/1952/problem/I "April Fools Day Contest 2024")
    254 
    255 If you stare at the PDF hard enough, you'll notice that some of the text looks curved. Given the hint about "gravitational lensing", it should be clear that this is not a coincidence.
    256 
    257 How can gravitational lensing distort text? If there's a lot of mass between you and the text, those matter can bend light going from text into your eyes, making straight text look curved. In addition, the meme image looks normal, implying such mass lies between the image and text (in other words, behind the image from your perspective). Here's a visualization of the configuration:
    258 
    259 ![ ](/predownloaded/4e/c4/4ec42886a7559ab2563c1ee78c426c218fd64fe7.png)
    260 
    261 Now let's do the difficult and technical part: finding the dark matter. To do this we need to first grab some PDF/vector graphics editor like LibreOffice or Inkscape. We can see a lot of random objects behind the image:
    262 
    263 ![ ](/predownloaded/51/5d/515d1efdc3be63c59429d36a1886ae0afe670785.png)
    264 
    265 These are probably the mass causing distorted text. Unfortunately, as the problem suggests, these objects are dark matter so are transparent because they don't interact with light. We can set their transparency to 0 (or opacity to max) and change their color to see them better:
    266 
    267 ![ ](/predownloaded/3e/44/3e44d184eff45c6ea2373e9db8ed0379fd2a3ace.png)
    268 
    269 Which gives the formula $(a^2 + b^2) + (a - b) + |a| \times 2b - (ab + 2)$. If we plug in $a$ and $b$ from the samples, we get $1$, which corresponds to the missing number in the image. Therefore the solution is to output $a + b + ((a^2 + b^2) + (a - b) + |a| \times 2b - (ab + 2))$.
    270 
    271 **Feedback**
    272 
    273 * Based problem
    274 * Based problem
    275 * Based problem
    276 
    277 [1952J - Help, what does it mean to be "Based"](/contest/1952/problem/J "April Fools Day Contest 2024")
    278 
    279 Idea: [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9")
    280 
    281 **Solution**
    282 
    283 ## [1952J - Help, what does it mean to be "Based"](/contest/1952/problem/J "April Fools Day Contest 2024")
    284 
    285 Update: You can find checker implementations [here](https://github.com/toxicpie/based-language).
    286 
    287 The recent April Fools contests all have problems related to mysterious languages. In this one, you are given several samples in a new, never been seen before constructed language, and your task is to learn it and solve a simple task with it. The idea of using internet slangs as a language was inspired by [this meme](https://twitter.com/Phantom_TheGame/status/1745935918832275881). The problem format is similar to some Linguistics Olympiad problems.
    288 
    289 **If you can't access the twitter post**
    290 
    291 ![screenshot of tweet](/predownloaded/a0/d3/a0d3a86bb4f31486cb5a4a707efc595b5d2abb61.png)
    292 
    293 This problem is rather straightforward: simply figure out what each line of code does, and try to combine known operations to solve the last task. Knowing the meaning of slangs might help in understanding them.
    294 
    295 In task 1, we learn 4 operations:
    296 
    297 1. `yoink a`: Input an integer `a`.
    298 2. `*slaps a on top of b*`: Add `a` to `b`.
    299 3. `yeet b`: Output the integer `b`.
    300 4. `go touch some grass`: Return/exit the program.
    301 
    302 In task 2 we learn:
    303 
    304 1. `bruh b is lowkey just 0`: Assign the variable `b` to 0.
    305 2. `rip this b fell off by a`: Subtract `a` from `b`.
    306 
    307 And the less obvious:
    308 
    309 1. `vibe check a ratios b`: Check if `a` is larger than `b`. If yes, execute the next line, otherwise don't.
    310 2. `simp for 7`: Goto line 7.
    311 
    312 In task 3 we learn new things:
    313 
    314 1. `yoink a`: Input an entire array `a`.
    315 2. Indexing operations: `a[0]`. We can also see that arrays are 0-indexed.
    316 
    317 These are enough to solve task 4. There are two simple approaches.
    318 
    319 * Sort the array and output $a[k-1]$. We may use bubble sort for easier implementation.
    320 
    321 ```
    322 yoink n
    323 yoink a
    324 bruh i is lowkey just n
    325 vibe check i ratios 1
    326 simp for 7
    327 simp for 22
    328 bruh j is lowkey just 1
    329 vibe check i ratios j
    330 simp for 11
    331 simp for 20
    332 bruh k is lowkey just j
    333 *slaps -1 on top of k*
    334 vibe check a[k] ratios a[j]
    335 simp for 18
    336 bruh tmp is lowkey just a[j]
    337 bruh a[j] is lowkey just a[k]
    338 bruh a[k] is lowkey just tmp
    339 *slaps 1 on top of j*
    340 simp for 8
    341 rip this i fell off by 1
    342 simp for 4
    343 yoink k
    344 rip this k fell off by 1
    345 yeet a[k]
    346 go touch some grass
    347 ```
    348 
    349 * Since the input integers are distinct, we can loop over each element to see whether exactly $k-1$ elements are smaller than it.
    350 
    351 ```
    352 yoink n
    353 yoink a
    354 yoink k
    355 bruh i is lowkey just 0
    356 bruh m is lowkey just 1
    357 bruh j is lowkey just 0
    358 vibe check n ratios j
    359 simp for 10
    360 simp for 13
    361 vibe check a[j] ratios a[i]
    362 *slaps 1 on top of m*
    363 simp for 19
    364 vibe check m ratios k
    365 simp for 21
    366 vibe check k ratios m
    367 simp for 21
    368 yeet a[i]
    369 go touch some grass
    370 *slaps 1 on top of j*
    371 simp for 7
    372 *slaps 1 on top of i*
    373 simp for 5
    374 ```
    375 
    376 **Feedback**
    377 
    378 * Based problem
    379 * Based problem
    380 * Based problem