codeforces-scrape

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

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 ![The trick.](/predownloaded/3e/a4/3ea40009fbca5c7b8771e0375d4c6f1f445294d2.png)
     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 ![figure 2](/predownloaded/bf/ea/bfea9f45a4eb2899372a00ff802f28d7a18cf980.png)
    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`.