codeforces-scrape

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

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