codeforces-scrape

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

2049.md (16238B)


      1 Source: https://codeforces.com/blog/entry/137273
      2 
      3 [2049A - MEX Destruction](/contest/2049/problem/A "Codeforces Round 994 (Div. 2)")
      4 
      5 Idea & preparation: [Evirir](/profile/Evirir "Master Evirir")
      6 
      7 **Tutorial**
      8 
      9 ### [2049A - MEX Destruction](/contest/2049/problem/A "Codeforces Round 994 (Div. 2)")
     10 
     11 Case 1: All elements are $0$. Then the answer is $0$.
     12 
     13 Case 2: Some element is non-zero, and all non-zero elements form a contiguous subarray. Then the answer is $1$ since we can choose that subarray and replace it with a $0$.
     14 
     15 Case 3: Otherwise, the answer is $2$.
     16 
     17 * We can replace the entire array with a non-zero element (since $0$ is in the array), then replace the entire array again with a $0$ (since the only element left is non-zero).
     18 * $1$ operation is not enough. If we only use $1$ operation, the selected subarray must contain all non-zero elements. Since the non-zero elements do not form a subarray, the selected subarray must contain a $0$, thus the $\operatorname{MEX}$ will be non-zero.
     19 
     20 **Solution**
     21 
     22 ```
     23 #include <bits/stdc++.h>
     24 using namespace std;
     25 
     26 void solve()
     27 {
     28     int n; cin >> n;
     29     vector<int> a(n);
     30     for (int i = 0; i < n; i++)
     31         cin >> a[i];
     32 
     33     while (!a.empty() && a.back() == 0)
     34         a.pop_back();
     35 
     36     reverse(a.begin(), a.end());
     37     while (!a.empty() && a.back() == 0)
     38         a.pop_back();
     39     reverse(a.begin(), a.end());
     40 
     41     if (a.empty())
     42     {
     43         cout << 0 << '\n';
     44         return;
     45     }
     46 
     47     bool hasZero = false;
     48     for (const auto x : a)
     49         hasZero |= x == 0;
     50     if (hasZero)
     51         cout << 2 << '\n';
     52     else
     53         cout << 1 << '\n';
     54 }
     55 
     56 int main()
     57 {
     58     int t;
     59     cin >> t;
     60     for (int i = 0; i < t; i++)
     61         solve();
     62 
     63     return 0;
     64 }
     65 ```
     66 
     67 [2049B - pspspsps](/contest/2049/problem/B "Codeforces Round 994 (Div. 2)")
     68 
     69 Idea & preparation: [Evirir](/profile/Evirir "Master Evirir")
     70 
     71 **Tutorial**
     72 
     73 ### [2049B - pspspsps](/contest/2049/problem/B "Codeforces Round 994 (Div. 2)")
     74 
     75 Since the entire $p$ must be a permutation, if $s_1 =$`s`, we can set $s_1 = $`.`, and if $s_n =$`p`, we can set $s_n =$`.`.
     76 
     77 After that, the answer is `YES` if and only if all non-dot characters in $s$ are all `p` or `s`.
     78 
     79 If all non-dot characters are `p`, we can choose the permutation $p = [1, 2, \ldots, n]$. If all non-dot characters are `s`, we can choose $p = [n, n - 1, \ldots, 1]$.
     80 
     81 Otherwise, there exists both a `p` and a `s`. Suppose for contradiction that there is a solution. Let $a$ and $b$ represent the subarrays represented by the `p` and `s` respectively. Without loss of generality, suppose $a$ is the shorter subarray.
     82 
     83 * Since $b$ is also a permutation, the elements of $a$ must be in $b$. Since $p$ is a permutation, $a$ must be a subarray of $b$.
     84 * However, $b$ cannot contain $a$: since $b$ is not the entire $p$, $b$ does not contain $p_1$. However, $a$ contains $p_1$. Contradiction.
     85 
     86 **Solution**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90 using namespace std;
     91 
     92 void solve()
     93 {
     94     int n; cin >> n;
     95     string s; cin >> s;
     96     if (s[0] == 's') s[0] = '.';
     97     if (s.back() == 'p') s.back() = '.';
     98     bool found_p = false;
     99     bool found_s = false;
    100     for (const auto c : s)
    101     {
    102         switch (c)
    103         {
    104         case 'p':
    105             found_p = true;
    106             break;
    107         case 's':
    108             found_s = true;
    109             break;
    110         }
    111     }
    112     cout << (found_p && found_s ? "NO" : "YES") << '\n';
    113 }
    114 
    115 int main()
    116 {
    117     int t; cin >> t;
    118     for (int i = 0; i < t; i++) solve();
    119 
    120     return 0;
    121 }
    122 ```
    123 
    124 [2049C - MEX Cycle](/contest/2049/problem/C "Codeforces Round 994 (Div. 2)")
    125 
    126 Idea and solution: [Evirir](/profile/Evirir "Master Evirir") and [Kaey](/profile/Kaey "Grandmaster Kaey")  
    127  Preparation: [Evirir](/profile/Evirir "Master Evirir")
    128 
    129 **Tutorial**
    130 
    131 ### [2049C - MEX Cycle](/contest/2049/problem/C "Codeforces Round 994 (Div. 2)")
    132 
    133 There are many possible solutions. The simplest one we can find (thanks to [Kaey](/profile/Kaey "Grandmaster Kaey")) is as follows:
    134 
    135 * Set $a_x = 0, a_{x+1} = 1, a_{x+2} = 0, \ldots$, alternating between 0 and 1, wrapping around accordingly. Formally, using 0-based indexing, set $a_{(x+i) \bmod n} = i \bmod 2$ for all $i$ ($0 \le i \le n - 1$).
    136 * If $n$ is odd or if $x - y$ is even, set $a_x = 2$.
    137 
    138 Why this works:
    139 
    140 * If $n$ is even and $x - y$ is odd, all $0$'s are only friends with $1$'s and vice versa.
    141 * If $n$ is odd, $a_x$ will be adjacent to $0$ and $1$, so we set $a_x = 2$. Now $a$ is valid ignoring the extra friendship. Adding in the extra friendship, $a$ is still valid since $a_x = 2 \gt a_y$, so it will not affect $a_y$.
    142 * If $n$ is even and $x - y$ is even, the extra friendship connects two $0$ or two $1$. Setting $a_x = 2$ works because dragon $x$'s friends still have another neighbor to maintain their $\operatorname{MEX}$.
    143 
    144 **Solution**
    145 
    146 ```
    147 #include <iostream>
    148 #include <vector>
    149 using namespace std;
    150 
    151 void solve() {
    152     int n, x, y;
    153     cin >> n >> x >> y;
    154     --x; --y;
    155     vector<int> ans(n);
    156     for (int i = 0; i < n; ++i) ans[(x + i) % n] = i % 2;
    157     if (n % 2 || (x - y) % 2 == 0)
    158         ans[x] = 2;
    159     for (auto x : ans)cout << x << ' ';
    160     cout << endl;
    161 }
    162 
    163 int main() {
    164     int T;
    165     cin >> T;
    166     while (T--) solve();
    167 }
    168 ```
    169 
    170 [2049D - Shift + Esc](/contest/2049/problem/D "Codeforces Round 994 (Div. 2)")
    171 
    172 Idea: [Evirir](/profile/Evirir "Master Evirir") and [Kaey](/profile/Kaey "Grandmaster Kaey")  
    173  Solution: [CSQ31](/profile/CSQ31 "Candidate Master CSQ31"), [Evirir](/profile/Evirir "Master Evirir"), [Kaey](/profile/Kaey "Grandmaster Kaey")  
    174  Preparation: [Evirir](/profile/Evirir "Master Evirir") and [CSQ31](/profile/CSQ31 "Candidate Master CSQ31")
    175 
    176 **Tutorial**
    177 
    178 ### [2049D - Shift + Esc](/contest/2049/problem/D "Codeforces Round 994 (Div. 2)")
    179 
    180 Let $f(i,j)$ be the minimum cost to move to cell $(i,j)$ after shifting and $g(i,j,x)$ be the minimum cost to move to $(i,j)$ assuming row $i$ is shifted to the left by $x$.
    181 
    182 For simplicity sake, we will add a row with all zeros above the first row. Also note that the operations with states denoting columns are all under modulo $m$, I am omitting the notation to avoid clutter.
    183 
    184 The transitions are as follows:
    185 
    186 Base cases:
    187 
    188 $\begin{align} f(0,j) &= 0 \quad (0 \leq j \lt m) \\ g(0,j,x) &= kx \quad (0 \leq j,x \lt m) \end{align}$
    189 
    190 From row $i$ to row $i+1$:
    191 
    192 $\begin{align} g(i,j,x) &= \min(f(i-1,j)+kx,g(i,j-1,x)) + a(i,j+x) \quad (*)\\ f(i,j) &= \displaystyle\min_{x}g(i,j,x) \end{align}$
    193 
    194 In $(*)$, the $f(i-1,j)$ term is from the case where you move from $(i-1,j)$ to $(i,j)$. Similarly the $g(i,j-1,x)$ term is from the case where you move from $(i,j-1)$ to $(i,j)$.
    195 
    196 The final answer is $f(n,m-1)$. The overall complexity is $O(nm^2)$.
    197 
    198 **Solution**
    199 
    200 ```
    201 #include<bits/stdc++.h>
    202 using namespace std;
    203 typedef long long int ll;
    204 ll dp[511][511],a[511][511];
    205 
    206 void solve()
    207 {
    208     int n,m,k;
    209     cin>>n>>m>>k;
    210     for(int i=1;i<=n;i++){
    211         for(int j=0;j<m;j++)cin>>a[i][j];
    212     }
    213     for(int i=0;i<=n;i++){
    214         for(int j=0;j<m;j++)dp[i][j] = 1e18;
    215     }
    216 
    217     dp[0][0] = 0;
    218     for(int i=1;i<=n;i++){
    219         for(int shift = 0;shift<m;shift++){
    220             vector<ll>tmp(m,1e18);
    221             for(int j=0;j<m;j++)tmp[j] = dp[i-1][j] + a[i][(j+shift)%m] + k*1LL*shift;
    222 
    223             for(int j=0;j<m;j++)tmp[j] = min(tmp[j],tmp[(j+m-1)%m] + a[i][(j+shift)%m]);
    224             for(int j=0;j<m;j++)tmp[j] = min(tmp[j],tmp[(j+m-1)%m] + a[i][(j+shift)%m]);
    225             for(int j=0;j<m;j++)dp[i][j] = min(dp[i][j],tmp[j]);
    226         }
    227         //for(int j=0;j<m;j++)cout<<dp[i][j]<<" ";
    228        // cout<<'\n';
    229     }
    230     cout<<dp[n][m-1]<<endl;
    231 }
    232 
    233 int main()
    234 {
    235     int t; cin>>t;
    236     for (int i = 0; i < t; i++) solve();
    237 }
    238 ```
    239 
    240 [2049E - Broken Queries](/contest/2049/problem/E "Codeforces Round 994 (Div. 2)")
    241 
    242 Idea & preparation: [Evirir](/profile/Evirir "Master Evirir")  
    243  Solution: [Kaey](/profile/Kaey "Grandmaster Kaey")
    244 
    245 **Tutorial**
    246 
    247 ### [2049E - Broken Queries](/contest/2049/problem/E "Codeforces Round 994 (Div. 2)")
    248 
    249 Make 2 queries $[1, n/4]$ and $[n/4+1, n/2]$. This tells us which half the 1 is in: it is in $[1, n / 2]$ if the query results are different and $[n / 2 + 1, n]$ otherwise.
    250 
    251 Make 1 query: query $[1, n/2]$ if the 1 is in it or $[n/2+1, n]$ otherwise. This tells us that $k \lt n / 2$ if the result is $1$ and $k \ge n / 2$ otherwise.
    252 
    253 Without loss of generality, assume that the 1 is in $[1, n / 2]$. Now we can binary search for $k$ in $[1, n / 2]$ or $[n / 2 + 1, n]$. Let $k'$ be our guess.
    254 
    255 * If $k \lt n / 2$, query $[n / 2 + 1, n / 2 + k']$. The result is $1$ if $k' \ge k$ and $0$ otherwise.
    256 * If $k \ge n / 2$, query $[1, k']$. The result is $0$ if $k' \ge k$ and $1$ otherwise.
    257 
    258 In both cases, the binary search takes $\log n - 1 \le 29$ queries. Overall, this takes at most $2 + 1 + 29 = 32$ queries.
    259 
    260 The limit of $33$ queries (instead of $32$) is to allow less optimized solutions and other solutions. For example, one can instead do 3 queries in the beginning $[1, n / 4]$, $[n / 4 + 1, n / 2]$, $[n / 2 + 1, 3n / 4]$ to determine which quarter the 1 is in.
    261 
    262 **Solution**
    263 
    264 ```
    265 #include <bits/stdc++.h>
    266 using namespace std;
    267 
    268 int qry(int l, int r, bool rev = 0, int n = 0) {
    269     if (rev) {
    270         int t = n - l;
    271         l = n - r;
    272         r = t;
    273     }
    274     cout << "? " << l + 1 << ' ' << r << endl;
    275     cin >> r;
    276     return r;
    277 }
    278 
    279 void solve() {
    280     int n;
    281     cin >> n;
    282     int a = qry(0, n / 4);
    283     int b = qry(n / 4, n / 2);
    284     bool kSmall = 1;
    285     bool firstHalf = 1;
    286     if (a == b) firstHalf = 0;
    287     int bs = 0;
    288     if (qry(0, n / 2, firstHalf, n) == 0) kSmall = 0;
    289     if (kSmall) {
    290         for (int k = n / 4; k; k /= 2)
    291             if (qry(0, bs + k, firstHalf, n) == 0) bs += k;
    292     } else {
    293         bs = n / 2 - 1;
    294         for (int k = n / 4; k; k /= 2)
    295             if (qry(0, bs + k, 1-firstHalf, n) == 1) bs += k;
    296     }
    297     cout << "! " << bs + 1 << endl;
    298 }
    299 
    300 int main() {
    301     int T = 1;
    302     cin >> T;
    303     while (T--) solve();
    304     return 0;
    305 }
    306 ```
    307 
    308 [2049F - MEX OR Mania](/contest/2049/problem/F "Codeforces Round 994 (Div. 2)")
    309 
    310 Idea & preparation: [YouKn0wWho](/profile/YouKn0wWho "Candidate Master YouKn0wWho")
    311 
    312 **Tutorial**
    313 
    314 ### [2049F - MEX OR Mania](/contest/2049/problem/F "Codeforces Round 994 (Div. 2)")
    315 
    316 Let's figure out when a sequence is good. Let $m$ be the maximum element of the sequence. Notice that the bitwise OR of the sequence is at least $m$ and as MEX $-$ OR $=1$, that means MEX has to be at least $m + 1$. Which means all elements from $0$ to $m$ has to be present in the sequence. As MEX can't be greater than $m + 1$, the MEX has to be exactly $m + 1$.
    317 
    318 Now we need to check for which $m$ the bitwise OR of the elements from $0$ to $m$ is exactly $m$. It's not hard to see that this is true for $m = 2^k - 1$ for some integer $k \geq 0$. The reason is that all bits from $0$ to $k - 1$ have to be set in $m$ for the OR to be $m$ and it's only possible if $m$ is of the form $2^k - 1$.
    319 
    320 So, a sequence is good if the maximum element is $m = 2^k - 1$ for some integer $k$ and all elements from $0$ to $m$ are present in the sequence.
    321 
    322 Now, let's see how to answer the queries without any updates. To find the longest good subarray, we can use a two-pointers approach. But a better way to do this is to fix the power $k (0 \leq k \leq \log_2 n)$ and find the longest good subarray with maximum element $2^k - 1$. To do this, ignore the elements greater than $2^k - 1$ and then split the array into segments of consecutive numbers where each segment has elements from $0$ to $2^k - 1$. To check if a segment is good, we can track the number of distinct elements in the segment. If the number of distinct elements is $2^k$, then the segment is good.
    323 
    324 So to sum it up, for each power $k$, we will track some segments/components and the number of distinct elements in them and also the lengths of the segments to get the longest one during queries.
    325 
    326 Now regarding the updates, it is hard to track everything if we do the updates normally. But its's easier if we look at them in reverse order!
    327 
    328 Then each update will be decreasing the value of $a_i$ by $x$. Then for each power $k$, we will have to add a new element to a component or merge two components. For tracking distinct elements, we can use a map or unordered map and to merge we can use DSU with small to large merging. And that's pretty much it.
    329 
    330 Please check my code for more details.
    331 
    332 Overall complexity is $O((n + q) \log^2 n)$ or $O((n + q) \log^3 n)$ depending on if you use an unordered map or a map.
    333 
    334 **Solution**
    335 
    336 ```
    337 #include<bits/stdc++.h>
    338 using namespace std;
    339  
    340 const int N = 1e5 + 9, Q = 3e5 + 9;
    341 using ll = long long;
    342  
    343 struct GoodSet { // insert, erase and track distinct and total elements
    344   map<int, int> mp;
    345   int size;
    346   int k;
    347   GoodSet() {}
    348   GoodSet(int _k): k(_k), size(0) { };
    349   void insert(int x, int c = 1) {
    350     mp[x] += c;
    351     size += c;
    352   }
    353   void erase(int x) {
    354     if (mp[x] == 1) {
    355       mp.erase(x);
    356     }
    357     else {
    358       mp[x]--;
    359     }
    360     size -= 1;
    361   }
    362   void merge(GoodSet oth) {
    363     for (auto [x, c]: oth.mp) {
    364       insert(x, c);
    365     }
    366   }
    367   bool is_good() { // check if all elements from 0 to 2^k - 1 exists in the set
    368     return (int) mp.size() == (1 << k);
    369   }
    370   int get_value() {
    371     if (is_good()) return size;
    372     return 0;
    373   }
    374 };
    375  
    376 struct MaxSet { // insert, erase and track max element
    377   map<int, int> mp;
    378   MaxSet() {}
    379   void insert(int x) {
    380     mp[x]++;
    381   }
    382   void erase(int x) {
    383     mp[x]--;
    384     if (mp[x] == 0) mp.erase(x);
    385   }
    386   int get_max() {
    387     return mp.rbegin() -> first;
    388   }
    389 };
    390  
    391 struct DSU { // DSU for each power of 2
    392   int n;
    393   int k;
    394   vector<int> par;
    395   vector<GoodSet> comp;
    396   MaxSet good_lengths;
    397   DSU() {}
    398   DSU(int _n, int _k): n(_n), k(_k) {
    399     par.resize(n + 1);
    400     comp.resize(n + 1);
    401     for (int i = 1; i <= n; i++) {
    402       par[i] = i;
    403       comp[i] = GoodSet(k);
    404       good_lengths.insert(comp[i].get_value());
    405     }
    406   }
    407   int find(int u) {
    408     return par[u] = (par[u] == u ? u : find(par[u]));
    409   }
    410   void merge(int u, int v) {
    411     u = find(u); v = find(v);
    412     if (u == v) return;
    413     good_lengths.erase(comp[u].get_value());
    414     good_lengths.erase(comp[v].get_value());
    415  
    416     // small to large merging
    417     if (comp[u].mp.size() < comp[v].mp.size()) {
    418       comp[u].mp.swap(comp[v].mp);
    419       swap(comp[u].size, comp[v].size);
    420     }
    421     comp[u].merge(comp[v]);
    422     comp[v].mp.clear(); // clear to save up memory
    423  
    424     good_lengths.insert(comp[u].get_value());
    425     par[v] = u;
    426   }
    427   // insert or erase an element from the component that u belongs to
    428   void update_in_component(int u, int x, bool insert = true) {
    429     u = find(u);
    430     good_lengths.erase(comp[u].get_value());
    431     if (insert) comp[u].insert(x);
    432     else comp[u].erase(x);
    433     good_lengths.insert(comp[u].get_value());
    434   }
    435 };
    436 DSU f[18];
    437 ll a[N]; // make it long long as total sum can be huge
    438 int id[Q], x[Q], ans[Q];
    439 void solve() {
    440   int n, q; cin >> n >> q;
    441   for (int i = 1; i <= n; i++) {
    442     cin >> a[i];
    443   }
    444   for (int i = 1; i <= q; i++) {
    445     cin >> id[i] >> x[i];
    446     a[id[i]] += x[i];
    447   }
    448   MaxSet se;
    449   for (int k = 0; (1 << k) <= n; k++) {
    450     f[k] = DSU(n, k);
    451     for (int i = 1; i <= n; i++) {
    452       if (a[i] < (1 << k)) {
    453         f[k].update_in_component(i, a[i], true);
    454       }
    455     }
    456     for (int i = 2; i <= n; i++) {
    457       if (a[i] < (1 << k) and a[i - 1] < (1 << k)) {
    458         f[k].merge(i - 1, i);
    459       }
    460     }
    461     se.insert(f[k].good_lengths.get_max());
    462   }
    463   for (int qid = q; qid >= 1; qid--) {
    464     ans[qid] = se.get_max();
    465     int i = id[qid], sub = x[qid];
    466     for (int k = 0; (1 << k) <= n; k++) {
    467       se.erase(f[k].good_lengths.get_max());
    468  
    469       if (a[i] < (1 << k)) f[k].update_in_component(i, a[i], false);
    470       if (a[i] - sub < (1 << k)) f[k].update_in_component(i, a[i] - sub, true);
    471  
    472       if (a[i] >= (1 << k) and a[i] - sub < (1 << k)) {
    473         if (i > 1 and a[i - 1] < (1 << k)) {
    474           f[k].merge(i - 1, i);
    475         }
    476         if (i + 1 <= n and a[i + 1] < (1 << k)) {
    477           f[k].merge(i, i + 1);
    478         }
    479       }
    480  
    481       se.insert(f[k].good_lengths.get_max());
    482     }
    483     a[i] -= sub;
    484   }
    485  
    486   for (int i = 1; i <= q; i++) {
    487     cout << ans[i] << '\n';
    488   }
    489 }
    490  
    491 int32_t main() {
    492   ios_base::sync_with_stdio(0);
    493   cin.tie(0);
    494   int t = 1;
    495   cin >> t;
    496   while (t--) {
    497     solve();
    498   }
    499   return 0;
    500 }
    501 ```