2036.md (14608B)
1 Source: https://codeforces.com/blog/entry/135849 2 3 [2036A - Quintomania](/contest/2036/problem/A "Codeforces Round 984 (Div. 3)") 4 5 Idea: [m3tr0](/profile/m3tr0 "Expert m3tr0") 6 7 **Tutorial** 8 9 If for all $i$ $(1 \leq i \leq n - 1)$ is true $|a_i - a_{i+1}| = 5$ or $|a_i - a_{i+1}| = 7$, the answer to the problem is “YES”, otherwise it is “NO”. 10 11 Complexity: $O(n)$ 12 13 **Solution (myav)** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 bool solve(){ 20 int n; 21 cin >> n; 22 vector<int>a(n); 23 for(int i = 0; i < n; i++) cin >> a[i]; 24 for(int i = 1; i < n; i++) { 25 if(abs(a[i] - a[i - 1]) != 5 && abs(a[i] - a[i - 1]) != 7) return false; 26 } 27 return true; 28 } 29 int main() { 30 int t; 31 cin >> t; 32 while(t--){ 33 cout << (solve() ? "YES" : "NO") << "\n"; 34 } 35 } 36 ``` 37 38 [2036B - Startup](/contest/2036/problem/B "Codeforces Round 984 (Div. 3)") 39 40 Idea: [Seny](/profile/Seny "Pupil Seny") 41 42 **Tutorial** 43 44 Let's create an array `brand_cost` of length $k$ and fill it so that `brand_cost[i]` stores the cost of all bottles of brand $i+1$. Then sort the array by non-growing and calculate the sum of its first `min(n, k)` elements, which will be the answer to the problem. 45 46 Complexity: $O(k \cdot \log k)$ 47 48 **Solution (Seny)** 49 50 ``` 51 #include <bits/stdc++.h> 52 using namespace std; 53 54 void solve() { 55 int n, k; 56 cin >> n >> k; 57 vector<int> brand_cost(k, 0); 58 for (int i = 0; i < k; i++) { 59 int b, c; 60 cin >> b >> c; 61 brand_cost[b - 1] += c; 62 } 63 sort(brand_cost.rbegin(), brand_cost.rend()); 64 long long ans = 0; 65 for (int i = 0; i < min(n, k); i++) { 66 ans += brand_cost[i]; 67 } 68 cout << ans << '\n'; 69 } 70 71 int main() { 72 int t; 73 cin >> t; 74 while (t--) { 75 solve(); 76 } 77 return 0; 78 } 79 ``` 80 81 [2036C - Anya and 1100](/contest/2036/problem/C "Codeforces Round 984 (Div. 3)") 82 83 Idea: [m3tr0](/profile/m3tr0 "Expert m3tr0") 84 85 **Hint** 86 87 With each query, to track the change in the presence of “1100” in a row, you don't have to go through the entire row — you can check just a few neighboring cells. 88 89 **Tutorial** 90 91 First, in a naive way, let's count $count$ — the number of times “1100” occurs in $s$. 92 93 Then for each of $q$ queries we will update $count$: consider the substring $s[\max(1, i - 3); \min(i + 3, n)]$ before changing $s_i$ and find $before$ — the number of times that “1100” occurs in it. Then update $s_i = v$ and similarly find $after$ — the number of times that “1100” occurs in $s[\max(1, i - 3); \min(i + 3, n)]$ after applying the query. 94 95 Thus, by doing $count = count + (after - before)$, we get the number of times that “1100” occurs in $s$ after the query is applied. If $count \gt 0$, the answer to the query is “YES”, otherwise it is “NO”. 96 97 Complexity: $O(|s| + q)$ 98 99 **Solution (m3tr0)** 100 101 ``` 102 #include <cstdio> 103 #include <cstring> 104 105 using namespace std; 106 typedef long long l; 107 108 char buf[1000000]; 109 l n; 110 111 bool check_1100(l i) { 112 if (i < 0) return false; 113 if (i >= n - 3) return false; 114 if (buf[i] == '1' && buf[i + 1] == '1' && buf[i + 2] == '0' && buf[i + 3] == '0') return true; 115 return false; 116 } 117 118 void solve() { 119 scanf("%s", buf); 120 n = strlen(buf); 121 l count = 0; 122 for (l i = 0; i < n; i++) 123 if (check_1100(i)) count++; 124 125 l q; scanf("%lld", &q); 126 while (q--) { 127 l i, v; scanf("%lld %lld", &i, &v); i--; 128 if (buf[i] != '0' + v) { 129 bool before = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i); 130 buf[i] = '0' + v; 131 bool after = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i); 132 count += after - before; 133 } 134 printf(count ? "YES\n" : "NO\n"); 135 } 136 } 137 138 int main() { 139 l t; scanf("%lld", &t); 140 while (t--) solve(); 141 } 142 ``` 143 144 [2036D - I Love 1543](/contest/2036/problem/D "Codeforces Round 984 (Div. 3)") 145 146 Idea: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Specialist eugenechka.boyko.2_0-0") 147 148 **Tutorial** 149 150 We will go through all layers of the carpet, adding to the answer the number of $1543$ records encountered on each layer. To do this, we can iterate over, for example, the top-left cells of each layer having the form $(i, i)$ for all $i$ in the range $[1, \frac{min(n, m)}{2}]$, and then traverse the layer with a naive algorithm, writing the encountered digits into some array. Then traverse the array and count the $1543$ occurrences in that layer. Also, when traversing the array, we should take into account the cyclic nature of the layer, remembering to check for possible occurrences of $1543$ containing a starting cell. 151 152 Complexity: $O(n \cdot m)$ 153 154 **Solution (m3tr0)** 155 156 ``` 157 #include <cstdio> 158 159 char a[1005][1005]; 160 char layer[4005]; 161 162 void solve() { 163 int n, m; scanf("%d %d", &n, &m); 164 for (int i = 0; i < n; ++i) scanf("%s", a[i]); 165 166 int count = 0; 167 for (int i = 0; (i + 1) * 2 <= n && (i + 1) * 2 <= m; ++i) { 168 int pos = 0; 169 for (int j = i; j < m - i; ++j) layer[pos++] = a[i][j]; 170 for (int j = i + 1; j < n - i - 1; ++j) layer[pos++] = a[j][m - i - 1]; 171 for (int j = m - i - 1; j >= i; --j) layer[pos++] = a[n - i - 1][j]; 172 for (int j = n - i - 2; j >= i + 1; --j) layer[pos++] = a[j][i]; 173 174 for (int j = 0; j < pos; ++j) 175 if (layer[j] == '1' && layer[(j + 1) % pos] == '5' && layer[(j + 2) % pos] == '4' && layer[(j + 3) % pos] == '3') 176 count++; 177 178 } 179 180 printf("%lld\n", count); 181 } 182 183 int main() { 184 int t; scanf("%d", &t); 185 while (t--) solve(); 186 } 187 ``` 188 189 [2036E - Reverse the Rivers](/contest/2036/problem/E "Codeforces Round 984 (Div. 3)") 190 191 Idea: [m3tr0](/profile/m3tr0 "Expert m3tr0") 192 193 **Hint** 194 195 For any non-negative integers, $a \leq a | b$, where $|$ is the bitwise “or” operation. 196 197 **Tutorial** 198 199 After computing the values of $b_{i,j}$ for all countries and regions, we can notice that for a fixed region $j$, the values of $b_{i,j}$ increase as the index $i$ increases. This is because the bitwise “or” operation cannot decrease a number, but only increase or leave it unchanged. Hence, we can use binary search to quickly find the country that matches the given conditions. 200 201 For each query and for each requirement, if $o$ = “<”, we search for the first country where $b_{i,r} \geq c$ (this will be the first country that does not satisfy the condition). If sign $o$ = “>”, we look for the first country where $b_{i,r} \leq c$. In both cases, we can use standard binary search to find the index. If the checks leave at least one country that satisfies all the requirements, we choose the country with the lowest number. 202 203 Complexity: counting values $O(n\cdot k)$, processing each query using binary search $O(m \log n)$, total $O(n \cdot k + q \cdot m \cdot \log n)$. 204 205 **Solution (m3tr0)** 206 207 ``` 208 #include <cstdio> 209 typedef long long l; 210 211 l ** arr; 212 213 int main() { 214 l n, k, q; scanf("%lld %lld %lld", &n, &k, &q); 215 216 arr = new l*[n]; 217 for (l i = 0; i < n; i++) arr[i] = new l[k]; 218 for (l i = 0; i < n; i++) for (l j = 0; j < k; j++) scanf("%lld", &arr[i][j]); 219 220 for (l i = 1; i < n; i++) for (l j = 0; j < k; j++) arr[i][j] |= arr[i - 1][j]; 221 222 while (q--) { 223 l m; scanf("%lld", &m); 224 l left_pos = 0, right_pos = n - 1; 225 while (m--) { 226 l r, c; char o; scanf("%lld %c %lld", &r, &o, &c); r--; 227 if (o == '<') { 228 l le = -1, ri = n, mid; 229 while (le + 1 != ri) { 230 mid = (le + ri) / 2; 231 if (arr[mid][r] < c) le = mid; 232 else ri = mid; 233 } 234 if (le < right_pos) right_pos = le; 235 } else { 236 l le = -1, ri = n, mid; 237 while (le + 1 != ri) { 238 mid = (le + ri) / 2; 239 if (arr[mid][r] <= c) le = mid; 240 else ri = mid; 241 } 242 if (ri > left_pos) left_pos = ri; 243 } 244 } 245 if (left_pos <= right_pos) printf("%lld\n", left_pos + 1); 246 else printf("-1\n"); 247 } 248 } 249 ``` 250 251 [2036F - XORificator 3000](/contest/2036/problem/F "Codeforces Round 984 (Div. 3)") 252 253 Idea: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Specialist eugenechka.boyko.2_0-0") 254 255 **Hint 1** 256 257 Note the base of the module 258 259 **Hint 2** 260 261 Can we quickly compute XOR on the segment $[l, r]$? 262 263 **Tutorial** 264 265 We also recommend the beautiful [tutorial](https://codeforces.com/blog/entry/135766?#comment-1214985) by [ne_justlm](/profile/ne_justlm "Expert ne_justlm")! 266 267 Let us introduce the notation $\DeclareMathOperator{\XOR}{XOR}\XOR(l, r) = l \oplus (l+1) \oplus \dots \oplus r$ . 268 269 The first thing that comes to mind when reading the condition is that we can compute XOR of all numbers on the segment $(0, x)$ for $O(1)$ by the following formula: 270 271 $ \XOR(0, x) = \begin{cases} x & \text{if } x \equiv 0 \pmod{4} \\ 1 & \text{if } x \equiv 1 \pmod{4} \\ x + 1 & \text{if } x \equiv 2 \pmod{4} \\ 0 & \text{if } x \equiv 3 \pmod{4} \end{cases} $ 272 273 Then $\XOR(l, r)$ can be found as $\XOR(0, r) \oplus \XOR(0, l-1)$. 274 275 Now note that for the answer we only need to learn for $O(1)$ to find XOR of all *uninteresting* on the segment: then we can do XOR with the whole segment and get XOR of all *interesting* numbers already. 276 277 The base of the modulus, equal to the degree of two, is not chosen by chance: we only need to “compress” $l$ and $r$ by $2^i$ times in such a way that the resulting range contains all *uninteresting* numbers shifted $i$ bits to the right. Then computing $\XOR(l', r')$ we get exactly the desired XOR of *uninteresting* numbers, also shifted $i$ bits to the right. Then, to find these remaining lower $i$ bits, we just need to find the number of *uninteresting* numbers on the segment $[l, r]$. If it is odd, these $i$ bits will be equal to $k$, since they are all equal to $k \mod 2^i$, and so have the same $i$ minor bits equal to $k$ proper, and so their XOR an odd number of times will also be equal to $k$. 278 279 Otherwise, the lower $i$ bits of the answer will be $0$, since we have done XOR an even number of times. The number of *uninteresting* numbers on the segment can be calculated in a similar way to $\XOR(l, r)$, namely find their number on the segments $[0, r]$ and $[0, l-1]$ and subtract the latter from the former. The number of numbers equal to $k$ modulo $m$ and not exceeding $r$ is calculated as $\left\lfloor \frac{r - k}{m} \right\rfloor$. 280 281 Time complexity of the solution: $O(\mathit{\log r})$. 282 283 **Solution (eugenechka.boyko.2_0-0)** 284 285 ``` 286 #include <iostream> 287 using namespace std; 288 #define int uint64_t 289 #define SPEEDY std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); 290 291 int xor_0_n(int n) { 292 int rem = n % 4; 293 if (rem == 0) { 294 return n; 295 } 296 if (rem == 1) { 297 return 1; 298 } 299 if (rem == 2) { 300 return n + 1; 301 } 302 return 0; 303 } 304 305 int xor_range(int l, int r) { 306 return xor_0_n(r) ^ xor_0_n(l - 1); 307 } 308 309 int32_t main() { 310 int t; 311 cin >> t; 312 while (t--) { 313 int l, r, i, k; 314 cin >> l >> r >> i >> k; 315 int highBits = xor_range((l - k + (1 << i) - 1) >> i, (r - k) >> i) << i; 316 int lowBits = k * (((r - k) / (1 << i) - (l - k - 1) / (1 << i)) & 1); 317 cout << (xor_range(l, r) ^ highBits ^ lowBits) << '\n'; 318 } 319 return 0; 320 } 321 ``` 322 323 [2036G - Library of Magic](/contest/2036/problem/G "Codeforces Round 984 (Div. 3)") 324 325 Idea: [m3tr0](/profile/m3tr0 "Expert m3tr0") 326 327 **Hint 1** 328 329 Have you considered the cases where $a \oplus b \oplus c = 0$? 330 331 **Hint 2** 332 333 Suppose you are certain that at least one lost number is located on some segment $[le, ri]$. Can you choose a value $mid$ such that the queries `xor {le} {mid}` and `xor {mid + 1} {ri}` you can unambiguously understand on which of the segments ($[le, mid]$ or $[(mid + 1), ri]$) lies at least one lost number, even if both of these queries return $0$? 334 335 **Tutorial** 336 337 To begin with, we note that for any number $x$, $x \oplus x = 0$ is satisfied. Therefore, by querying `xor l r`, you will get bitwise XOR of only those volume numbers that are in the library in a single copy (within the scope of querying $l$ and $r$, of course). Also note that for **two** pairwise distinct numbers $x$ and $y$, $x \oplus y \neq 0$ is always satisfied. 338 339 Initially, our goal is — to determine the largest bit of the maximum of the lost numbers. To do this, we can go through the bits starting from the largest significant bit in n. For each $i$-th bit, we will ask `xor {2^i} {min(2^(i + 1) - 1, n)}`. Note that all numbers on this interval have $i$-th bit equal to one. Then if we get a result **not** equal to zero, then this bit is the desired largest bit of the maximum of the lost numbers. If we get a result **equal** to zero, then this bit is guaranteed not to be present in any of the numbers, i.e. all three numbers are less than $2^i$. 340 341 Let's prove it. If we had one or two numbers on the requested interval, their XOR would not be $0$ (see the first paragraph). If all three numbers are on this interval, then the XOR of their $i$-th bit is $1 \oplus 1 \oplus 1 = 1$, and hence the XOR of the numbers themselves is also different from $0$. 342 343 Now that we know the largest bit $i$ of the desired number, we can find this number by any realization of binary search inside the interval $[2^i; \min(2^{i + 1} - 1, n)]$. By the answer to any query on any interval within that interval, we can unambiguously know whether our number is present on that interval or not — the proof is similar to the one above. 344 345 The first number is found. The second number can be found using any bin search, since XOR of two different numbers is always different from zero. The main thing is not to forget to “exclude” the already found number from the obtained result using the same XOR. And the third number can be found by requesting the result of the whole interval from $1$ to $n$ and “excluding” the already found two numbers from it. 346 347 Number of requests: $\approx 2 \cdot \log n \approx 120 \lt 150$ 348 349 **Solution (m3tr0)** 350 351 ``` 352 #include <cstdio> 353 typedef long long l; 354 355 l n, num1, num2; 356 357 l req(l le, l ri, l num) { 358 if (le > n) return 0; 359 if (ri > n) ri = n; 360 361 printf("xor %lld %lld\n", le, ri); fflush(stdout); 362 l res; scanf("%lld", &res); 363 364 if (num > 1 && le <= num1 && num1 <= ri) res ^= num1; 365 if (num > 2 && le <= num2 && num2 <= ri) res ^= num2; 366 return res; 367 } 368 369 void solve() { 370 scanf("%lld", &n); num1 = 0; num2 = 0; 371 l start = 1LL << (63 - __builtin_clzll(n)); 372 373 for (l i = start; i > 0; i >>= 1) { 374 l res = req(num1 | i, num1 | (i * 2 - 1), 1); 375 if (res) num1 |= i; 376 } 377 378 for (l i = start; i > 0; i >>= 1) { 379 l res = req(num2 | i, num2 | (i * 2 - 1), 2); 380 if (res) num2 |= i; 381 } 382 383 printf("ans %lld %lld %lld\n", num1, num2, req(1, n, 3)); 384 fflush(stdout); 385 } 386 387 int main() { 388 l t; scanf("%lld", &t); 389 while (t--) solve(); 390 } 391 ```