2095.md (16270B)
1 Source: https://codeforces.com/blog/entry/141311 2 3 ### [2095A — Piecing It Together](https://codeforces.com/contest/2095/problem/A) 4 5 Credits: [flamestorm](/profile/flamestorm "Master flamestorm") 6 7 **Solution** 8 9 If you complete the puzzle, you will get a line of Python code reading $\texttt{print("puzzling")}$. To solve the problem, you just need to print $\texttt{puzzling}$. 10 11 **Code (C++)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 void solve() { 19 cout << "puzzling\n"; 20 } 21 22 int main() { 23 ios::sync_with_stdio(false); 24 cin.tie(nullptr); 25 solve(); 26 } 27 ``` 28 29 **Code (Python)** 30 31 ``` 32 print("puzzling") 33 ``` 34 35 ### [2095B — Plinko](https://codeforces.com/contest/2095/problem/B) 36 37 Credits: [AlperenT](/profile/AlperenT "Master AlperenT") 38 39 **Solution** 40 41 In this problem you need to drop a ball from a column of your choosing and get it to the green area. 42 43 With simple analysis (similar to Pascal's triangle), one can notice that best chance of winning is by dropping the ball from column $0$ or $16$ where you get $\frac{1}{2}$ chance to win. This means expected number of plays to win $10$ times is $2^{10} = 1024$, which is a lot (technically though, it is $2^{9} = 512$ as the first game always wins for penalty reasons). 44 45 However, one can notice that the green area spans further than columns $0$ to $16$. This allows one to win simply by dropping the ball from any column outside that range. 46 47 If anyone got accepted by chance using columns $[0, 16]$, please write in comments. 48 49 Lastly, if you have not noticed already, [this](https://codeforces.com/blog/entry/141024?#comment-1260509) was a hint for this problem. 50 51 **Code (C++)** 52 53 ``` 54 #include <algorithm> 55 #include <bitset> 56 #include <cassert> 57 #include <chrono> 58 #include <cmath> 59 #include <deque> 60 #include <iomanip> 61 #include <iostream> 62 #include <map> 63 #include <queue> 64 #include <random> 65 #include <set> 66 #include <string> 67 #include <vector> 68 typedef long long ll; 69 typedef long double ld; 70 using namespace std; 71 72 int main() 73 { 74 ios::sync_with_stdio(false); 75 cin.tie(0); 76 cout << "-10000\n"; 77 return 0; 78 } 79 ``` 80 81 ### [2095C — Would It Be Unrated?](https://codeforces.com/contest/2095/problem/C) 82 83 Credits: [prvocislo](/profile/prvocislo "Grandmaster prvocislo") 84 85 **Solution** 86 87 To solve this problem, you just need to do what the task asks — output the number of tests in this problem. 88 89 How do you do that? Well, if nobody has gotten accepted yet, there is not much you can do besides guess the answer through brute force. 90 91 However, you can just wait for someone else to do this tedious work for you. As soon as there is at least one accepted submission, you can use a trick: 92 93  94 95 This box on the status page will let you filter for submissions based on their failing test. If a submission got accepted, then it will show up if you query any number, as long as that number doesn't exceed the number of tests. This means that you can use this to binary search on the answer — keep cutting down the search space until you find the largest value that still shows at least one accepted submission. 96 97 Another way to get a reasonable estimate of the number of testcases are to watch as someone's accepted submission gets judged (`running on test x`), or to look at how many tries it took people to get accepted (assuming they start guessing from $1$, it should be around $140$). 98 99 Trivia: By writing `print(143)` in Python (or an equivalent in another language), you can solve both problems B and C in just $10$ characters! 100 101 Trivia 2: Some time during contest, a mysterious contestant [AprilFoolsClairvoyant](/profile/AprilFoolsClairvoyant "Unrated, AprilFoolsClairvoyant") from the future submitted the first accepted. Such behaviour is unacceptable as time machines are prohibited by the codeforces rules, so we quickly disqualified him. 102 103 **Code (Python)** 104 105 ``` 106 print(143) 107 ``` 108 109 ### [2095D — Where Am I?](https://codeforces.com/contest/2095/problem/D) 110 111 Credits: [AlperenT](/profile/AlperenT "Master AlperenT"), [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9") 112 113 **Solution** 114 115 In this problem, as can be understood from the name "Where am I?", you need to find the location of the photo. 116 117 From the output style (two real numbers, first in $[-90, 90]$ and second in $[-180, 180]$), we can deduce that the problem is asking for the latitude and the longitude of the location. Given an answer, the checker returns the distance (using Haversine formula) to the actual location and accepts an answer if it is closer than 100 meters. 118 119 Easiest way to solve this problem is to just examine the photo. The first obvious thing is the "New York" sign. Do not be fooled though, the location is not in New York. A closer examination allows us to see the "Las Vegas" sign and a quick google search gives us the "New York-New York Hotel & Casino" in Las Vegas. 120 121 Knowing this and analyzing the angle of the photo we can find the exact location using street view on Google Maps (although any other map should be fine). 122 123 This gives us the coordinates $36.104300, -115.172835$, which should give accepted (however any location nearby by 100 meters is accepted as to not cause annoyance.) 124 125 Additionally, it is possible to solve this problem with different methods without even looking at the photo as the checker returns the distance. Feel free to write your ideas in the comments and we can add them here. 126 127 **Code (C++)** 128 129 ``` 130 #include <bits/stdc++.h> 131 132 using namespace std; 133 134 int main(){ 135 cout << "36.104300 -115.172835"; 136 } 137 ``` 138 139 ### [2095E — Pair Count](https://codeforces.com/contest/2095/problem/E) 140 141 Credits: [temporary1](/profile/temporary1 "Master temporary1") 142 143 **Solution** 144 145 If you click on the link to the [bitwise XOR operation](https://word.rodeo/?utm_source=share#cvMcraT7fZ6Yj3T3fwWbp8jppto8Pan9HXzC5fWYjPCCvqUMqseEkRFkzttufIM=), you will actually be taken to a Wordle. Solving it will give you the answer $\texttt{MULTIPLY}$ (Since you can submit non-English words, and you have infinite tries (The page actually only allows 6 tries, but you can get around this by revisiting the page in incognito mode), the solution is actually relatively straightforward — you can find all the letters and where they appear by submitting strings each consisting of the same letter, then just combine all the guesses.). Thus $\oplus$ actually denotes the multiply operation. 146 147 So the solution is actually to find the number pairs of indexes $(i, j)$ for which $a_i^3 a_j^3 \equiv k \bmod p$. We can do this in $\mathcal{O}(n \log n + n \log p)$ time if we go from left to right and, for each $j$, count the number of $i$ such that $a_i^3 \equiv k a_j^{-3} \bmod p$ by keeping a map storing how frequent each $a_j^3$ was so far. 148 149 Note that there is an edge case when $k = 0$ which you should handle separately. 150 151 **Code (C++)** 152 153 ``` 154 #include <bits/stdc++.h> 155 using namespace std; 156 157 #define ll long long 158 159 int a[300005]; 160 161 ll power(ll x, int n, int p) { 162 x %= p; 163 ll res = 1; 164 while (n) { 165 if (n&1)res = (res*x)%p; 166 x = (x*x)%p; 167 n >>= 1; 168 } 169 return res; 170 } 171 172 int main() { 173 ios_base::sync_with_stdio(false); 174 cin.tie(NULL); 175 int n, p, k; 176 cin >> n >> p >> k; 177 for (int i = 1; i <= n; ++i) { 178 cin >> a[i]; 179 } 180 if (k == 0) { 181 cout << (*min_element(a+1,a+n+1) == 0 ? n-1 : 0) << '\n'; 182 return 0; 183 } 184 map<int,int> mp; 185 ll ans = 0; 186 for (int i = 1; i <= n; ++i) { 187 if (a[i] == 0)continue; 188 int x = power(a[i],3,p); 189 int inv = power(x,p-2,p); 190 ans += mp[(k*(ll)inv)%p]; 191 ++mp[x]; 192 } 193 cout << ans << '\n'; 194 return 0; 195 } 196 ``` 197 198 ### [2095F — ⅓ оf а Рrоblеm](https://codeforces.com/contest/2095/problem/F) 199 200 Credits: [flamestorm](/profile/flamestorm "Master flamestorm") 201 202 **Solution** 203 204 $\frac{1}{3}$ of the problem is in the English statement, and the other $\frac{2}{3}$ is in the Russian statement. (This is hinted because the title of the problem in English has some Cyrillic characters, and the title of the problem in Russian has some Latin characters. These characters look identical, but if you search the text up, you'll notice the results are quite strange — because some of the characters are in a different script!) 205 206 Combining them, noting that the Russian part should go first to make sense, gives the expression $12a + 14ab + |a - b| + (a - 3b) b + 2$, which is what you should compute. 207 208 **Code (Python)** 209 210 ``` 211 print((lambda a, b: 12*a + 14*a*b + abs(a - b) + (a - 3*b) * b + 2)(*map(int, input().split()))) 212 ``` 213 214 ### [2095G — Definitely a Geometry Problem](https://codeforces.com/contest/2095/problem/G) 215 216 Credits: [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9") 217 218 **Solution** 219 220 No three slimes lie on the same circle, so in fact all of them lie on the same line. 221 222 This means that you only need to sort the slimes $s_1, \dots, s_n$, and find the smallest diameter $d := \min_{1 \leq i \leq n-k+1} \text{dist}(s_i, s_{i+k-1})$. Then we just need to output $\pi \frac{d^2}{4}$. 223 224 **Code (Haskell)** 225 226 ``` 227 import Data.List (sort) 228 229 dist :: [Int] -> [Int] -> Double 230 dist [x1, y1] [x2, y2] = hypot (fromIntegral (x1 - x2)) (fromIntegral (y1 - y2)) 231 where hypot x y = sqrt (x * x + y * y) 232 233 solve :: Int -> [[Int]] -> Double 234 solve k points = min_r * min_r * pi 235 where 236 min_d = minimum $ zipWith dist points (drop (k - 1) points) 237 min_r = min_d / 2 238 239 main :: IO () 240 main = do 241 [_n, k] <- (map read . words) <$> getLine 242 points <- (map (map read . words) . lines) <$> getContents 243 print $ solve k (sort points) 244 ``` 245 246 ### [2095H — Blurry Vision](https://codeforces.com/contest/2095/problem/H) 247 248 Credits: [AlperenT](/profile/AlperenT "Master AlperenT") 249 250 **Solution** 251 252 Tutorial is loading... 253 254 **Code (Python)** 255 256 ``` 257 import cv2 258 import numpy as np 259 from scipy.signal import wiener 260 261 def gaussian_kernel(size, sigma): 262 k = cv2.getGaussianKernel(size, sigma) 263 kernel = np.outer(k, k) 264 return kernel 265 266 def wiener_deconvolution(blurred, kernel, noise_power=0.000005): 267 kernel /= np.sum(kernel) 268 269 img_fft = np.fft.fft2(blurred) 270 kernel_fft = np.fft.fft2(kernel, s=blurred.shape) 271 272 kernel_fft_conj = np.conj(kernel_fft) 273 denominator = kernel_fft * kernel_fft_conj + noise_power 274 result_fft = (img_fft * kernel_fft_conj) / denominator 275 276 result = np.fft.ifft2(result_fft).real 277 return np.clip(result, 0, 255).astype(np.uint8) 278 279 def deblur_image(path, kernel_size, sigma): 280 blurred = cv2.imread(path, cv2.IMREAD_GRAYSCALE) 281 282 kernel = gaussian_kernel(kernel_size, sigma) 283 deblurred = wiener_deconvolution(blurred, kernel) 284 285 cv2.imwrite("deblurred.png", deblurred) 286 287 deblur_image("blurred.png", 25, 7) 288 ``` 289 290 ### [2095I — Mysterious Script](https://codeforces.com/contest/2095/problem/I) 291 292 Credits: [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9") 293 294 **Solution** 295 296 The Balikons use base-9 numbers. This can be easily seen from the very important Figure 1 which clearly shows that the species has 9 fingers. 297 298 Now we need to know how to read the mysterious script. Except weird diagonal attachments which work as word ending markers, all characters are formed by horizontal and vertical strokes. In fact, each unique set of horizontal or vertical strokes has its own reading, and a character's reading is a defined by its horizontal and vertical components. For more information see Figure 2. 299 300 Observe that numbers are denoted by words that end with -s. We can see that characters used as digits all have a specific form: two long horizontal strokes and two long vertical strokes. Also, notice that each Balikon character resembles a 3x3 grid. Combining these and the base-9 fact, we can see that each digit character creates a square on the grid. From all digits in the example (1, 2, 3, 5, 6, 7) we can see that the numbers are ordered from top to bottom from left to right. 301 302  303 304 Figure 2: Balikon script 305 306 Now we know all digits in the Balikon script and how to read them. 307 308 **Code (Rust)** 309 310 ``` 311 mod balikon { 312 #[derive(Debug)] 313 pub struct BalikonNum(pub u64); 314 315 #[derive(Debug)] 316 pub struct ParseBalikonError; 317 318 impl BalikonNum { 319 const BASE: u64 = 9; 320 const DIGITS: [&str; Self::BASE as usize] = 321 ["la", "le", "lon", "sha", "she", "shon", "ta", "te", "ton"]; 322 323 fn parse_inner(s: &str) -> Option<u64> { 324 if s.is_empty() { 325 return Some(0); 326 } 327 (0..Self::BASE) 328 .filter_map(|i| { 329 Self::parse_inner(s.strip_suffix(Self::DIGITS[i as usize])?) 330 .map(|x| x * Self::BASE + i) 331 }) 332 .next() 333 } 334 } 335 336 impl<T> From<T> for BalikonNum 337 where 338 u64: From<T>, 339 { 340 fn from(value: T) -> Self { 341 Self(value.into()) 342 } 343 } 344 345 impl std::str::FromStr for BalikonNum { 346 type Err = ParseBalikonError; 347 348 fn from_str(s: &str) -> Result<Self, Self::Err> { 349 s.strip_suffix("s") 350 .and_then(Self::parse_inner) 351 .map(BalikonNum) 352 .ok_or(ParseBalikonError) 353 } 354 } 355 356 impl std::fmt::Display for BalikonNum { 357 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { 358 let mut n = self.0; 359 let mut digits = vec![]; 360 while n > 0 { 361 digits.push(n % Self::BASE); 362 n /= Self::BASE; 363 } 364 if digits.is_empty() { 365 digits.push(0); 366 } 367 for i in digits.into_iter().rev() { 368 write!(f, "{}", Self::DIGITS[i as usize])?; 369 } 370 write!(f, "s") 371 } 372 } 373 374 impl std::ops::Add for BalikonNum { 375 type Output = Self; 376 377 fn add(self, rhs: Self) -> Self::Output { 378 BalikonNum(self.0 + rhs.0) 379 } 380 } 381 } 382 383 use balikon::BalikonNum; 384 385 fn main() { 386 let mut input = String::new(); 387 std::io::stdin().read_line(&mut input).expect("what"); 388 389 let (a, b) = input.trim().split_once(' ').expect("parse error"); 390 let a: BalikonNum = a.parse().expect("parse error"); 391 let b: BalikonNum = b.parse().expect("parse error"); 392 println!("{}", a + b); 393 } 394 ``` 395 396 ### [2095J — Premiere at a Wrong Time](https://codeforces.com/contest/2095/problem/J) 397 398 Credits: [-1e11](/profile/-1e11 "Master -1e11"), [ToxicPie9](/profile/ToxicPie9 "Candidate Master ToxicPie9") 399 400 **Hint 1** 401 402 Look at the problem name. What can be premiered at a wrong time? 403 404 **Hint 2** 405 406 Yes, the video editorial. Where can you usually find an editorial? 407 408 **Hint 3** 409 410 Yes, the blog. In the last paragraphs of the blog, there's a link to the editorial. Click it and watch it carefully. 411 412 **Hint 4** 413 414 Is there anything unusual with this editorial? 415 416 **Hint 5** 417 418 You're right! Who puts musics while recording a video editorial? Also, Kent mentioned that "the songs we're using as the background music are in our favorite playlist; we enjoy them a lot, and you should definitely check them out!" Figure out what the songs are! 419 420 **Hint 6** 421 422 There's still something accessible. Can you find it? 423 424 **Hint 7** 425 426 Brilliant idea to steal the solution from the slide! The link is clearly visible in the video. You can manually copy the URL and read it at your end. 427 428 **Solution** 429 430 In Step 4, you can use Shazam, Google's hum-a-song search, or any other music identification tools, and find that the musics (in playing order) are: 431 432 * [What's The Problem? (by OSKI)](https://ncs.io/WTP) 433 * [23 (by Diamond Eyes)](https://ncs.io/D23) 434 * [Time (by OVSKY)](https://ncs.io/OTime) 435 * [51 (by THYKIER)](https://ncs.io/EPTheLimit) 436 * [A&B (by MADZI & ETikka)](https://ncs.io/aandb) 437 * [On (by Alisky)](https://ncs.io/AOn) 438 * [Code (by MANSHN)](https://ncs.io/Code) 439 * [Forces (by Jim Yosef)](https://ncs.io/forces) 440 441 Combining all these words, you'll get "what's the problem 23 time 51 A&B on code forces". As $23 \times 51 = 1173$, this is asking what 1173A and 1173B are on Codeforces. 442 443 If you read [the slide](https://hackmd.io/@cychien/april-fools-2025-editorial), you can find the input and output format of this problem. The input can be either `first` or `second`. Therefore, if the input is `first`, output `Nauuo and Votes`; otherwise, output `Nauuo and Chess`.