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