1979.md (14731B)
1 Source: https://codeforces.com/blog/entry/130213 2 3 Thank you for participating! 4 5 ## [1979A - Guess the Maximum](/contest/1979/problem/A "Codeforces Round 951 (Div. 2)") 6 7 **Solution** 8 9 Let $m$ be the maximum among the numbers $a_i, a_{i + 1},\ldots, a_j$. Notice that there always exists such $k$ that $i \le k \lt j$ and $a_k = m$ or $a_{k + 1} = m$. Therefore, we can assume that Bob always chooses the pair of numbers $p$ and $p + 1$ ($1 \le p \lt n$) as $i$ and $j$. 10 11 Therefore you need to consider the maximums in pairs of adjacent elements and take the minimum among them. Let $min$ be the found minimum, then it is obvious that the answer is equal to $min - 1$. 12 13 **Code** 14 15 ``` 16 #include <iostream> 17 using namespace std; 18 19 int main() { 20 int t; 21 cin >> t; 22 while (t--) { 23 int n; 24 cin >> n; 25 int a[n]; 26 for (int& i : a) { 27 cin >> i; 28 } 29 int mini = max(a[0], a[1]); 30 for (int i = 1; i < n - 1; i++) { 31 mini = min(mini, max(a[i], a[i + 1])); 32 } 33 cout << mini - 1 << "\n"; 34 } 35 } 36 ``` 37 38 ## [1979B - XOR Sequences](/contest/1979/problem/B "Codeforces Round 951 (Div. 2)") 39 40 **Hint** 41 42 Look at samples. 43 44 **Solution** 45 46 Consider two numbers $v$ and $u$ such that $x \oplus v = y \oplus u$. Then consider the numbers $x \oplus (v + 1)$ and $y \oplus (u + 1)$. Let's look at the last bit of $v$ and $u$. Possible scenarios: 47 48 * Both bits are equal to $0$ — adding one will change the bits at the same positions, therefore $x \oplus (v + 1) = y \oplus (u + 1)$; 49 * Both bits are equal to $1$ — adding one will change the bits at the same positions and also add one to the next bit, therefore we can similarly consider the next bit; 50 * Bits are different — adding one to the zero bit will only change one bit, while the subsequent bit of the other number will be changed. This means that $x \oplus (v + 1) \neq y \oplus (u + 1)$. 51 52 It is clear that we need to maximize the number of zeros in the maximum matching suffix of $u$ and $v$. Obviously, this number is equal to the maximum matching suffix of $x$ and $y$. Let $k$ be the length of the maximum matching suffix of $x$ and $y$, then the answer is $2^k$. 53 54 This can be calculated in $O(\log C)$ time for one test case, where $C$ is the limit on $x$ and $y$. 55 56 **Code** 57 58 ``` 59 #include <bits/stdc++.h> 60 using namespace std; 61 62 int main() { 63 int t; 64 cin >> t; 65 while (t--) { 66 int a, b; 67 cin >> a >> b; 68 69 for (int i = 0; i < 30; i++) { 70 if ((a & (1 << i)) != (b & (1 << i))) { 71 cout << (1ll << i) << "\n"; 72 break; 73 } 74 } 75 } 76 } 77 ``` 78 79 ## [1979C - Earning on Bets](/contest/1979/problem/C "Codeforces Round 951 (Div. 2)") 80 81 **Hint** 82 83 Try to come up with a condition for the existence of an answer. 84 85 **Solution** 86 87 Let $S$ be the total amount of coins placed on all possible outcomes. Then, if the coefficient for winning is $k_i$, we have to place **more** than $\frac{S}{k_i}$ on this outcome. 88 89 We can obtain the following inequality: 90 91 $\sum_{i = 1}^n \frac{S}{k_i} \lt S.$ 92 93 Dividing both sides by $S$, we obtain the necessary and sufficient condition for the existence of an answer: 94 95 $\sum_{i = 1}^n \frac{1}{k_i} \lt 1.$ 96 97 This check can be performed by reducing all fractions to a common denominator. Notice that the numerators of the reduced fractions correspond to the required bets on the outcomes. 98 99 **Code** 100 101 ``` 102 #include <bits/stdc++.h> 103 using namespace std; 104 105 #define int long long 106 107 int gcd(int a, int b) { 108 while (b != 0) { 109 int tmp = a % b; 110 a = b; 111 b = tmp; 112 } 113 return a; 114 } 115 int lcm(int a, int b) { 116 return a * b / gcd(a, b); 117 } 118 119 void solve() { 120 int n; 121 cin >> n; 122 123 vector <int> k(n); 124 for (int i = 0; i < n; i++) { 125 cin >> k[i]; 126 } 127 128 int z = 1; 129 for (int i = 0; i < n; i++) { 130 z = lcm(z, k[i]); 131 } 132 133 int suma = 0; 134 for (int i = 0; i < n; i++) { 135 suma += z / k[i]; 136 } 137 138 if (suma < z) { 139 for (int i = 0; i < n; i++) { 140 cout << z / k[i] << " "; 141 } 142 cout << "\n"; 143 } else { 144 cout << -1 << "\n"; 145 } 146 } 147 148 signed main() { 149 int t; 150 cin >> t; 151 while (t--) { 152 solve(); 153 } 154 } 155 ``` 156 157 ## [1979D - Fixing a Binary String](/contest/1979/problem/D "Codeforces Round 951 (Div. 2)") 158 159 **Solution** 160 161 Let's consider the block of characters at the end. Notice that their quantity cannot decrease. Let $x$ be the number of identical characters at the end; there are three possible cases: 162 163 * $x = k$ — it is enough to find any block of length greater than $k$ and separate a block of length $k$ from it; 164 * $x \gt k$ — obviously, there is no solution; 165 * $x \lt k$ — find a block of length $k - x$ or $2k - x$ and separate a block of length $k - x$ from it. 166 167 This solution works in $O(n)$, but it is not the only correct one. Your solution may differ significantly from the one proposed. 168 169 **Code** 170 171 ``` 172 #include <bits/stdc++.h> 173 using namespace std; 174 175 int main() { 176 int t; 177 cin >> t; 178 while (t--) { 179 int n, k; 180 cin >> n >> k; 181 182 string s; 183 cin >> s; 184 185 int x = 0; 186 for (int i = n - 1; i >= 0; i--) { 187 if (s[i] == s[n - 1]) { 188 x++; 189 } else { 190 break; 191 } 192 } 193 194 auto check = [&]() { 195 for (int i = 0; i < k; i++) { 196 if (s[i] != s[0]) return false; 197 } 198 for (int i = 0; i + k < n; i++) { 199 if (s[i] == s[i + k]) return false; 200 } 201 return true; 202 }; 203 204 auto operation = [&](int p) { 205 reverse(s.begin(), s.begin() + p); 206 s = s.substr(p, (int)s.size() - p) + s.substr(0, p); 207 if (check()) { 208 cout << p << "\n"; 209 } else { 210 cout << -1 << "\n"; 211 } 212 }; 213 214 if (x == k) { 215 int p = n; 216 for (int i = n - 1 - k; i >= 0; i--) { 217 if (s[i] == s[i + k]) { 218 p = i + 1; 219 break; 220 } 221 } 222 operation(p); 223 } else if (x > k) { 224 cout << -1 << "\n"; 225 } else { 226 bool was = false; 227 for (int i = 0; i < n; i++) { 228 if (s[i] != s.back()) continue; 229 int j = i; 230 while (j + 1 < n && s[i] == s[j + 1]) { 231 j++; 232 } 233 if (j - i + 1 + x == k) { 234 operation(j + 1); 235 was = true; 236 break; 237 } else if (j - i + 1 - k + x == k) { 238 operation(i + k - x); 239 was = true; 240 break; 241 } 242 i = j; 243 } 244 if (!was) { 245 operation(n); 246 } 247 } 248 } 249 } 250 ``` 251 252 ## [1979E - Manhattan Triangle](/contest/1979/problem/E "Codeforces Round 951 (Div. 2)") 253 254 **Hint** 255 256 In every Manhattan triangle there are two points such that $|x_1 - x_2| = |y_1 - y_2|$. 257 258 **Solution** 259 260 Note this fact: in every Manhattan triangle there are two points such that $|x_1 - x_2| = |y_1 - y_2|$. 261 262 Let's start with distributing all points with their $(x + y)$ value. 263 264 For each point $(x; y)$ find point $(x + d / 2; y - d / 2)$ using lower bound method in corresponding set. Then we have to find the third point: it can be in either $(x + y + d)$ or $(x + y - d)$ diagonal. Borders at $x$ coordinate for them are $[x + d / 2; x + d]$ and $[x - d / 2; x]$ — it can be found using the same lower bound method. 265 266 Then, distribute all points with $(x - y)$ value and do the same algorithm. 267 268 Total time complexity is $O(n \log n)$. 269 270 **Code** 271 272 ``` 273 #include <bits/stdc++.h> 274 using namespace std; 275 276 const int MAXC = 1e5; 277 const int MAXD = 4e5 + 10; 278 279 set <pair <int, int>> diag[MAXD]; 280 281 void solve() { 282 int n, d; 283 cin >> n >> d; 284 285 vector <int> x(n), y(n); 286 for (int i = 0; i < n; i++) { 287 cin >> x[i] >> y[i]; 288 x[i] += MAXC; 289 y[i] += MAXC; 290 } 291 292 bool found = false; 293 { 294 for (int i = 0; i < n; i++) { 295 diag[x[i] + y[i]].insert({x[i], i}); 296 } 297 for (int i = 0; i < n; i++) { 298 auto it1 = diag[x[i] + y[i]].lower_bound({x[i] + d / 2, -1}); 299 if (it1 == diag[x[i] + y[i]].end() || it1->first != x[i] + d / 2) continue; 300 if (x[i] + y[i] + d < MAXD) { 301 auto it2 = diag[x[i] + y[i] + d].lower_bound({x[i] + d / 2, -1}); 302 if (it2 != diag[x[i] + y[i] + d].end() && it2->first <= it1->first + d / 2) { 303 cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n"; 304 found = true; 305 break; 306 } 307 } 308 if (x[i] + y[i] - d >= 0) { 309 auto it2 = diag[x[i] + y[i] - d].lower_bound({x[i] - d / 2, -1}); 310 if (it2 != diag[x[i] + y[i] - d].end() && it2->first <= it1->first - d / 2) { 311 cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n"; 312 found = true; 313 break; 314 } 315 } 316 } 317 for (int i = 0; i < n; i++) { 318 diag[x[i] + y[i]].erase({x[i], i}); 319 } 320 } 321 if (!found) { 322 for (int i = 0; i < n; i++) { 323 y[i] -= 2 * MAXC; 324 diag[x[i] - y[i]].insert({x[i], i}); 325 } 326 for (int i = 0; i < n; i++) { 327 auto it1 = diag[x[i] - y[i]].lower_bound({x[i] + d / 2, -1}); 328 if (it1 == diag[x[i] - y[i]].end() || it1->first != x[i] + d / 2) continue; 329 if (x[i] - y[i] + d < MAXD) { 330 auto it2 = diag[x[i] - y[i] + d].lower_bound({x[i] + d / 2, -1}); 331 if (it2 != diag[x[i] - y[i] + d].end() && it2->first <= it1->first + d / 2) { 332 cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n"; 333 found = true; 334 break; 335 } 336 } 337 if (x[i] - y[i] - d >= 0) { 338 auto it2 = diag[x[i] - y[i] - d].lower_bound({x[i] - d / 2, -1}); 339 if (it2 != diag[x[i] - y[i] - d].end() && it2->first <= it1->first - d / 2) { 340 cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n"; 341 found = true; 342 break; 343 } 344 } 345 } 346 for (int i = 0; i < n; i++) { 347 diag[x[i] - y[i]].erase({x[i], i}); 348 } 349 } 350 if (!found) { 351 cout << "0 0 0\n"; 352 } 353 } 354 355 int main() { 356 int t; 357 cin >> t; 358 while (t--) { 359 solve(); 360 } 361 } 362 ``` 363 364 ## [1979F - Kostyanych's Theorem](/contest/1979/problem/F "Codeforces Round 951 (Div. 2)") 365 366 **Solution** 367 368 Let's consider the following recursive algorithm. We will store the Hamiltonian path as a double-ended queue, maintaining the start and end. 369 370 In case there are only $1$ or $2$ vertices left in the graph, the problem is solved trivially. 371 372 Suppose we know that the current graph has $n$ vertices, and there are **at most** $(n - 2)$ edges missing. Then the total number of edges in such a graph is at least 373 374 $\frac{n(n - 1)}{2} - (n - 2) = \frac{n^2 - 3n + 4}{2}.$ 375 376 Let all vertices in the graph have a degree of at most $(n - 3)$, then the total number of edges does not exceed 377 378 $\frac{n(n-3)}{2} = \frac{n^2 - 3n}{2},$ 379 380 which is less than the stated value. Hence, we conclude that there is **at least one** vertex with a degree greater than $(n - 3)$. 381 382 If there exists a vertex $v$ with a degree of $(n - 2)$, then it is sufficient to run our recursive algorithm for the remaining graph. Since $v$ is only not connected by an edge to one vertex, $v$ is connected either to the start or the end of the maintained path in the remaining graph. Thus, we can insert the vertex $v$ either at the beginning or at the end of the path. 383 384 Otherwise, let $u$ be the vertex with a degree of $(n - 1)$. There is at least one vertex $w$ with a degree not exceeding $(n - 3)$. Remove $u$ and $w$ from the graph. Notice that the number of edges in such a graph does not exceed 385 386 $\frac{n^2 - 3n + 4}{2} - (n - 1) - (n - 3) + 1 = \frac{n^2 - 7n + 14}{2}$ $\frac{n^2 - 7n + 14}{2} = \frac{n^2 - 5n + 6}{2} - \frac{2n - 8}{2}$ $\frac{n^2 - 5n + 6}{2} - \frac{2n - 8}{2} = \frac{(n - 2)(n - 3)}{2} - (n - 4)$ $\frac{(n - 2)(n - 3)}{2} - (n - 4) = \frac{(n - 2)((n - 2) - 1)}{2} - ((n - 2) - 2).$ 387 388 The invariant is preserved, so we can run the algorithm for the remaining graph. Then, we can arrange the vertices in the following order: $w$ — $u$ — $s$ — ..., where $s$ — the start of the Hamiltonian path in the remaining graph. 389 390 It remains to understand how to use queries. 391 392 Make a query $d = (n - 2)$. Let $u$ be the second number in the response to our query. If $u \neq 0$, the degree of vertex $v$ is $(n - 2)$. Run our recursive algorithm, and then compare the start and end of the obtained path with $u$. 393 394 Otherwise, if $u = 0$, it means the degree of vertex $v$ is $(n - 1)$. In this case, ask about any vertex with a low degree (this can be done with a query $d = 0$). Then simply arrange the vertices in the order mentioned above. 395 396 We will make no more than $n$ queries, and the final asymptotic will be $O(n)$. 397 398 **Code** 399 400 ``` 401 #include <bits/stdc++.h> 402 using namespace std; 403 404 pair <int, int> ask(int d) { 405 cout << "? " << d << endl; 406 int v, u; 407 cin >> v >> u; 408 return {v, u}; 409 } 410 411 pair <int, int> get(int n, vector <int>& nxt) { 412 if (n == 1) { 413 int v = ask(0).first; 414 return {v, v}; 415 } 416 if (n == 2) { 417 int u = ask(0).first; 418 int v = ask(0).first; 419 nxt[u] = v; 420 return {u, v}; 421 } 422 pair <int, int> t = ask(n - 2); 423 int v = t.first; 424 int ban = t.second; 425 if (ban != 0) { 426 pair <int, int> res = get(n - 1, nxt); 427 if (ban != res.first) { 428 nxt[v] = res.first; 429 return {v, res.second}; 430 } else { 431 nxt[res.second] = v; 432 return {res.first, v}; 433 } 434 } else { 435 int u = ask(0).first; 436 nxt[u] = v; 437 pair <int, int> res = get(n - 2, nxt); 438 nxt[v] = res.first; 439 return {u, res.second}; 440 } 441 } 442 443 void solve() { 444 int n; 445 cin >> n; 446 447 vector <int> nxt(n + 1, -1); 448 pair <int, int> ans = get(n, nxt); 449 450 int v = ans.first; 451 cout << "! "; 452 do { 453 cout << v << " "; 454 v = nxt[v]; 455 } while (v != -1); 456 cout << endl; 457 } 458 459 int main() { 460 int t; 461 cin >> t; 462 while (t--) { 463 solve(); 464 } 465 } 466 ```