codeforces-scrape

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

1905.md (18420B)


      1 Source: https://codeforces.com/blog/entry/123384
      2 
      3 # [A — Constructive Problems](https://codeforces.com/contest/1905/problem/A)
      4 
      5 Author: [cadmiumky](/profile/cadmiumky "Grandmaster cadmiumky")
      6 
      7 **Solution**
      8 
      9 We can observe an invariant given by the problem is that every time we apply adjacent aid on any state of the matrix, the sets of rows that have at least one rebuilt city, respectively the sets of columns that appear that have at least one rebuilt city remain constant. Therefore, if we want to have a full matrix as consequence of applying adjacent aid multiple times, both of these sets must contain all rows/columns. As such, the answer is bounded by $max(n, m)$.
     10 
     11 We can tighten this bound by finding an example which always satisfies the statement. If we take, without loss of generality, $n \le m$, the following initial setting will satisfy the statement: $(1, 1), (2, 2), (3, 3), ..., (n, n), (n, n + 1), (n, n + 2), .. (n, m)$
     12 
     13 **Author's Note**
     14 
     15 I have proposed this div2A at 3 contests and after 1 year of waiting I finally was able to propose it (mainly because theoretically, this was supposed to be my round :)).
     16 
     17 As the title suggests, this problem is inspired by one day trying to solve some constructive problem that required to draw some weird grid with some properties. And, as I was drawing multiple grids to try out multiple strategies, I was wondering how to draw these grids more optimally, as actually having to count for every matrix the height/width was pretty annoying, and I could just eyeball it by drawing it next to another drawn (but filled out) grid. As such, I needed an already drawn grid "below" the current one and another "to the left".
     18 
     19 **Code (valeriu)**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 #define all(x) (x).begin(),(x).end()
     24 using namespace std;
     25 
     26 using ll = long long;
     27 using ld = long double;
     28 
     29 //#define int ll
     30 #define sz(x) ((int)(x).size())
     31 
     32 using pii = pair<int,int>;
     33 using tii = tuple<int,int,int>;
     34 
     35 const int nmax = 1e6 + 5;
     36 const int inf = 1e9 + 5;
     37 int n, k, m, q;
     38 vector<int> g[nmax];
     39 int v[nmax];
     40 
     41 static void testcase() {
     42   cin >> n >> m;
     43   cout << max(n, m) << '\n';
     44   return;
     45 }
     46 
     47 signed main() {
     48   ios::sync_with_stdio(0);
     49   cin.tie(0);
     50   int t;
     51   cin >> t;
     52   for (int i = 0; i < t; i++)
     53     testcase();
     54 }
     55 
     56 /**
     57       Anul asta se da centroid.
     58 -- Surse oficiale
     59 */
     60 ```
     61 
     62 **Rate Problem**
     63 
     64 Good problem
     65 
     66 Ok problem
     67 
     68 Bad problem
     69 
     70 Didn't solve it, idk
     71 
     72 # [B — Beginner's Zelda](https://codeforces.com/contest/1905/problem/B)
     73 
     74 Author: [cadmiumky](/profile/cadmiumky "Grandmaster cadmiumky")
     75 
     76 **Solution**
     77 
     78 We can prove by induction that on any tree with $K$ leaves, the answer is $[{\frac{K + 1}{2}}]$, where with $[x]$ we denote the greatest integer smaller than $x$. This can be proven by induction, we will give an overview of what a proof would look like:
     79 
     80 * For two leaves, the answer is clearly $1$.
     81 * For three leaves, the answer is clearly $2$.
     82 * For more than four leaves, it is always the case that we can find two leaves for which the node that will be created as a result of applying an operation on these two will have degree greater than $1$ (i.e. it will not be a leaf)
     83 
     84 The third argument holds because in a tree with four leaves, we have either at least two nodes with degree at least $3$ (and as such we can choose two leaves which contain these two nodes on their chain), or a node with degree at least $4$. Furthermore, it reduces the number of leaves in the tree by $2$.
     85 
     86 **Code (valeriu)**
     87 
     88 ```
     89 #include <cmath>
     90 #include <functional>
     91 #include <fstream>
     92 #include <iostream>
     93 #include <vector>
     94 #include <algorithm>
     95 #include <string>
     96 #include <set>
     97 #include <map>
     98 #include <list>
     99 #include <time.h>
    100 #include <math.h>
    101 #include <random>
    102 #include <deque>
    103 #include <queue>
    104 #include <unordered_map>
    105 #include <unordered_set>
    106 #include <iomanip>
    107 #include <cassert>
    108 #include <bitset>
    109 #include <sstream>
    110 #include <cstring>
    111 #include <numeric>
    112 #define all(x) (x).begin(),(x).end()
    113 using namespace std;
    114 
    115 using ll = long long;
    116 using ld = long double;
    117 
    118 //#define int ll
    119 #define sz(x) ((int)(x).size())
    120 
    121 using pii = pair<int,int>;
    122 using tii = tuple<int,int,int>;
    123 
    124 const int nmax = 1e6 + 5;
    125 const int inf = 1e9 + 5;
    126 int n, k, m, q;
    127 int freq[nmax];
    128 
    129 static void testcase() {
    130   cin >> n;
    131   for (int i = 1, a, b; i < n; i++) {
    132     cin >> a >> b;
    133     freq[a]++;
    134     freq[b]++;
    135   }
    136   int cnt = 0;
    137   for(int i = 1; i <= n; i++)
    138     cnt += (freq[i] == 1),
    139     freq[i] = 0;
    140   cout << (cnt + 1) / 2 << '\n';
    141   return;
    142 }
    143 
    144 signed main() {
    145   ios::sync_with_stdio(0);
    146   cin.tie(0);
    147   int t;
    148   cin >> t;
    149   for (int i = 0; i < t; i++)
    150     testcase();
    151 }
    152 
    153 /**
    154       Anul asta se da centroid.
    155 -- Surse oficiale
    156 */
    157 ```
    158 
    159 **Rate Problem**
    160 
    161 Good problem
    162 
    163 Ok problem
    164 
    165 Bad problem
    166 
    167 Didn't solve it, idk
    168 
    169 # [C — Largest Subsequence](https://codeforces.com/contest/1905/problem/C)
    170 
    171 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006")
    172 
    173 **Solution**
    174 
    175 We can notice that this operation will ultimately reverse the lexicographically largest subset of the initial string.
    176 
    177 Thus, we can easily check if the string is sortable, and for finding the number of operations we will subtract the length of the largest prefix of equal values of the subset from its length.
    178 
    179 This solution works in $O(n)$ time.
    180 
    181 **Code (tibinyte)**
    182 
    183 ```
    184 #include <bits/stdc++.h>
    185 using namespace std;
    186 int main()
    187 {
    188     cin.tie(nullptr)->sync_with_stdio(false);
    189     int q;
    190     cin >> q;
    191     while (q--)
    192     {
    193         int n;
    194         string s;
    195         cin >> n >> s;
    196         s = '$' + s;
    197         vector<int> subset;
    198         for (int i = 1; i <= n; ++i)
    199         {
    200             while (!subset.empty() && s[subset.back()] < s[i])
    201             {
    202                 subset.pop_back();
    203             }
    204             subset.push_back(i);
    205         }
    206         int ans = 0;
    207         int m = (int)subset.size() - 1;
    208         while (ans <= m && s[subset[ans]] == s[subset[0]])
    209         {
    210             ans++;
    211         }
    212         ans = m - ans + 1;
    213 
    214         for (int i = 0; i <= m; ++i)
    215         {
    216             if (i < m - i)
    217             {
    218                 swap(s[subset[i]], s[subset[m - i]]);
    219             }
    220         }
    221         for (int i = 2; i <= n; ++i)
    222         {
    223             if (s[i] < s[i - 1])
    224             {
    225                 ans = -1;
    226                 break;
    227             }
    228         }
    229         cout << ans << '\n';
    230     }
    231 }
    232 ```
    233 
    234 **Rate Problem**
    235 
    236 Good problem
    237 
    238 Ok problem
    239 
    240 Bad problem
    241 
    242 Didn't solve it, idk
    243 
    244 # [D — Cyclic MEX](https://codeforces.com/contest/1905/problem/D)
    245 
    246 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006")
    247 
    248 **Solution**
    249 
    250 Let's analyze how the values of each prefix mex changes upon performing a cyclic shift to the left:
    251 
    252 * The first prefix mex is popped.
    253 * Each prefix mex with a value less than $p_1$ doesn't change.
    254 * Each prefix mex with a value greater than $p_1$ becomes $p_1$.
    255 * $n$ is appended to the back.
    256 
    257 Let's keep our prefix mexes compressed ( meaning that we keep the value and its frequency instead of keeping multiple same values ). After that, we can simulate the above process naively with a deque, because the potential will decrease by the number of performed operations.
    258 
    259 This solution works in $O(n)$ time.
    260 
    261 **Code (tibinyte)**
    262 
    263 ```
    264 #include <bits/stdc++.h>
    265 
    266 #define int long long
    267 
    268 using namespace std;
    269 
    270 int32_t main()
    271 {
    272 	cin.tie(nullptr)->sync_with_stdio(false);
    273 	int q;
    274 	cin >> q;
    275 	while (q--)
    276 	{
    277 		int n;
    278 		cin >> n;
    279 		vector<int> a(n + 1);
    280 		for (int i = 1; i <= n; ++i)
    281 		{
    282 			cin >> a[i];
    283 		}
    284 		deque<pair<int, int>> dq;
    285 		vector<int> f(n + 1);
    286 		int mex = 0;
    287 		int sum = 0;
    288 		for (int i = 1; i <= n; ++i)
    289 		{
    290 			f[a[i]]++;
    291 			while (f[mex])
    292 			{
    293 				mex++;
    294 			}
    295 			dq.push_back({mex, 1});
    296 			sum += mex;
    297 		}
    298 		int ans = sum;
    299 		for (int i = 1; i < n; ++i)
    300 		{
    301 			pair<int, int> me = {a[i], 0};
    302 			sum -= dq.front().first;
    303 			dq.front().second--;
    304 			if (dq.front().second == 0)
    305 			{
    306 				dq.pop_front();
    307 			}
    308 			while (!dq.empty() && dq.back().first >= a[i])
    309 			{
    310 				sum -= dq.back().first * dq.back().second;
    311 				me.second += dq.back().second;
    312 				dq.pop_back();
    313 			}
    314 			dq.push_back(me);
    315 			sum = sum + me.first * me.second;
    316 			dq.push_back({n, 1});
    317 			sum += n;
    318 			ans = max(ans, sum);
    319 		}
    320 		cout << ans << '\n';
    321 	}
    322 }
    323 ```
    324 
    325 **Rate Problem**
    326 
    327 Good problem
    328 
    329 Ok problem
    330 
    331 Bad problem
    332 
    333 Didn't solve it, idk
    334 
    335 # [E — One-X](https://codeforces.com/contest/1905/problem/E)
    336 
    337 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006")
    338 
    339 **Solution**
    340 
    341 Let's try to solve a slightly easier problem first: changing the coefficient of the label to be the msb of the label.
    342 
    343 We can note that at each depth, every label will have the same number of digits ( in base 2 ), thus the same msb. And we can notice that for each depth there are at most $2$ different interval lengths. Combining the former with the latter, we can solve this case in $O(log(N))$ time complexity, since the maximum depth is bounded by $log(N)$.
    344 
    345 We can find an easy generalization to this: for the $k$-th most significant bit of each label to be $1$, we have to go right from a node whose depth is $k-1$. Thus the above solution can be extended to find the contribution of the $k$-th most significant bit of each label.
    346 
    347 Doing this for all bits gives us a time complexity of $O(log^2(N))$ which is sufficient to pass the given constraints.
    348 
    349 **Code (tibinyte)**
    350 
    351 ```
    352 #include <bits/stdc++.h>
    353 #define int long long
    354 using namespace std;
    355 const int mod = 998244353;
    356 struct Mint
    357 {
    358     int val;
    359     Mint(long long x = 0)
    360     {
    361         val = x % mod;
    362     }
    363     Mint operator+(Mint oth)
    364     {
    365         return val + oth.val;
    366     }
    367     Mint operator-(Mint oth)
    368     {
    369         return val - oth.val + mod;
    370     }
    371     Mint operator*(Mint oth)
    372     {
    373         return val * oth.val;
    374     }
    375 };
    376 Mint powmod(int a, int b)
    377 {
    378     if (b == 0)
    379     {
    380         return 1;
    381     }
    382     if (b % 2 == 1)
    383     {
    384         return powmod(a, b - 1) * a;
    385     }
    386     Mint P = powmod(a, b / 2);
    387     return P * P;
    388 }
    389 map<int, vector<vector<tuple<int, int, int>>>> memo;
    390 vector<vector<tuple<int, int, int>>> find_ranges(int lg) // log^2
    391 {
    392     if (memo.find(lg) != memo.end())
    393     {
    394         return memo[lg];
    395     }
    396     if (lg == 1)
    397     {
    398         return {{{1, 1, 1}}};
    399     }
    400     vector<vector<tuple<int, int, int>>> l = find_ranges((lg + 1) / 2);
    401     vector<vector<tuple<int, int, int>>> r = find_ranges(lg / 2);
    402     vector<vector<tuple<int, int, int>>> ans(max(l.size(), r.size()) + 1);
    403     Mint x = (powmod(2, (lg + 1) / 2) - 1) * (powmod(2, lg / 2) - 1);
    404     ans[0].push_back({lg, 1, x.val});
    405      for (int i = 0; i < (int)l.size(); ++i)
    406     {
    407         for (auto j : l[i])
    408         {
    409             ans[i + 1].push_back(j);
    410         }
    411     }
    412     for (int i = 0; i < (int)r.size(); ++i)
    413     {
    414         for (auto j : r[i])
    415         {
    416             bool ok = false;
    417             for (auto &[size, cnt, ways] : ans[i + 1])
    418             {
    419                 if (size == get<0>(j))
    420                 {
    421                     ok = true;
    422                     cnt += get<1>(j);
    423                 }
    424             }
    425             if (!ok)
    426             {
    427                 ans[i + 1].push_back(j);
    428             }
    429         }
    430     }
    431     return memo[lg] = ans;
    432 }
    433 Mint count(int lg, int coef)
    434 {
    435     vector<vector<tuple<int, int, int>>> adam = find_ranges(lg);
    436     Mint ans = 0;
    437     Mint pow_2 = 1;
    438     for (int i = 0; i < (int)adam.size(); ++i)
    439     {
    440         for (auto [size, cnt, ways] : adam[i])
    441         {
    442             ans = ans + pow_2 * coef * cnt * ways;
    443         }
    444         pow_2 = pow_2 * 2;
    445     }
    446     return ans;
    447 }
    448 int32_t main()
    449 {
    450     cin.tie(nullptr)->sync_with_stdio(false);
    451     int q;
    452     cin >> q;
    453     while (q--)
    454     {
    455         int n;
    456         cin >> n;
    457         vector<vector<tuple<int, int, int>>> adam = find_ranges(n);
    458         Mint ans = count(n, 1);
    459         for (int i = 1; i < (int)adam.size(); ++i)
    460         {
    461             for (auto [size, cnt, ways] : adam[i - 1])
    462             {
    463                 int lsize = (size + 1) / 2;
    464                 int rsize = size / 2;
    465                 if (rsize)
    466                 {
    467                     ans = ans + count(rsize, cnt);
    468                 }
    469             }
    470         }
    471         cout << ans.val << '\n';
    472         memo.clear();
    473     }
    474 }
    475 ```
    476 
    477 **Rate Problem**
    478 
    479 Good problem
    480 
    481 Ok problem
    482 
    483 Bad problem
    484 
    485 Didn't solve it, idk
    486 
    487 # [F — Field Should Not Be Empty](https://codeforces.com/contest/1905/problem/F)
    488 
    489 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006")
    490 
    491 **Solution**
    492 
    493 The key observation to this problem is that most swaps are useless. In fact, we can find that only $2n$ swaps can increase our initial cost:
    494 
    495 * The first type of meaningful swaps is $(i,p_i)$
    496 * For each $1 \lt i \lt n$, consider $k$ and $l$ such that $p_k = max(p_1,p_2,...,p_{i-1})$ and $p_l = min(p_{i+1},p_{i+2},...,p_n)$. The second type is $(k,l)$.
    497 
    498 The reason why this is true is because the first type of swap can create a new good index ( since every good index must be a fixed point ) and the second type of swap can fix an already good index. It's obvious that if a swap does neither of the above, it can't increase our current cost.
    499 
    500 Calculating $f(p)$ after each swap can be done with a segment tree. Consider adding one on the ranges $(min(i,p_i),max(i,p_i))$. Now an index is good if and only if its value is $1$, which is also the minimum value an index can have. Thus our segment tree has to find the number of minimums while performing range additions which can be easily maintained by lazy propagation.
    501 
    502 This solution works in $O(nlog(n))$ time complexity.
    503 
    504 **Code (tibinyte)**
    505 
    506 ```
    507 #include <bits/stdc++.h>
    508 using namespace std;
    509 struct aint
    510 {
    511     vector<pair<int, int>> a;
    512     vector<int> lazy;
    513     void resize(int n)
    514     {
    515         a = vector<pair<int, int>>(4 * n);
    516         lazy = vector<int>(4 * n);
    517     }
    518     void init(int node, int left, int right)
    519     {
    520         a[node].second = (right - left + 1);
    521         if (left != right)
    522         {
    523             int mid = (left + right) / 2;
    524             init(2 * node, left, mid);
    525             init(2 * node + 1, mid + 1, right);
    526         }
    527     }
    528     void prop(int node, int left, int right)
    529     {
    530         a[node].first += lazy[node];
    531         if (left != right)
    532         {
    533             lazy[2 * node] += lazy[node];
    534             lazy[2 * node + 1] += lazy[node];
    535         }
    536         lazy[node] = 0;
    537     }
    538     pair<int, int> merge(pair<int, int> a, pair<int, int> b)
    539     {
    540         if (a.first == b.first)
    541         {
    542             return pair<int, int>{a.first, a.second + b.second};
    543         }
    544         return min(a, b);
    545     }
    546     void update(int node, int left, int right, int st, int dr, int val)
    547     {
    548         prop(node, left, right);
    549         if (right < st || left > dr)
    550         {
    551             return;
    552         }
    553         if (st <= left && dr >= right)
    554         {
    555             lazy[node] += val;
    556             prop(node, left, right);
    557             return;
    558         }
    559         int mid = (left + right) / 2;
    560         update(2 * node, left, mid, st, dr, val);
    561         update(2 * node + 1, mid + 1, right, st, dr, val);
    562         a[node] = merge(a[2 * node], a[2 * node + 1]);
    563     }
    564 };
    565 struct bit
    566 {
    567     vector<int> a;
    568     void resize(int n)
    569     {
    570         a = vector<int>(n + 1);
    571     }
    572     void update(int pos, int val)
    573     {
    574         int n = (int)a.size() - 1;
    575         for (int i = pos; i <= n; i += i & (-i))
    576         {
    577             a[i] += val;
    578         }
    579     }
    580     int query(int pos)
    581     {
    582         int ans = 0;
    583         for (int i = pos; i; i -= i & (-i))
    584         {
    585             ans += a[i];
    586         }
    587         return ans;
    588     }
    589     int query(int st, int dr)
    590     {
    591         return query(dr) - query(st - 1);
    592     }
    593 };
    594 int32_t main()
    595 {
    596     cin.tie(nullptr)->sync_with_stdio(false);
    597     int q;
    598     cin >> q;
    599     while (q--)
    600     {
    601         int n;
    602         cin >> n;
    603         vector<int> a(n + 1);
    604         bool sortat = true;
    605         for (int i = 1; i <= n; ++i)
    606         {
    607             cin >> a[i];
    608             if (a[i] != i)
    609             {
    610                 sortat = false;
    611             }
    612         }
    613         if (sortat)
    614         {
    615             cout << n - 2 << '\n';
    616             continue;
    617         }
    618         vector<pair<int, int>> qui(n + 1);
    619         stack<int> s;
    620         bit tree;
    621         tree.resize(n);
    622         for (int i = 1; i <= n; ++i)
    623         {
    624             while (!s.empty() && a[s.top()] < a[i])
    625             {
    626                 s.pop();
    627             }
    628             if (!s.empty())
    629             {
    630                 qui[i].first = s.top();
    631             }
    632             if (tree.query(a[i], n) > 1)
    633             {
    634                 qui[i].first = 0;
    635             }
    636             tree.update(a[i], 1);
    637             s.push(i);
    638         }
    639         while (!s.empty())
    640             s.pop();
    641         tree.resize(n);
    642         for (int i = n; i >= 1; --i)
    643         {
    644             while (!s.empty() && a[s.top()] > a[i])
    645             {
    646                 s.pop();
    647             }
    648             if (!s.empty())
    649             {
    650                 qui[i].second = s.top();
    651             }
    652             if (tree.query(1, a[i]) > 1)
    653             {
    654                 qui[i].second = 0;
    655             }
    656             tree.update(a[i], 1);
    657             s.push(i);
    658         }
    659         aint lesgo;
    660         lesgo.resize(n);
    661         lesgo.init(1, 1, n);
    662         function<void(int, int)> upd = [&](int ind, int sign)
    663         {
    664             lesgo.update(1, 1, n, min(ind, a[ind]), max(ind, a[ind]), sign);
    665         };
    666         function<int()> count = [&]()
    667         {
    668             if (lesgo.a[1].first == 1)
    669             {
    670                 return lesgo.a[1].second;
    671             }
    672             return 0;
    673         };
    674         function<void(int, int)> mySwap = [&](int i, int j)
    675         {
    676             upd(i, -1);
    677             upd(j, -1);
    678             swap(a[i], a[j]);
    679             upd(i, 1);
    680             upd(j, 1);
    681         };
    682         for (int i = 1; i <= n; ++i)
    683         {
    684             upd(i, 1);
    685         }
    686         int ans = 0;
    687         for (int i = 1; i <= n; ++i)
    688         {
    689             if (qui[i].first && qui[i].second)
    690             {
    691                 mySwap(qui[i].first, qui[i].second);
    692                 ans = max(ans, count());
    693                 mySwap(qui[i].first, qui[i].second);
    694             }
    695         }
    696         vector<int> pos(n + 1);
    697         for (int i = 1; i <= n; ++i)
    698         {
    699             pos[a[i]] = i;
    700         }
    701         for (int i = 1; i <= n; ++i)
    702         {
    703             int qui1 = i;
    704             int qui2 = pos[i];
    705             mySwap(qui1, qui2);
    706             ans = max(ans, count());
    707             mySwap(qui1, qui2);
    708         }
    709         cout << ans << '\n';
    710     }
    711 }
    712 ```
    713 
    714 **Rate Problem**
    715 
    716 Good problem
    717 
    718 Ok problem
    719 
    720 Bad problem
    721 
    722 Didn't solve it, idk