codeforces-scrape

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

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