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 ```