codeforces-scrape

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

1992.md (13596B)


      1 Source: https://codeforces.com/blog/entry/131461
      2 
      3 Thanks [K1o0n](/profile/K1o0n "Specialist K1o0n") for being the mvp of this round.
      4 
      5 [1992A - Only Pluses](/contest/1992/problem/A "Codeforces Round 957 (Div. 3)")
      6 
      7 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
      8 
      9 Preparation: [K1o0n](/profile/K1o0n "Specialist K1o0n")
     10 
     11 **Tutorial**
     12 
     13 Let's prove why it's always better to add to the smallest number, let $a \le b \le c$, then compare the three expressions: $(a+1)\times b \times c$, $a \times (b+1) \times c$, and $a \times b \times (c+1)$. Remove the common part $a \times b \times c$, and we get: $b \times c$, $a \times c$, $a \times b$.
     14 
     15 $b \times c \ge a \times c$, since $a \le b$, similarly, $b \times c \ge a \times b$, since $a \le c$. Therefore, we can simply find the minimum $5$ times and add one to it. And thus, obtain the answer.
     16 
     17 Another, primitive approach is to simply iterate through what we will add to $a$, $b$, and $c$ with three loops.
     18 
     19 Since we can only add $5$ times, the time complexity of the solution is $O(1)$.
     20 
     21 **Solution (Python)**
     22 
     23 ```
     24 for _ in range(int(input())):
     25     arr = sorted(list(map(int,input().split())))
     26     for i in range(5):
     27         arr[0]+=1
     28         arr.sort()
     29     print(arr[0] * arr[1] * arr[2])
     30 ```
     31 
     32 [1992B - Angry Monk](/contest/1992/problem/B "Codeforces Round 957 (Div. 3)")
     33 
     34 Idea: [Noobish_Monk](/profile/Noobish_Monk "Master Noobish_Monk")
     35 
     36 Preparation: [K1o0n](/profile/K1o0n "Specialist K1o0n")
     37 
     38 **Tutorial**
     39 
     40 Let's say we want to connect two casseroles with lengths $x$ and $y$. We can disassemble one of them into pieces of length $1$ and then attach them to the casserole of size $y$. In total, we will perform $2x - 1$ operations. Since we want to connect $k$ pieces, at least $k - 1$ of them will have to be disassembled and then attached to something. If we attach something to a piece, there is no point in disassembling it, because to disassemble it, we will need to remove these pieces as well. Therefore, we want to choose a piece to which we will attach all the others. It will be optimal to choose a piece with the maximum size and attach everything to it. Thus, the answer is $2 \cdot (n - mx) - k + 1$, where $mx$ $-$ the length of the maximum piece.
     41 
     42 Solution complexity: $O(n)$.
     43 
     44 **Solution (C++)**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48 using namespace std;
     49 signed main() {
     50     int T;
     51     cin >> T;
     52     while (T--){
     53         int n, k;
     54         cin >> n >> k;
     55         vector<int> s(k);
     56         int m = -1;
     57         for (int i = 0; i < k; i++){
     58             cin >> s[i];
     59             m = max(m, s[i]);
     60         }
     61         cout << 2 * (n - m) - k + 1 << '\n';
     62     }
     63 }
     64 ```
     65 
     66 **Solution (Python)**
     67 
     68 ```
     69 for _ in range(int(input())):
     70     n,k = map(int,input().split())
     71     mx = max(map(int, input().split()))
     72     print((n - mx) * 2 - (k - 1))
     73 ```
     74 
     75 [1992C - Gorilla and Permutation](/contest/1992/problem/C "Codeforces Round 957 (Div. 3)")
     76 
     77 Idea: [K1o0n](/profile/K1o0n "Specialist K1o0n")
     78 
     79 Preparation: [K1o0n](/profile/K1o0n "Specialist K1o0n")
     80 
     81 **Tutorial**
     82 
     83 Let $p$ be some permutation. Let's look at the contribution of the number $p_i$ to the sum $\sum_{i=1}^n {f(i)}$. If it is less than $k$, the contribution is $0$, otherwise the contribution is $p_i \cdot (n - i + 1)$. Similarly, let's look at the contribution of $p_i$ to the sum $\sum_{i=1}^n {g(i)}$. If it is greater than $m$, the contribution is $0$, otherwise it is $p_i \cdot (n - i + 1)$. Since $m \lt k$, each number gives a contribution greater than $0$ in at most one sum. Therefore, it is advantageous to place numbers not less than $k$ at the beginning, and numbers not greater than $m$ at the end. Also, numbers not less than $k$ should be in descending order to maximize the sum of $f(i)$. Similarly, numbers not greater than $m$ should be in ascending order to minimize the sum of $g(i)$.
     84 
     85 For example, you can construct such a permutation: $n, n - 1, \ldots, k, m + 1, m + 2, \ldots, k - 1, 1, 2, \ldots, m$. It is easy to see that $\sum_{i=1}^n f(i)$ cannot be greater for any other permutation, and $\sum_{i=1}^n g(i)$ cannot be less for any other permutation, so our answer is optimal.
     86 
     87 Solution complexity: $O(n)$.
     88 
     89 **Solution (Python)**
     90 
     91 ```
     92 for _ in range(int(input()):
     93     n,m,k = map(int,input().split())
     94     print(*range(n,m,-1), *range(1,m))
     95 ```
     96 
     97 [1992D - Test of Love](/contest/1992/problem/D "Codeforces Round 957 (Div. 3)")
     98 
     99 Idea: [ArSarapkin](/profile/ArSarapkin "International Master ArSarapkin")
    100 
    101 Preparation: [K1o0n](/profile/K1o0n "Specialist K1o0n")
    102 
    103 **Tutorial**
    104 
    105 In this problem, there are two main solutions: dynamic programming and greedy algorithm.
    106 
    107 Dynamic programming solution: $dp_i$ $-$ the minimum number of meters that need to be swum to reach the $i$-th cell. The base case of the dynamic programming is $dp_0 = 0$. Then, the update rule is: \begin{equation*} dp_i = \text{minimum of} \begin{cases} dp_{i-1} + 1& \text{if } A_i = \text{'W'} \\ min(dp_j) & \text{for all } j, \text{where:} \max(0, i — m) \le j < i \text{ and } A_j = \text{'L'} \end{cases} \end{equation*} Solution complexity: $O(nm)$.
    108 
    109 Greedy algorithm solution: If we can jump, we want to jump to the shore if possible. If we can't, we want to jump to any log ahead to jump from it later. If we can't, we jump as far as possible to avoid crocodiles and swim as little as possible.
    110 
    111 Solution complexity: $O(n)$.
    112 
    113 **Solution (greedy)**
    114 
    115 ```
    116 def run() -> None:
    117     n,m,k = map(int, input().split())
    118     A = input()
    119     logs = [i for i in range(n) if A[i] == "L"]
    120     logs.append(n+1)
    121     i = -1
    122     next_log = 0
    123     while i < n-1:
    124         if m >= logs[next_log] - i:
    125             i = logs[next_log]
    126         else:
    127             i+=m
    128             if i > n-1:
    129                 print("YES")
    130                 return
    131             while i < n and i < logs[next_log]:
    132                 if A[i] != "C" and k > 0:
    133                     i+=1
    134                     k-=1
    135                 else:
    136                     print("NO")
    137                     return
    138         next_log +=1
    139     print("YES")
    140  
    141 for _ in range(int(input())):
    142     run()
    143 ```
    144 
    145 **Solution (DP)**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149 using namespace std;
    150 int main() {
    151     int t;
    152     cin >> t;
    153     while (t--) {
    154         int n, m, k; 
    155         cin >> n >> m >> k;
    156         string s;
    157         cin >> s;
    158         vector<int> dp(n + 2, -1);
    159         dp[0] = k;
    160         for (int i = 1; i <= n + 1; i++) {
    161             if (i != n + 1 && s[i - 1] == 'C') 
    162                 continue;
    163             for (int t = 1; t <= m; t++)
    164                 if (i - t >= 0 && (i - t == 0 || s[i - t - 1] == 'L'))
    165                     dp[i] = max(dp[i], dp[i - t]);
    166             if (i > 1 && s[i - 2] == 'W') 
    167                 dp[i] = max(dp[i], dp[i - 1] - 1);
    168         }
    169         if (dp[n + 1] >= 0) 
    170             cout << "YES\n";
    171         else 
    172             cout << "NO\n";
    173     }
    174 }
    175 ```
    176 
    177 [1992E - Novice's Mistake](/contest/1992/problem/E "Codeforces Round 957 (Div. 3)")
    178 
    179 Idea: [Noobish_Monk](/profile/Noobish_Monk "Master Noobish_Monk"), [K1o0n](/profile/K1o0n "Specialist K1o0n")
    180 
    181 Preparation: [K1o0n](/profile/K1o0n "Specialist K1o0n")
    182 
    183 **Tutorial**
    184 
    185 Notice that $n * a - b$ is strictly less than $10^6$, i.e., it has no more than $6$ digits. The number of characters in the strange calculation $n * a - b$ is equal to $|n| * a - b$, where $|n|$ is the number of digits in n. Let's iterate over the value of $a$, and then determine the boundaries $minB$ and $maxB$ for it, such that $|n| * a \gt maxB$ and $|n| * a - minB \le 6$. Then: \begin{cases} minB = |n| * a- 6 \\ maxB = |n| * a- 1 \end{cases} Let's iterate over all $b$ from $minB$ to $maxB$. To quickly check the strange calculation, let's only find its first $|n| * a - b$ digits. This way, we can find all suitable pairs $(a, b)$.
    186 
    187 Solution complexity: $O(a)$.
    188 
    189 **Solution (Python)**
    190 
    191 ```
    192 for _ in range(int(input())):
    193     n = int(input())
    194     sn = str(n)
    195     lenN = len(str(n))
    196     ans = []
    197     for a in range(1, 10001):
    198         minB = max(1, lenN * a - 5)
    199         maxB = lenN * a
    200         for b in range(minB, maxB):
    201             x = n * a - b
    202             y = 0
    203             for i in range(lenN * a - b):
    204                 y = y * 10 + int(sn[i % lenN])
    205             if x == y:
    206                 ans.append((a, b))
    207     print(len(ans))
    208     for p in ans:
    209         print(*p)
    210 ```
    211 
    212 [1992F - Valuable Cards](/contest/1992/problem/F "Codeforces Round 957 (Div. 3)")
    213 
    214 Idea: [Noobish_Monk](/profile/Noobish_Monk "Master Noobish_Monk")
    215 
    216 Preparation: [Noobish_Monk](/profile/Noobish_Monk "Master Noobish_Monk")
    217 
    218 **Tutorial**
    219 
    220 Let's consider the greedy algorithm ``take as long as you can''. Let's prove that it works. In any optimal division, if we take the first segment of non-maximum length, we will not violate the criteria if we transfer one element from the second segment to the first. Therefore, the given greedy algorithm is correct.
    221 
    222 Now let's figure out how to quickly understand if the segment can be extended. First, find all divisors of the number $x$. If the number $a_i$ is not a divisor of it, then it cannot be included in any set of numbers whose product is equal to $x$, so we can simply add it to the segment. If $a_i$ is a divisor, we need to somehow learn to understand whether it, in combination with some other divisors, gives the number $x$ on the segment. We will maintain a set of divisors that are products of some numbers in the segment. To update the set when adding $a_i$, we will go through all the divisors of this set and for each divisor $d$ add $d \cdot a_i$ to the set. If we added the number $x$ to the set, $a_i$ will already be in the next segment and we need to clear the set.
    223 
    224 P. S.: About implementation details and runtime. If you maintain the set in a set structure, then we get a runtime of $O(n \cdot d(x) \cdot \log(d(x)))$, where $d(x)$ is the number of divisors of $x$. Instead of a set, you can use, for example, a global array $used$ of size $10^5 + 1$, as well as maintain a vector of reachable divisors. Using these structures, you can achieve a runtime of $O(n \cdot d(x))$.
    225 
    226 **Solution (C++)**
    227 
    228 ```
    229 #include <iostream>
    230 #include <vector>
    231 
    232 using namespace std;
    233 
    234 const int A = 1e6 + 1;
    235 bool used[A];
    236 bool divs[A];
    237 
    238 void solve() {
    239 	int n, x;
    240 	cin >> n >> x;
    241 	vector<int> a(n);
    242 	vector<int> vecDivs;
    243 	for (int d = 1; d * d <= x; d++) {
    244 		if (x % d == 0) {
    245 			divs[d] = true;
    246 			vecDivs.push_back(d);
    247 			if (d * d < x) {
    248 			    vecDivs.push_back(x / d);
    249 				divs[x / d] = true;
    250 			}
    251 		}
    252 	}
    253 	for (int i = 0; i < n; i++)
    254 		cin >> a[i];
    255 	int ans = 1;
    256 	used[1] = true;
    257 	vector<int> cur{ 1 };
    258 	for (int i = 0; i < n; i++) {
    259 		if (!divs[a[i]])
    260 			continue;
    261 		vector<int> ncur;
    262 		bool ok = true;
    263 		for (int d : cur)
    264 			if (1ll * d * a[i] <= x && divs[d * a[i]] && !used[d * a[i]]) {
    265 				ncur.push_back(d * a[i]);
    266 				used[d * a[i]] = true;
    267 				if (d * a[i] == x)
    268 					ok = false;
    269 			}
    270 		for (int d : ncur)
    271 			cur.push_back(d);
    272 		if (!ok) {
    273 			ans++;
    274 			for (int d : cur)
    275 				used[d] = false;
    276 			used[1] = true;
    277 			used[a[i]] = true;
    278 			cur = vector<int>{ 1, a[i] };
    279 		}
    280 	}
    281 	for (int d : vecDivs) {
    282 	    divs[d] = false;
    283 	    used[d] = false;
    284 	}
    285 	cout << ans << '\n';
    286 }
    287 
    288 signed main() {
    289     int T;
    290     cin >> T;
    291     while (T--)
    292 	    solve();
    293 	return 0;
    294 }
    295 ```
    296 
    297 [1992G - Ultra-Meow](/contest/1992/problem/G "Codeforces Round 957 (Div. 3)")
    298 
    299 Idea: [Noobish_Monk](/profile/Noobish_Monk "Master Noobish_Monk"), [K1o0n](/profile/K1o0n "Specialist K1o0n")
    300 
    301 Preparation: [K1o0n](/profile/K1o0n "Specialist K1o0n")
    302 
    303 **Tutorial**
    304 
    305 We will iterate over the size of the set $k$ and its $\text{MEOW}$, $m$. If $2k \geqslant n$, then the set $x$ will fill all the remaining numbers up to $n$, and there may still be some larger than $n$ in it, so the $MEOW$ of all such sets will be $2k+1$, and there will be a total of $C(n, k)$ such sets for each $k$. If $2k \lt n$, $m$ lies in the interval from $k+1$ to $2k+1$. Notice that there can be exactly $m - 1 - k$ numbers before $m$, and correspondingly $2k + 1 - m$ numbers to the right of $m$, so the answer needs to be added with $C_{m - 1}^{m - 1 - k} \cdot C_{n - m}^{2k + 1 - m} \cdot m$.
    306 
    307 Asymptotic complexity of the solution: $O(n^2)$.
    308 
    309 **Solution (C++)**
    310 
    311 ```
    312 #include <iostream>
    313 
    314 using namespace std;
    315 
    316 const int mod = 1e9 + 7;
    317 
    318 int add(int a, int b) {
    319     if (a + b >= mod)
    320         return a + b - mod;
    321     return a + b;
    322 }
    323 
    324 int sub(int a, int b) {
    325     if (a < b)
    326         return a + mod - b;
    327     return a - b;
    328 }
    329 
    330 int mul(int a, int b) {
    331     return (int)((1ll * a * b) % mod);
    332 }
    333 
    334 int binpow(int a, int pw) {
    335     int b = 1;
    336     while (pw) {
    337         if (pw & 1)
    338             b = mul(b, a);
    339         a = mul(a, a);
    340         pw >>= 1;
    341     }
    342     return b;
    343 }
    344 
    345 int inv(int a) {
    346     return binpow(a, mod - 2);
    347 }
    348 
    349 const int N = 15000;
    350 int f[N], r[N];
    351 
    352 void precalc() {
    353     f[0] = 1;
    354     for (int i = 1; i < N; i++)
    355         f[i] = mul(f[i - 1], i);
    356     r[N - 1] = inv(f[N - 1]);
    357     for (int i = N - 2; i > -1; i--)
    358         r[i] = mul(r[i + 1], i + 1);
    359 }
    360 
    361 int C(int n, int k) {
    362     if (n < 0 || k < 0 || n < k)
    363         return 0;
    364     return mul(f[n], mul(r[k], r[n - k]));
    365 }
    366 
    367 inline void solve() {
    368     int n;
    369     cin >> n;
    370     int ans = 1;
    371     for (int k = 1; k <= n; k++) {
    372         if (2 * k >= n) {
    373             ans = add(ans, mul(2 * k + 1, C(n, k)));
    374             continue;
    375         }
    376         for (int m = k + 1; m <= 2 * k + 1; m++) {
    377             int c = mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m));
    378             ans = add(ans, mul(mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m)), m));
    379         }
    380     }
    381     cout << ans << '\n';
    382 }
    383 
    384 signed main() {
    385     int T = 1;
    386     cin >> T;
    387     precalc();
    388     while(T--)
    389         solve();
    390     return 0;
    391 }
    392 ```