2266.md (24149B)
1 Source: https://codeforces.com/blog/entry/156984 2 3 Thanks for participating in [Codeforces Round 1122 (Div. 3)](/contest/2266 "Codeforces Round 1122 (Div. 3)")! 4 5 **Rate the contest!** 6 7 **Quality** 8 9 * Excellent contest 10 * Good contest 11 * Average contest 12 * Bad contest 13 * Horrible contest 14 15 **Difficulty** 16 17 * Trivial contest 18 * Easy contest 19 * Average contest 20 * Hard contest 21 * Impossible contest 22 23 [2266A - Good Contest](/contest/2266/problem/A "Codeforces Round 1122 (Div. 3)") 24 25 **Hint** 26 27 How many participants can possibly have solved all three problems? 28 29 **Solution** 30 31 At most $\min(a_1,a_2,a_3)$ participants could have solved all three problems. This is achievable by making the same $\min(a_1,a_2,a_3)$ participants solve every problem, then distributing the remaining solves arbitrarily. 32 33 Thus, the answer is $n-\min(a_1,a_2,a_3)$. 34 35 The complexity is $O(1)$ per test case. 36 37 **Code (C++)** 38 39 ``` 40 #include <bits/stdc++.h> 41 using namespace std; 42 43 void solve() { 44 int N; cin >> N; 45 int a, b, c; cin >> a >> b >> c; 46 int m = min({a,b,c}); 47 cout << N-m << endl; 48 } 49 50 int main() { 51 int T; cin >> T; 52 while (T--) {solve();} 53 } 54 ``` 55 56 **Rate the problem!** 57 58 **Difficulty** 59 60 * Trivial problem 61 * Easy problem 62 * Average problem 63 * Hard problem 64 * Impossible problem 65 66 **Quality** 67 68 * Excellent problem 69 * Good problem 70 * Average problem 71 * Bad problem 72 * Horrible problem 73 74 [2266B - Three Piles](/contest/2266/problem/B "Codeforces Round 1122 (Div. 3)") 75 76 **Hint 1** 77 78 Consider the cases $a\geq b$ and $a \lt b$ separately. 79 80 **Hint 2** 81 82 If Alice ever takes stones, she should take all of them. 83 84 **Solution** 85 86 If $a\geq b$, Alice takes all $c$ stones immediately. There is nothing left for Bob to use to reduce her lead, so the score is $a+c-b$. 87 88 Now suppose $a \lt b$. Alice can take $0$ stones, and Bob will also take $0$ because he is already ahead and taking more stones would only increase the score. This gives $b-a$. Otherwise, Alice should take all $c$ stones at once. Taking only part of them gives a difference between the two cases of taking none and taking all, so it cannot be better than both. Taking all gives $|a+c-b|$. 89 90 If $a+c \lt b$, this is smaller than $b-a$. Otherwise, it equals $a+c-b$. Therefore, the answer is $\max(|a-b|,a+c-b)$. 91 92 The complexity is $O(1)$ per test case. 93 94 **Code (C++)** 95 96 ``` 97 #include <bits/stdc++.h> 98 using namespace std; 99 100 void solve() { 101 int a, b, c; cin >> a >> b >> c; 102 cout << max(abs(a-b),(a+c-b)) << endl; 103 } 104 105 int main() { 106 int T; cin >> T; 107 while (T--) {solve();} 108 } 109 ``` 110 111 **Rate the problem!** 112 113 **Difficulty** 114 115 * Trivial problem 116 * Easy problem 117 * Average problem 118 * Hard problem 119 * Impossible problem 120 121 **Quality** 122 123 * Excellent problem 124 * Good problem 125 * Average problem 126 * Bad problem 127 * Horrible problem 128 129 [2266C - AND, OR, Sort!](/contest/2266/problem/C "Codeforces Round 1122 (Div. 3)") 130 131 **Hint 1** 132 133 If a prefix contains both $0$ and $1$, what are its bitwise AND and bitwise OR? 134 135 **Hint 2** 136 137 A sorted binary string is determined by one split point. 138 139 **Solution** 140 141 If a prefix contains both $0$ and $1$, its AND is $0$ and its OR is $1$, so its last character can be changed to either value. 142 143 If $s_1=1$, the first character can never change, so the final string must be all ones. Every zero can be changed using OR, giving the number of zeros as the answer. 144 145 Now suppose $s_1=0$. Fix the point after which the ones start. For a split after $i$, we need to change every one in $[1,i]$ and every zero in $[i+1,n]$. We can first change the required zeros on the right using OR, then change the required ones on the left using AND. A split inside the initial block of zeros is never better than moving it to the end of that block. 146 147 So, scan every split while maintaining the number of ones on the left and zeros on the right, and take the minimum. 148 149 The complexity is $O(n)$ per test case. 150 151 **Code (C++)** 152 153 ``` 154 #include <bits/stdc++.h> 155 using namespace std; 156 157 void solve() { 158 int N; cin >> N; 159 string s; cin >> s; 160 int z = 0; 161 int o = 0; 162 for (int i = 0; i < N; i++) {z+=(s[i]=='0');} 163 if (s[0]=='1') {cout << z << endl; return;} 164 int aa = 1e9; 165 for (int i = 0; i < N; i++) { 166 o+=(s[i]=='1'); 167 z-=(s[i]=='0'); 168 aa=min(aa,o+z); 169 } 170 cout << aa << endl; 171 } 172 173 int main() { 174 int T; cin >> T; 175 while (T--) {solve();} 176 } 177 ``` 178 179 **Rate the problem!** 180 181 **Difficulty** 182 183 * Trivial problem 184 * Easy problem 185 * Average problem 186 * Hard problem 187 * Impossible problem 188 189 **Quality** 190 191 * Excellent problem 192 * Good problem 193 * Average problem 194 * Bad problem 195 * Horrible problem 196 197 [2266D - Falling Concrete](/contest/2266/problem/D "Codeforces Round 1122 (Div. 3)") 198 199 **Hint 1** 200 201 Look at how the height and position of each section change after an operation. 202 203 **Hint 2** 204 205 A section moving one position to the right gains $1$ height, while a section moving one position to the left loses $1$ height. 206 207 **Solution** 208 209 During an operation, every section passed over moves one position to the right and gains $1$ height. The section being moved goes $j-i$ positions to the left and loses exactly $j-i$ height. Thus, for every section, $\text{height}-\text{position}$ never changes. The section initially at position $i$ therefore always keeps the value $a_i-i$. 210 211 We can also reorder the sections however we want by building the desired order from left to right and repeatedly moving the required section into the next position. 212 213 Suppose $k$ consecutive positions starting at $p$ are flat at height $h$. Their invariant values are $h-p,h-p-1,\ldots,h-p-k+1$, which are $k$ distinct consecutive integers. The reverse is also true: if $k$ sections have consecutive values $a_i-i$, placing them in decreasing order makes their heights equal. 214 215 Therefore, the answer is the longest consecutive run among the distinct values $a_i-i$. Put them in a set and scan in increasing order. 216 217 The complexity is $O(n\log n)$ per test case. 218 219 **Code (C++)** 220 221 ``` 222 #include <bits/stdc++.h> 223 using namespace std; 224 225 void solve() { 226 int N; cin >> N; 227 set<int> s; 228 for (int i = 1; i <= N; i++) { 229 int a; cin >> a; 230 s.insert(a-i); 231 } 232 int aa = 0; 233 int tt = 0; 234 int c = -1e9; 235 for (auto x : s) { 236 if (x!=c+1) {aa=max(aa,tt); tt=0;} 237 tt++; 238 c=x; 239 } 240 aa=max(aa,tt); 241 cout << aa << endl; 242 } 243 244 int main() { 245 int T; cin >> T; 246 while (T--) {solve();} 247 } 248 ``` 249 250 **Rate the problem!** 251 252 **Difficulty** 253 254 * Trivial problem 255 * Easy problem 256 * Average problem 257 * Hard problem 258 * Impossible problem 259 260 **Quality** 261 262 * Excellent problem 263 * Good problem 264 * Average problem 265 * Bad problem 266 * Horrible problem 267 268 [2266E - Prime Destruction](/contest/2266/problem/E "Codeforces Round 1122 (Div. 3)") 269 270 **Hint** 271 272 Use DP. Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$. 273 274 **Solution** 275 276 Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$. Clearly, $dp_i=0$ for $i\leq k$. 277 278 For $i \gt k$, suppose we choose a prime divisor $p$ of $i$. One operation gives us $p$ copies of $i/p$, and these copies can then be handled independently. Thus, $dp_i=\min_{p\mid i,\ p\text{ prime}}(1+p\cdot dp_{i/p})$. 279 280 Since $i/p \lt i$, compute the DP in increasing order. We can precompute the distinct prime divisors of every number with a sieve. Finally, the original elements are independent, so the answer is $\sum dp_{a_i}$. 281 282 The complexity is $O(n\log\log n)$ per test case after preprocessing. 283 284 **Bonus** 285 286 Can you solve the problem for all $f(1),f(2),\ldots,f(n)$? 287 288 This was actually the original version of the problem! 289 290 **Code (C++)** 291 292 ``` 293 #include <bits/stdc++.h> 294 using namespace std; 295 296 vector<long long> pf[200001]; 297 long long dp[200001]; 298 bool cmp[200001]; 299 300 void pre() { 301 for (long long i = 2; i <= 200000; i++) { 302 if (!cmp[i]) { 303 cmp[i]=true; 304 for (long long j = 2*i; j <= 200000; j+=i) { 305 pf[j].push_back(i); 306 cmp[j]=true; 307 } 308 pf[i].push_back(i); 309 } 310 } 311 } 312 313 void solve() { 314 long long N, K; cin >> N >> K; 315 long long aa = 0; 316 vector<long long> dp(N+1,1e18); 317 for (long long i = 1; i <= N; i++) { 318 if (i<=K) {dp[i]=0;} 319 for (auto x : pf[i]) {dp[i]=min(dp[i],dp[i/x]*x+1);} 320 } 321 for (long long i = 0; i < N; i++) { 322 long long a; cin >> a; 323 aa+=dp[a]; 324 } 325 cout << aa << endl; 326 } 327 328 int main() { 329 pre(); 330 long long T; cin >> T; 331 while (T--) {solve();} 332 } 333 ``` 334 335 **Rate the problem!** 336 337 **Difficulty** 338 339 * Trivial problem 340 * Easy problem 341 * Average problem 342 * Hard problem 343 * Impossible problem 344 345 **Quality** 346 347 * Excellent problem 348 * Good problem 349 * Average problem 350 * Bad problem 351 * Horrible problem 352 353 [2266F - MEX Replacement](/contest/2266/problem/F "Codeforces Round 1122 (Div. 3)") 354 355 **Hint 1** 356 357 Work backwards from one copy of the value you want to create. 358 359 **Hint 2** 360 361 Process the values from large to small, and let $q$ be the number of copies of the current value that you need. 362 363 **Hint 3** 364 365 If you need $q$ copies of $x$ but only have $c \lt q$, the missing $q-c$ copies of $x$ each force another copy of every smaller value. 366 367 **Solution** 368 369 We check whether a value $M$ can appear, then binary search the largest valid $M$. The largest initial value is already present, so only larger values need to be checked. 370 371 Work backwards from one copy of $M$. At first we need one copy of every value below it, so set $q=1$ and process the values downwards. Suppose we currently need $q$ copies of $x \gt 0$, and there are $c$ copies of $x$ in the initial multiset. If $c\geq q$, we use $q$ of them and have $c-q$ extras. If $c \lt q$, the missing $q-c$ copies of $x$ each require another copy of every smaller value. Thus, $q$ becomes $q+(q-c)=2q-c$. 372 373 So the transition is $q\leftarrow q+\max(0,q-c)$. Extra positive elements cannot save us at another positive level, but they can all be turned into zeros by taking them alone. We count these extras, and when we reach $0$, the check succeeds exactly when the initial zeros plus all extras are at least $q$. 374 375 Missing values are easy to skip. If there are $d$ missing values in a row, then $q$ doubles $d$ times, so multiply it by $2^d$ at once. We can also cap $q$ once it becomes larger than the total number of elements to avoid overflow. 376 377 If $M$ is possible, then every smaller value is also possible, since all of them have to exist while building $M$. Therefore, binary search works. After sorting the pairs, one check is $O(n)$. 378 379 The complexity is $O(n\log n+n\log C)$ per test case, where $C$ is the binary search range. 380 381 **Bonus** 382 383 Can you get a much smaller upper bound for the binary search? 384 385 **Bonus Answer** 386 387 Let $mx=\max x_i$. 388 389 You only need to search up to about $mx+50$. Once we go much further than $mx$, there are many consecutive missing values, and every missing value doubles $q$, so the required number of elements grows too quickly. 390 391 Thus, we can binary search only on $[mx,mx+50]$, giving $O(n\log 50)$ checks after sorting. 392 393 The exact proof and bound are left to the reader :) 394 395 **Code (C++)** 396 397 ``` 398 #include <bits/stdc++.h> 399 using namespace std; 400 401 bool check(long long mid, vector<pair<long long, long long>> &A) { 402 long long n = 1; 403 long long ex = 0; 404 long long p = mid; 405 for (long long i = 0; i < A.size(); i++) { 406 if (p-A[i].first+(63-__builtin_clzll(n))>60) {return false;} 407 n<<=(p-A[i].first-1); 408 if (!A[i].first) {ex+=A[i].second; break;} 409 if (A[i].second>n) {ex+=A[i].second-n;} 410 else {n=(n<<1)-A[i].second;} 411 p=A[i].first; 412 } 413 return (ex>=n); 414 } 415 416 void solve() { 417 long long N; cin >> N; 418 vector<pair<long long, long long>> A; 419 long long lo = 0; 420 long long hi = 1000000100; 421 for (long long i = 0; i < N; i++) { 422 long long a, b; cin >> a >> b; 423 A.push_back({a,b}); 424 lo=max(lo,a); 425 } 426 sort(A.rbegin(),A.rend()); 427 if (A.back().first) {A.push_back({0,0});} 428 while (lo<hi) { 429 long long mid = (lo+hi+1)/2; 430 if (check(mid,A)) {lo=mid;} 431 else {hi=mid-1;} 432 } 433 cout << lo << endl; 434 } 435 436 int main() { 437 long long T; cin >> T; 438 while (T--) {solve();} 439 } 440 ``` 441 442 **Rate the problem!** 443 444 **Difficulty** 445 446 * Trivial problem 447 * Easy problem 448 * Average problem 449 * Hard problem 450 * Impossible problem 451 452 **Quality** 453 454 * Excellent problem 455 * Good problem 456 * Average problem 457 * Bad problem 458 * Horrible problem 459 460 [2266G - Modular Tree](/contest/2266/problem/G "Codeforces Round 1122 (Div. 3)") 461 462 **Hint 1** 463 464 Process the tree from the leaves upward. 465 466 **Hint 2** 467 468 A node can always be brought back to its original value after changing it. 469 470 **Hint 3** 471 472 For every node $i$, its reachable values have the form $(a_i+g_ix)\bmod b_i$ for some integer $x$. Find $g_i$. 473 474 **Solution** 475 476 For every node $u$, let $g_u$ be such that its reachable values are exactly $(a_u+g_ux)\bmod b_u$. We compute $g_u$ from the leaves upward. 477 478 Suppose $v$ is a child of $u$. If $g_v=b_v$, then $v$ is fixed at $a_v$. Otherwise, its value can change from $a_v$ by multiples of $g_v$. Let $S_u$ be the sum of the initial values of all direct children of $u$. We can add $S_u$ to $u$ by leaving all children at their initial values, and every non-fixed child $v$ lets us vary this amount by multiples of $g_v$. Therefore, $g_u=\gcd(b_u,S_u,g_v\text{ for all non-fixed children }v)$. 479 480 For a leaf, this gives $g_u=b_u$, as expected. Once we know $g_u$, the largest reachable value is $a_u+\left\lfloor\frac{b_u-1-a_u}{g_u}\right\rfloor g_u$. 481 482 These maxima can all be achieved together. We can first set a node to its maximum, then continue working strictly inside its children's subtrees without changing that node. So after computing all $g_u$ bottom-up, we simply sum the maximum reachable value of every node. 483 484 The complexity is $O(n\log 10^9)$ per test case. 485 486 **Code (C++)** 487 488 ``` 489 #include <bits/stdc++.h> 490 using namespace std; 491 492 void dfs(long long node, long long par, vector<long long> &A, vector<long long> &B, vector<long long> &g, vector<vector<long long>> &adj) { 493 long long gc = 0; 494 long long tt = 0; 495 for (auto x : adj[node]) { 496 if (x != par) { 497 dfs(x,node,A,B,g,adj); 498 if (g[x]!=B[x]) {gc=gcd(gc,g[x]);} 499 tt+=A[x]; 500 } 501 } 502 gc=gcd(gc,tt); 503 gc=gcd(gc,B[node]); 504 g[node]=gc; 505 } 506 507 void solve() { 508 long long N; cin >> N; 509 vector<long long> A; A.push_back(-1); 510 vector<long long> B; B.push_back(-1); 511 vector<vector<long long>> adj(N+1); 512 for (long long i = 0; i < N; i++) { 513 long long a; cin >> a; 514 A.push_back(a); 515 } 516 for (long long i = 0; i < N; i++) { 517 long long a; cin >> a; 518 B.push_back(a); 519 } 520 for (long long i = 0; i < N-1; i++) { 521 long long a, b; cin >> a >> b; 522 adj[a].push_back(b); 523 adj[b].push_back(a); 524 } 525 vector<long long> g(N+1); //init to 0 for identity gcd 526 dfs(1,0,A,B,g,adj); 527 long long aa = 0; 528 for (long long i = 1; i <= N; i++) {aa+=((B[i]-A[i]-1)/g[i])*g[i]+A[i];} 529 cout << aa << endl; 530 } 531 532 int main() { 533 long long T; cin >> T; 534 while (T--) {solve();} 535 } 536 ``` 537 538 **Rate the problem!** 539 540 **Difficulty** 541 542 * Trivial problem 543 * Easy problem 544 * Average problem 545 * Hard problem 546 * Impossible problem 547 548 **Quality** 549 550 * Excellent problem 551 * Good problem 552 * Average problem 553 * Bad problem 554 * Horrible problem 555 556 [2266H - Deque Malfunction](/contest/2266/problem/H "Codeforces Round 1122 (Div. 3)") 557 558 **Hint 1** 559 560 We only need to keep one occurrence of every value $1,2,\ldots,n$. What can we do with every other occurrence? 561 562 **Hint 2** 563 564 Let $t_i$ be the arrival position of the occurrence of $i$ which stays in the final deque. When can $i$ be inserted without a malfunction? 565 566 **Hint 3** 567 568 An element can be inserted normally exactly when $t_i$ is a prefix minimum or a suffix minimum of $t_1,t_2,\ldots,t_n$. 569 570 **Hint 4** 571 572 Fix the position of the global minimum. The prefix minima and suffix minima can be optimized separately. 573 574 **Solution** 575 576 If some value from $1$ to $n$ never appears, the answer is $-1$. Otherwise, choose one occurrence of each value to keep. Every unused occurrence can simply be pushed to an end and immediately removed from that same end. 577 578 Let $t_i$ be the position of the chosen occurrence of $i$. We can push $i$ to the front normally exactly when every chosen value which arrived earlier is larger than $i$, or $t_i \lt \min(t_1,\ldots,t_{i-1})$. Similarly, we can push it to the back exactly when $t_i \lt \min(t_{i+1},\ldots,t_n)$. Thus, a value avoids a malfunction exactly when $t_i$ is a prefix minimum or a suffix minimum. The global minimum is counted in both, so if there are $L$ prefix minima and $R$ suffix minima, we keep $L+R-1$ values for free. 579 580 Now optimize the prefix minima. Process the values $1,2,\ldots,n$. Let $dp[p]$ be the maximum number of prefix minima so far when the smallest chosen arrival position is $p$. For an occurrence at position $t$, making it the new minimum gives $new[t]=1+\max_{p \gt t}dp[p]$. All of these transitions must be calculated before adding the states for the current value. 581 582 An old state with minimum $p$ can stay unchanged only if the current value has some occurrence after $p$. If $last_i$ is its last occurrence, every state with $p \gt last_i$ must therefore be deleted. For value $1$, every occurrence simply starts with value $1$. 583 584 After all values are processed, let $L[p]$ be the best number of prefix minima whose global minimum is at position $p$. Run the same DP with the values in reverse order to get $R[p]$ for suffix minima. For a fixed $p$, the two sides can be combined independently, sharing only the global minimum itself. Therefore, the maximum number of values which avoid a malfunction is $\max_p(L[p]+R[p]-1)$, and the answer is $n-\max_p(L[p]+R[p]-1)$. 585 586 **Implementation 1: Lazy Segment Tree** 587 588 Store the DP in a segment tree. For an occurrence $t$, the transition needs the maximum on $(t,m]$. After calculating all transitions for the current value, clear the suffix after $last_i$ and insert the new states. 589 590 A lazy segment tree supports the suffix clear and range maximum queries in $O(\log m)$, so the total complexity is $O(m\log m)$. 591 592 **Code (Lazy Segment Tree)** 593 594 ``` 595 #include <bits/stdc++.h> 596 using namespace std; 597 598 struct lst { //cur range add range max, change accordingly, no need for l,r in range add range mx 599 vector<int> seg; 600 vector<bool> tg; 601 vector<int> lz; 602 int sz = 1; 603 int id = 0; //change sent 604 int acc(int x, int y) {return max(x,y);} //other more complex lst can do range set and range add 605 void pull(int n) {seg[n]=acc(seg[n<<1],seg[(n<<1)|1]);} 606 void apply(int n, int l, int r, int v) {seg[n]=v; tg[n]=true; lz[n]=v;} //if something else, change id, acc, apply, and how lz accumulates/replaces in push 607 void push(int n, int l, int r) {if (!tg[n]) {return;} tg[n]=false; apply(n<<1,l,(l+r)/2,lz[n]); apply((n<<1)|1,(l+r)/2+1,r,lz[n]); lz[n]=0;} 608 lst(vector<int> A) { //inp 0 index 609 while (sz<A.size()) {sz<<=1;} 610 seg.assign(2*sz,id); 611 tg.assign(2*sz,false); //in case 0 is a range set 612 lz.assign(2*sz,0); 613 for (int i = 0; i < A.size(); i++) {seg[sz+i]=A[i];} 614 for (int i = sz-1; i >= 1; i--) {pull(i);} 615 } 616 int qq(int n, int l, int r, int sl, int sr) { 617 if (sl>r||sr<l) {return id;} 618 if (l<=sl&&sr<=r) {return seg[n];} 619 push(n,sl,sr); 620 return acc(qq(n<<1,l,r,sl,(sl+sr)/2),qq((n<<1)|1,l,r,(sl+sr)/2+1,sr)); 621 } 622 void uu(int n, int l, int r, int sl, int sr, int v) { 623 if (sl>r||sr<l) {return;} 624 if (l<=sl&&sr<=r) {apply(n,sl,sr,v); return;} 625 push(n,sl,sr); 626 uu(n<<1,l,r,sl,(sl+sr)/2,v); 627 uu((n<<1)|1,l,r,(sl+sr)/2+1,sr,v); 628 pull(n); 629 } 630 int q(int l, int r) {return qq(1,l,r,1,sz);} 631 void u(int l, int r, int v) {uu(1,l,r,1,sz,v);} 632 }; 633 634 void solve() { 635 int N, M; cin >> N >> M; 636 vector<int> A; 637 for (int i = 0; i < N; i++) { 638 A.push_back(i+1); 639 } 640 vector<vector<int>> tt(N+1); 641 vector<int> ndp1(M+1); 642 for (int i = 1; i <= M; i++) { 643 int a; cin >> a; 644 tt[a].push_back(i); 645 } 646 for (int i = 1; i <= N; i++) { 647 if (tt[i].empty()) {cout << -1 << endl; return;} 648 } 649 vector<int> ii(M+1); // one sentinel at end so no RE 650 lst dp1(ii); 651 bool f = true; 652 for (auto x : A) { 653 for (auto t : tt[x]) { 654 int rr = dp1.q(t+1,M+1); 655 ndp1[t]=(rr?rr+1:rr+(f)); 656 } 657 for (auto t : tt[x]) { 658 dp1.u(t,t,ndp1[t]); 659 } 660 dp1.u(tt[x].back()+1,M+1,0); 661 if (f) {f=false;} 662 } 663 vector<int> ndp2(M+1); 664 reverse(A.begin(),A.end()); 665 lst dp2(ii); 666 f=true; 667 for (auto x : A) { 668 for (auto t : tt[x]) { 669 int rr = dp2.q(t+1,M+1); 670 ndp2[t]=(rr?rr+1:rr+(f)); 671 } 672 for (auto t : tt[x]) { 673 dp2.u(t,t,ndp2[t]); 674 } 675 dp2.u(tt[x].back()+1,M+1,0); 676 if (f) {f=false;} 677 } 678 int aa = 0; 679 for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);} 680 cout << N-aa << endl; 681 } 682 683 int main() { 684 int T; cin >> T; 685 while (T--) {solve();} 686 } 687 ``` 688 689 **Implementation 2: Amortized Set Deletion** 690 691 We can also use a normal segment tree together with a set of active positions. Whenever a state with position greater than $last_i$ becomes invalid, remove the largest such position from the set and set its segment tree value to $0$. 692 693 Each position is inserted once and deleted at most once in one pass, so there are only $O(m)$ deletions in total. The total complexity is again $O(m\log m)$. 694 695 **Code (Amortized Set Deletion)** 696 697 ``` 698 #include <bits/stdc++.h> 699 using namespace std; 700 701 struct tri { //inp zero index vector, transformed to 1 index 702 vector<int> s; 703 int sz = 1; 704 tri(vector<int> &A) { 705 while (sz<A.size()) {sz<<=1;} 706 s.assign(2*sz,0); 707 for (int i = 0; i < A.size(); i++) {s[i+sz] = A[i];} 708 for (int i = sz-1; i >= 1; i--) {s[i]=max(s[i<<1],s[(i<<1)|1]);} 709 } 710 void u(int i, int x) { 711 int p = sz+i-1; s[p] = x; 712 for (p>>=1; p; p>>=1) {s[p]=max(s[p<<1],s[(p<<1)|1]);} 713 } 714 int aa(int n, int l, int r, int sl, int sr) { 715 if (l<=sl&&sr<=r) {return s[n];} 716 else if (sr<l||sl>r) {return 0;} 717 else {return max(aa(n<<1,l,r,sl,(sl+sr)>>1),aa((n<<1)|1,l,r,((sl+sr)>>1)+1,sr));} 718 } 719 int q(int l, int r) {return aa(1,l,r,1,sz);} 720 }; 721 722 void solve() { 723 int N, M; cin >> N >> M; 724 vector<int> A; 725 for (int i = 0; i < N; i++) { 726 A.push_back(i+1); 727 } 728 vector<vector<int>> tt(N+1); 729 vector<int> ndp1(M+1); 730 for (int i = 1; i <= M; i++) { 731 int a; cin >> a; 732 tt[a].push_back(i); 733 } 734 for (int i = 1; i <= N; i++) { 735 if (tt[i].empty()) {cout << -1 << endl; return;} 736 } 737 vector<int> ii(M+1); // one sentinel at end so no RE 738 tri dp1(ii); 739 set<int> act; 740 bool f = true; 741 for (auto x : A) { 742 for (auto t : tt[x]) { 743 int rr = dp1.q(t+1,M+1); 744 ndp1[t]=(rr?rr+1:rr+(f)); 745 } 746 for (auto t : tt[x]) { 747 dp1.u(t,ndp1[t]); 748 act.insert(t); 749 } 750 while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp1.u((*act.rbegin()),0); act.erase(*act.rbegin());} 751 if (f) {f=false;} 752 } 753 vector<int> ndp2(M+1); 754 act.clear(); 755 reverse(A.begin(),A.end()); 756 tri dp2(ii); 757 f=true; 758 for (auto x : A) { 759 for (auto t : tt[x]) { 760 int rr = dp2.q(t+1,M+1); 761 ndp2[t]=(rr?rr+1:rr+(f)); 762 } 763 for (auto t : tt[x]) { 764 dp2.u(t,ndp2[t]); 765 act.insert(t); 766 } 767 while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp2.u((*act.rbegin()),0); act.erase(*act.rbegin());} 768 if (f) {f=false;} 769 } 770 int aa = 0; 771 for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);} 772 cout << N-aa << endl; 773 } 774 775 int main() { 776 int T; cin >> T; 777 while (T--) {solve();} 778 } 779 ``` 780 781 **Rate the problem!** 782 783 **Difficulty** 784 785 * Trivial problem 786 * Easy problem 787 * Average problem 788 * Hard problem 789 * Impossible problem 790 791 **Quality** 792 793 * Excellent problem 794 * Good problem 795 * Average problem 796 * Bad problem 797 * Horrible problem