1720.md (14285B)
1 Source: https://codeforces.com/blog/entry/106136 2 3 ## [A — Burenka Plays with Fractions](https://codeforces.com/contest/1720/problem/A) 4 5 Authors: [glebustim](/profile/glebustim "Мастер glebustim") 6 7 **Solution** 8 9 Note that we always can make fractions equal in two operations: Multiply first fraction's enumerator by $bc$, the first fraction is equal to $\frac{abc}{b} = ac$, Multiply second fraction's enumerator by $ad$, the second fraction is equal to $\frac{acd}{d} = ac$. 10 11 That means that the answer does not exceed 2. 12 13 If fractions are equal from input, the answer is 0. Otherwise, it can't be 0. 14 15 Now we have to check if the answer is 1. Let's assume that for making fractions equal in 1 operation we have to multiply first fraction's enumerator by $x$. Then $\frac{ax}{b} = \frac{c}{d}$ must be true. From this we can see that $x = \frac{bc}{ad}$. $x$ must be integer, so $bc$ must be divisible by $ad$. If we assume that we multiplied first fraction's denumerator by $x$, we can do the same calculations and see that $ad$ must be divisible by $bc$. So, for checking if the answer is $1$ we need to check if one of $ad$ and $bc$ is divisible by another one. If we multiply second fraction's enumerator or denumerator by $x$ we will get the same conditions for answer being equla to 1. 16 17 If the answer is not 0 or 1, it's 2. 18 19 Complexity: $O(1)$ 20 21 **Code(C++)** 22 23 ``` 24 #include <bits/extc++.h> 25 using namespace std; 26 using namespace __gnu_cxx; 27 using namespace __gnu_pbds; 28 29 #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) 30 #define sfor(i, l, r) for (int i = l; i <= r; ++i) 31 #define bfor(i, r, l) for (int i = r; i >= l; --i) 32 #define all(a) a.begin(), a.end() 33 using ll = long long; 34 using ld = long double; 35 using pii = pair<int, int>; 36 using vi = vector<int>; 37 using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>; 38 39 void solve() { 40 ll a, b, c, d; 41 cin >> a >> b >> c >> d; 42 ll x = a * d, y = b * c; 43 if (x == y) 44 cout << "0\n"; 45 else if (y != 0 && x % y == 0 || x != 0 && y % x == 0) 46 cout << "1\n"; 47 else 48 cout << "2\n"; 49 } 50 51 int main() { 52 fast; 53 int t; 54 cin >> t; 55 while (t--) 56 solve(); 57 } 58 ``` 59 60 ## [B — Interesting Sum](https://codeforces.com/contest/1720/problem/B) 61 62 **Solution** 63 64 Obviously, answer does not exceed $max_{1} + max_{2} - min_{1} - min_{2}$, where $max_{1}, max_{2}$ are two maximum values in the array, and $min_{1}, min_{2}$ are two minimum values. Let's find a segment, such as this is true. For that we will look at all positions containing $max_{1}$ or $max_{2}$ ($S_{1}$) and all positions containing $min_{1}$ or $min_{2}$ ($S_2$). After that we choose a pair $l \in S_1$, $r \in S_2$, such as $abs(r - l)$ is minimum possible. Complexity: $O(n\log n)$ 65 66 **Code(C++)** 67 68 ``` 69 #include <iostream> 70 #include <vector> 71 #include <algorithm> 72 73 using namespace std; 74 75 typedef long long ll; 76 typedef long double ld; 77 78 #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 79 80 vector<ll> vec; 81 ll n; 82 83 int main() { 84 fastInp; 85 86 ll t; 87 cin >> t; 88 89 while (t--) { 90 cin >> n; 91 92 vec.resize(n); 93 for (auto& c : vec) cin >> c; 94 95 sort(vec.begin(), vec.end()); 96 97 cout << vec[n - 1] + vec[n - 2] - vec[0] - vec[1] << "\n"; 98 } 99 100 return 0; 101 } 102 ``` 103 104 ## [C — Corners](https://codeforces.com/contest/1720/problem/C) 105 106 Authors: [allvik66](/profile/allvik66 "Гроссмейстер allvik66") 107 108 **Solution** 109 110 Let's say that $cnt_1$ is the number of ones in the table. 111 112 Note that if there is a connected area of zeros in the table of size at least 2, then we can add one $0$ to this area by replacing only one 1 in the table. That means that if we have such area we can fill the table with zeros in $cnt_1$ operations (we can't make more opertions because we need to replace at least one 1 by operation). 113 114 There can be no such area in the beginning, but after first operation it will appear. So, for finding the answer we just need to find an angle with minimal number of 1 in it, and which we can replace. 115 116 Complexity: $O(nm)$ 117 118 **Code(C++)** 119 120 ``` 121 #include <iostream> 122 #include <vector> 123 #include <algorithm> 124 #include <array> 125 #include <cassert> 126 #include <map> 127 #include <set> 128 #include <cmath> 129 #include <deque> 130 #include <random> 131 #include <iomanip> 132 #include <chrono> 133 #include <bitset> 134 #include <queue> 135 #include <complex> 136 #include <functional> 137 138 using namespace std; 139 const int INF = 1e9; 140 const int MAXN = 2000; 141 int a[MAXN][MAXN]; 142 143 inline void solve1() { 144 int n, m, sum = 0; 145 cin >> n >> m; 146 string s; 147 for (int i = 0; i < n; ++i) { 148 cin >> s; 149 for (int j = 0; j < m; ++j) { 150 a[i][j] = s[j] - '0'; 151 sum += a[i][j]; 152 } 153 } 154 int minn = INF; 155 for (int i = 0; i < n - 1; ++i) { 156 for (int j = 0; j < m - 1; ++j) { 157 int cnt = a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1]; 158 if (cnt == 0) continue; 159 minn = min(minn, max(1, cnt - 1)); 160 } 161 } 162 if (sum == 0) cout << "0\n"; 163 else cout << 1 + sum - minn << "\n"; 164 } 165 166 signed main() { 167 int t = 1; 168 cin >> t; 169 while (t--) { 170 solve1(); 171 } 172 } 173 ``` 174 175 ## [D1 — Xor-Subsequence (easy version)](https://codeforces.com/contest/1720/problem/D1) 176 177 Authors: [kirill.kligunov](/profile/kirill.kligunov "Эксперт kirill.kligunov") 178 179 **Solution** 180 181 Let's use dynamic programming to solve this task. $dp_i$ -- maximum length of good subsequence, that ends int $i$-th element of $a$, than naive solution is 182 183 $ dp_i = \max_{\substack{j = 0 \\ a_j \oplus i \lt a_i \oplus j}}^i dp_j + 1 $ 184 185 Let's observe that $a_j \oplus i$ changes $i$ not more than by $200$. 186 187 This way we can relax $dp_i$ not from $j = 0$, but $j = i - 512$, because xor operation changes only last 8 bits, so for $j' \lt i - 512$, definitely $a_{j'} \oplus j \gt a_{j} \oplus j'$. 188 189 Additional idea: 190 191 It not so hard to proove that we can try $j$ from $i - 256$ to $i - 1$. 192 193 **Code(C++)** 194 195 ``` 196 #include <iostream> 197 #include <vector> 198 199 using namespace std; 200 201 typedef long long ll; 202 typedef long double ld; 203 204 #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 205 206 vector<ll> vec; 207 ll n; 208 209 const ll CHECK = 512; 210 211 int solve() { 212 213 cin >> n; 214 215 vec.resize(n); 216 for (auto& c : vec) cin >> c; 217 218 vector<ll> dp(1); 219 220 ll bst = 0; 221 for (int i = 0; i < n; i++) { 222 ll cur = 0; 223 dp.push_back(1); 224 for (int j = i - 1; j >= max(0ll, i - CHECK); j--) { 225 if ((vec[i] ^ j) > (vec[j] ^ i)) { 226 dp.back() = max(dp.back(), dp[j + 1] + 1); 227 } 228 } 229 230 bst = max(bst, dp.back()); 231 } 232 233 cout << bst << "\n"; 234 235 return 0; 236 } 237 238 int main(){ 239 fastInp; 240 int t; 241 cin >> t; 242 while(t--) solve(); 243 } 244 ``` 245 246 ## [D2 — Xor-Subsequence (hard version)](https://codeforces.com/contest/1720/problem/D2) 247 248 Authors: [kirill.kligunov](/profile/kirill.kligunov "Эксперт kirill.kligunov") 249 250 **Solution** 251 252 Let's calculate answer for each prefix. Let's find answer if the last number in our subsequence is number with index $i$. 253 254 Let there be such $j$ that $a[j] \oplus i \lt a[i] \oplus j $. That means that there are $k$ bits in numbers $a[j] \oplus i$ and $a[i] \oplus j$ which are the same, and after that $a[j] \oplus i$ has different $k + 1$-th bit. Let's notice that if first $k$ bits are the same in $a[j] \oplus i$ and $a[i] \oplus j$, then these bits are the same in $a[j] \oplus j$ and $a[i] \oplus i$ 255 256 Let's keep our answer in bit trie. We will add numbers $a[j] \oplus j$ for our prefix. To find dp value for index $i$, we will descend in our trie with pair of integers $a_i \oplus i$ and $i$. Each time we descend with bit $l$(0 or 1), in the opposite subtree there might be numbers which we can use to recalculate our answer. If in that subtree exists indexс $j$, then $k+1$-th bit of $a[j] \cdot i$ to $0$. Let's keep such dp for every subtree: maximum value of $dp[j]$ for every $j$, such that $j$ lies in the subtree (but we need to keep answer if $k$-th bit of $j$ is 0, and if it's equals 1). We should try to improve our answer using $j$ if we descend to the opposite subtree. Then we can easily find answer for current $i$. After that we only need to add our number in the trie and recalculate the dp. 257 258 Complexity: O(n * logC) where C its max value 259 260 **Code(C++)** 261 262 ``` 263 #include <iostream> 264 #include <vector> 265 #include <algorithm> 266 267 using namespace std; 268 269 const int maxlog = 30; 270 const int maxn = 300000; 271 272 int nodes[maxn * maxlog + maxlog][2]; 273 int nodev[maxn * maxlog + maxlog][2]; 274 int last; 275 276 inline int f() { 277 nodes[last][0] = 0; 278 nodes[last][1] = 0; 279 nodev[last][0] = 0; 280 nodev[last][1] = 0; 281 return last++; 282 } 283 284 int solve() { 285 int n; 286 cin >> n; 287 vector <int> v(n); 288 for (auto& i : v) cin >> i; 289 int ans = 0; 290 last = 0; 291 f(); 292 for (int i = 0; i < n; i++) { 293 int a = 0; 294 int b = v[i] ^ i; 295 int c = i; 296 int getmax = 0; 297 for (int j = maxlog; j >= 0; j--) { 298 if (nodes[a][((b >> j) & 1) ^ 1]) getmax = max(getmax, nodev[nodes[a][((b >> j) & 1) ^ 1]][(((b ^ c) >> j) & 1) ^ 1]); 299 if (!nodes[a][(b >> j) & 1]) break; 300 a = nodes[a][(b >> j) & 1]; 301 } 302 ans = max(ans, getmax + 1); 303 a = 0; 304 b = v[i] ^ i; 305 c = i; 306 int d = getmax + 1; 307 for (int j = maxlog; j >= 0; j--) { 308 if (!nodes[a][(b >> j) & 1]) nodes[a][(b >> j) & 1] = f(); 309 nodev[nodes[a][(b >> j) & 1]][(c >> j) & 1] = max(nodev[nodes[a][(b >> j) & 1]][(c >> j) & 1], d); 310 a = nodes[a][(b >> j) & 1]; 311 } 312 } 313 cout << ans << "\n"; 314 return 0; 315 } 316 317 int main() { 318 ios::sync_with_stdio(0); cin.tie(0); 319 int t; 320 cin >> t; 321 while (t--) solve(); 322 } 323 ``` 324 325 ## [E — Misha and Paintings](https://codeforces.com/contest/1720/problem/E) 326 327 Authors: [allvik66](/profile/allvik66 "Гроссмейстер allvik66"), [pakhomovee](/profile/pakhomovee "Мастер pakhomovee") 328 329 **Solution** 330 331 If $k$ is greater than the number of different numbers in the matrix, then the answer is $k$ minus the number of different elements. 332 333 Otherwise the answer does not exceed 2. 334 335 Let's proof that: choose the maximum square (let its side be equal to $L$), containing the top left corner of the matrix, such as recolouring it to some new colour makes the number of different colours in the table at least $k$. 336 337 If the number of different colours after recolouring is greater than $k$, then choose a square with bottom right corner in $(L + 1, L + 1)$, such as recolouring it makes the number of different colours at least $k$. If we got exactly $k$ colours then we are done. Otherwise let's extend the square by one. We got $k$ or $k - 1$ different colours. This way, by choosing the correct colour of the square we can get exactly $k$ colours. Otherwise we are done. 338 339 It remains to learn how to check whether the answer is equal to 1. We will iterate over length of the side of the square of the answer. Now we need $O(n^2)$ to check whether the required square with such a side exists. To do this, we calculate for each square in the table with such a side length (there are $n^2$ such squares), how many numbers this square completely covers (all appeareances of this numbers are in thsi square). To do this, let's iterate over the number $c$. Having considered its occurrences, it is easy to understand that the upper left corners of all squares with our side length, covering all cells with the number $c$, lie in some subrectangle of the table, so you can simply add 1 on this subrectangle using offline prefix sums. Having processed all the numbers in this way, we can count for each square how many numbers it covers completely, and therefore check whether it fits the requirements. 340 341 Complexity: $O(n^3)$ 342 343 **Code(C++)** 344 345 ``` 346 #include <iostream> 347 #include <vector> 348 #include <cmath> 349 #include <array> 350 351 using namespace std; 352 const int INF = 1e9; 353 354 inline int min(int a, int b) { 355 if (a < b) return a; 356 return b; 357 } 358 359 inline int max(int a, int b) { 360 if (a > b) return a; 361 return b; 362 } 363 364 inline void solve1() { 365 int n, k, cnt = 0; 366 cin >> n >> k; 367 vector <vector <int>> a(n, vector <int>(n)), pref(n + 1, vector <int>(n + 1)); 368 vector <array <int, 4>> all(n * n, { INF, -INF, INF, -INF }); 369 for (int i = 0; i < n; ++i) { 370 for (int j = 0; j < n; ++j) { 371 cin >> a[i][j]; --a[i][j]; 372 all[a[i][j]][0] = min(all[a[i][j]][0], i); 373 all[a[i][j]][1] = max(all[a[i][j]][1], i); 374 all[a[i][j]][2] = min(all[a[i][j]][2], j); 375 all[a[i][j]][3] = max(all[a[i][j]][3], j); 376 } 377 } 378 for (auto& i : all) { 379 if (i[0] != INF) ++cnt; 380 } 381 if (cnt <= k) { 382 cout << k - cnt; 383 return; 384 } 385 for (int len = 1; len <= n; ++len) { 386 for (auto& i : all) { 387 if (i[0] == INF) continue; 388 int mn_x = i[0], mx_x = i[1], mn_y = i[2], mx_y = i[3]; 389 mx_x = max(0, mx_x - len + 1); 390 mx_y = max(0, mx_y - len + 1); 391 mn_x = min(mn_x, n - len); 392 mn_y = min(mn_y, n - len); 393 if (mx_x <= mn_x && mx_y <= mn_y) { 394 ++pref[mx_x][mx_y]; 395 --pref[mx_x][mn_y + 1]; 396 --pref[mn_x + 1][mx_y]; 397 ++pref[mn_x + 1][mn_y + 1]; 398 } 399 } 400 for (int x = 0; x < n; ++x) { 401 for (int y = 0; y < n; ++y) { 402 if (x == 0 && y == 0) continue; 403 else if (x == 0) pref[x][y] += pref[x][y - 1]; 404 else if (y == 0) pref[x][y] += pref[x - 1][y]; 405 else pref[x][y] += pref[x - 1][y] + pref[x][y - 1] - pref[x - 1][y - 1]; 406 } 407 } 408 for (int x = 0; x < n; ++x) { 409 for (int y = 0; y < n; ++y) { 410 if (cnt - pref[x][y] == k || cnt - pref[x][y] + 1 == k) { 411 cout << 1; 412 return; 413 } 414 } 415 } 416 for (int i = 0; i <= n; ++i) { 417 for (int j = 0; j <= n; ++j) { 418 pref[i][j] = 0; 419 } 420 } 421 } 422 cout << 2; 423 } 424 425 int main() { 426 if (1) { 427 ios_base::sync_with_stdio(false); 428 cin.tie(nullptr); 429 cout.tie(nullptr); 430 } 431 if (1) { 432 int t = 1; 433 // cin >> t; 434 while (t--) { 435 solve1(); 436 } 437 } 438 439 return 0; 440 } 441 ```