2166.md (25611B)
1 Source: https://codeforces.com/blog/entry/148452 2 3 [2166A — Same Difference](https://codeforces.com/contest/2166/problem/A) 4 5 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n") 6 7 **Tutorial** 8 9 It can be observed that $s_n$ will not change throughout the operations, therefore, for the final string to have every character the same, every character must be equal to $s_n$. 10 11 To change every character to $s_n$, we can iterate over all characters from right to left, repeatedly setting $s_{i-1}\leftarrow s_i$ if $s_{i-1}\neq s_n$. Through this, we can need one operation for every character not equal to $s_n$, which is also obvious as a lower bound. 12 13 Time complexity: $O(n)$. 14 15 **Solution** 16 17 ``` 18 #include <bits/stdc++.h> 19 20 using namespace std; 21 22 char s[100005]; 23 24 int main() 25 { 26 int n, t, i, m; 27 scanf("%d", &t); 28 while(t--) 29 { 30 scanf("%d", &n); 31 scanf("%s", s + 1); 32 m = 0; 33 for(i = 1; i < n; i++) 34 m += (s[i] != s[n]); 35 printf("%d\n", m); 36 } 37 return 0; 38 } 39 ``` 40 41 [2166B — Tab Closing](https://codeforces.com/contest/2166/problem/B) 42 43 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n") 44 45 The problem statement arised naturally from closing tabs in any modern browser. 46 47 **Tutorial** 48 49 After some experimenting, it can be seen that the answer does not exceed $2$. Simply click at $a$ as long as there's still a tab at that point. After that, each tab must have length of $b$, move the cursor to $b$, and click until all tabs have been closed. 50 51 Now it remains to be seen under what scenarios we can achieve $1$ move. Since the last tab closed will have length $b$, our cursor should be moved to $b$. Therefore, the answer will be $1$ when $nb\le a$, or $b=a$, and $2$ otherwise. 52 53 Remember to use long long if using multiplication to calculate $nb$. 54 55 Time Complexity: $O(1)$ per test case. 56 57 **Solution** 58 59 ``` 60 #include <bits/stdc++.h> 61 62 using namespace std; 63 64 int main() 65 { 66 int t, n, a, b; 67 scanf("%d", &t); 68 while(t--) 69 { 70 scanf("%d%d%d", &a, &b, &n); 71 printf(((long long)b * n <= a || b >= a) ? "1\n" : "2\n"); 72 } 73 return 0; 74 } 75 ``` 76 77 [2165A — Cyclic Merging](https://codeforces.com/contest/2165/problem/A) 78 79 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n") 80 81 **Tutorial** 82 83 We consider a simple strategy: repeatedly merge the smallest element onto the smaller of its two neighbours. 84 85 We will prove this greedy is correct: For any merge sequence, consider the smallest element $mn$, it must be merged into a larger element at some point in the future. However, its neighbour will not be smaller, which means that we can simply modify the merge sequence to merge $mn$ into its neighbours at the very first. 86 87 Further observation will show that this value is equal to $\sum_{i=1}^{n-1}\max(a_i,a_{i+1})+\max(a_n,a_1)-\max({a_1,a_2,\cdots,a_n})$. A brief sketch of the proof is as follows: It can be shown that we can break the ring into a sequence at an arbitrary maxima, since the maxima will not be merged into others. 88 89 For the problem on a sequence, consider each element $a_i$, find the closest element $a_x$ to the left of $a_i$, such that $a_x \gt a_i$ (when equal, break ties according to index). If there are elements between $a_x$ and $a_i$, then it's clear that in performing the aforementioned greedy, at some point we will merge everything in $a_{x+1},a_{x+2},\cdots,a_i$ into a single element, and then merge it into $a_i$. Therefore the answer will be increased by $a_i$ if $a_{i-1} \lt a_i$. The same thing will happen to the right of $a_i$. Therefore the answer is $\sum_{i=1}^{n-1}[a_i\ge a_{i+1}]a_i+[a_i \lt a_{i+1}]a_{i+1}$, which can be rephrased as $\sum_{i=1}^{n-1}\max(a_i,a_{i+1})$, which in turn is the formula above. 90 91 However, this is not needed to pass the problem. We expected participants to pass using doubly linked lists, sets, or any other data structures which can support the operations needed. 92 93 Time Complexity: $O(n)$ or $O(n\log n)$. 94 95 **Solution** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 typedef long long ll; 102 103 const int N = 1e6 + 5; 104 ll a[N]; 105 106 int main() 107 { 108 int t, n, m, i; 109 ll k; 110 scanf("%d", &t); 111 while(t--) 112 { 113 scanf("%d", &n); 114 m = 0; 115 for(i = 0; i < n; i++) 116 { 117 scanf("%lld", a + i); 118 if(a[i] > a[m]) 119 m = i; 120 } 121 a[n] = a[0]; 122 k = -a[m]; 123 for(i = 0; i < n; i++) 124 k += max(a[i], a[i + 1]); 125 printf("%lld\n", k); 126 } 127 return 0; 128 } 129 ``` 130 131 **Solution (linked lists, by Arpa)** 132 133 ``` 134 // In the name of Allah. 135 136 #include <bits/stdc++.h> 137 using namespace std; 138 139 140 int main() { 141 ios::sync_with_stdio(false); 142 cin.tie(nullptr); 143 int t; 144 cin >> t; 145 while (t--) { 146 int n; 147 cin >> n; 148 list<int> alive; 149 int a[n]; 150 list<int>::iterator w[n]; 151 auto c_next = [&alive](const list<int>::iterator& it) { 152 return next(it) == alive.end() ? alive.begin() : next(it); 153 }; 154 auto c_prev = [&alive](const list<int>::iterator& it) { 155 return it == alive.begin() ? --alive.end() : prev(it); 156 }; 157 auto hole = [&](const list<int>::iterator& it) { 158 return a[*it] <= min(a[*c_next(it)], a[*c_prev(it)]); 159 }; 160 for (int i = 0; i < n; ++i) { 161 cin >> a[i]; 162 w[i] = alive.insert(alive.end(), i); 163 } 164 queue<int> q; 165 { 166 int i = 0; 167 for (auto it = alive.begin(); it != alive.end(); ++it, ++i) 168 if (hole(it)) 169 q.push(i); 170 } 171 long long ans = 0; 172 bool mark[n] = {}; 173 while (alive.size() > 1) { 174 auto i = q.front(); 175 q.pop(); 176 if (mark[i]) 177 continue; 178 mark[i] = true; 179 auto it = w[i]; 180 ans += min(a[*c_next(it)], a[*c_prev(it)]); 181 auto jt = c_next(it); 182 alive.erase(it); 183 it = jt; 184 if (hole(it)) 185 q.push(*it); 186 it = c_prev(it); 187 if (hole(it)) 188 q.push(*it); 189 } 190 cout << ans << '\n'; 191 } 192 } 193 ``` 194 195 [2165B — Marble Council](https://codeforces.com/contest/2165/problem/B) 196 197 idea & solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire") 198 199 **Tutorial** 200 201 For a multiset $S$, we will find a check to determine whether it can be generated. 202 203 For each color $x$ not in $S$, we need to somehow "hide" all of the $x$'s in other sets. That is, for every partitioned set, the occurrence of $x$ must be less than or equal to the occurrence of the modes. 204 205 For each color $c$ in $S$, no matter how many times $c$ appeared in $S$, or how we partition these $c$ into different sets, the color $c$ can provide at most $cnt_c$ "chances" to hide an element of $x$. 206 207 Therefore, $cnt_x\le\sum_{c\in S}cnt_c$ must hold. 208 209 It is easy to construct a partition once this condition is held for all $x$. Thus, we only need to count sets that satisfy $\max_{x\not\in S} cnt_x\le\sum_{c\in S} cnt_c$. 210 211 This is a simple knapsack dp problem from here, you can either add elements in increasing order of $cnt$ and keep track if the last color is used at all, or observe that the condition is just $\sum_{c\in S}cnt_c\ge\max cnt$, and just running a completely vanilla knapsack dp. 212 213 Time Complexity: $O(n^2)$. 214 215 **Solution (By ZhouYuHang)** 216 217 ``` 218 #include <bits/stdc++.h> 219 using namespace std; 220 221 const int N = 5e3 + 5, P = 998244353; 222 223 int n; 224 int a[N], cnt[N]; 225 int dp[N]; 226 227 void solve() { 228 cin >> n; 229 for (int i = 1; i <= n; ++i) cin >> a[i]; 230 231 memset(cnt, 0, sizeof cnt); 232 int max_cnt = 0; 233 for (int i = 1; i <= n; ++i) { 234 max_cnt = max(max_cnt, ++cnt[a[i]]); 235 } 236 237 memset(dp, 0, sizeof dp), dp[0] = 1; 238 for (int i = 1; i <= n; ++i) if (cnt[i]) { 239 for (int j = n; j >= cnt[i]; --j) { 240 dp[j] = (dp[j] + 1ll * cnt[i] * dp[j - cnt[i]]) % P; 241 } 242 } 243 244 int ans = 0; 245 for (int i = max_cnt; i <= n; ++i) (ans += dp[i]) %= P; 246 cout << ans << endl; 247 } 248 249 int main() { 250 ios::sync_with_stdio(false); 251 cin.tie(nullptr); 252 253 int T; 254 cin >> T; 255 while (T--) { 256 solve(); 257 } 258 259 return 0; 260 } 261 ``` 262 263 [2165C — Binary Wine](https://codeforces.com/contest/2165/problem/C) 264 265 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n") 266 267 Some participants mentioned that similar ideas have appeared recently. We knew of at least one such problem, however, the problem was already proposed and accepted at that time. 268 269 I believe that the problems are not identical, though similar ideas were used, it is also a show of skill to remember and reuse ideas learnt from previous problems. Therefore, I would like to think the problem does have a place in the contest. 270 271 There was an oversight on the preparation of this problem, the tests did not include enough small tests, which allowed some codes with wrong implementation to pass. We apologize for the inconvenience. 272 273 **Tutorial** 274 275 There are many ways to approach this problem, my personal approach is as follows: 276 277 Consider what kind of $a$ would satisfy the requirements, after some exploring, we can arrive at the following check: Sum each bit of $a$, resulting in an integer sequence, if this sequence is lexicographically larger or equal to the binary representation of $c$, then $a$ is ok. 278 279 This can be explained by considering bits from high to low: 280 281 * If at some point we have more $a$'s than $c$, we can use a 1-bit on this position to fix everything under this bit. 282 * If at some point we have $0$ a's and the $c$ bit is $1$, it's then obvious that we cannot satisfy the conditions, since we also cannot use higher bits to change the situation, as this will cause higher bits to be less than $c$. 283 284 Thus, we have obtained a clean check to $a$. 285 286 To minimize the $+1$ operations, we will iterate bits from high to low, if the current $a$'s is less than $c$, we will have to select a single $a$ element, and increase it to the point that the current bit is $1$. Note that we will not increase two $a$ elements, since in reaching the state, we will inevitably reach the state where one of the $a$ is $1000\cdots00$, and the other one is $0111\cdots11$, this is already enough. 287 288 From here, observe that only the maximum $O(\log V)$ elements are used, we can easily achieve a complexity of $O(n\log n+q\log^2V)$, or $O(n\log n+q\log V\log\log V)$ with heaps. 289 290 **Solution** 291 292 ``` 293 #include <bits/stdc++.h> 294 #define N 500011 295 #define ll long long 296 using namespace std; 297 int T,n,q,a[N]; 298 int main() 299 { 300 scanf("%d",&T);while(T--) 301 { 302 scanf("%d%d",&n,&q); 303 for(int i=1;i<=n;++i)scanf("%d",a+i); 304 sort(a+1,a+1+n,greater<int>()); 305 int nn=min(n,32); 306 while(q--) 307 { 308 int c;scanf("%d",&c); 309 static int b[44];ll ans=0; 310 for(int i=1;i<=nn;++i)b[i]=a[i]; 311 for(int i=29;~i;--i) 312 { 313 int cc=0; 314 for(int j=1;j<=nn;++j)cc+=b[j]>>i&1; 315 if(cc>(c>>i&1))break; 316 if(cc<(c>>i&1)) 317 { 318 int id=1; 319 for(int j=2;j<=nn;++j)if(b[j]>b[id])id=j; 320 ans+=(1<<i)-b[id]; 321 b[id]=0; 322 } 323 else for(int j=1;j<=nn;++j)b[j]&=~(1<<i); 324 } 325 printf("%lld\n",ans); 326 } 327 } 328 } 329 ``` 330 331 [2165D — Path Split](https://codeforces.com/contest/2165/problem/D) 332 333 idea & solution: [le0n](/profile/le0n "Legendary Grandmaster le0n") 334 335 Some participants mentioned that similar ideas have appeared recently, we did not know of this. 336 337 This problem was initially proposed with a Hall-dp solution, also with complexity $O(n)$, but testers told us of a simpler greedy solution. 338 339 **Hint 1** 340 341 Reduce the problem to bipartite matching. 342 343 **Hint 2** 344 345 Devise a greedy algorithm to solve the matching problem, and prove it (or not). 346 347 **Tutorial** 348 349 The problem can be formulated as a minimum path cover, which in turn can be converted into a bipartite matching problem: 350 351 * For each element in $a$, create both a left side vertex and a right side vertex, each left side vertex with value $a_i$ can match right side vertices with index larger than $i$, and with value $a_i-1$ or $a_i+1$. 352 353 It can be observed that the graph can be partitioned into two unconnected components by parity. 354 355 A certain intuition the matching for $a_i=1$ stricter than $a_i=3$, maybe we can try just letting the $a_i=1$ greedily choose the next element, and just believe that it will work out. 356 357 Therefore, we can propose a greedy algorithm: we iterate values $v$ from small to large, for every vertex with value $v$ on the left side, if it is unmatched, we match it with a $v+1$ on the right side with index closest to it, we do the same for value $v$ vertices on the right side. 358 359 We can prove that this is correct: Consider an element with $a_i=1$, if it did not match the closest $a_i=2$ on the right, we will try to substitute this pair into the final matching. 360 361 Suppose our $a_i=1$ vertex is $A$, the $a_i=2$ vertex on the right is $B$. If we insert $A-B$ into the matching, and discard any preexisting matches with $A$ or $B$, the only case where we our matching size decreases is when $A$ and $B$ are both matched with some $C$ and $D$, respectively. 362 363 It can then be shown by simple reasoning that $C$ and $D$ can be matched, which means our matching size will not be reduced. 364 365 Therefore, we can choose any $a_i=1$ and the closest $a_i=2$, and simply delete them from the graph. 366 367 Thus, the greedy is proved. 368 369 Implementation should be easy. Time Complexity: $O(n\log n)$ or $O(n)$. 370 371 **Tutorial (Hall-dp)** 372 373 Observation: construct a bipartite graph with $2n$ vertices, named $L_1,L_2,\dots,L_n$ and $R_1,R_2,\dots,R_n$. There is an edge between $L_i$ and $R_j$ iff $i \lt j$ and $|a_i-a_j|=1$. The answer to the original problem is $n$ minus the size of the maximum matching of this graph. 374 375 Consider using hall theorem on $L_1,L_2,\dots,L_n$, thus we only need to calculate $\max |S|-|N(S)|$. 376 377 Separate $L$ into $L_{odd}$ and $L_{even}$, which contains all the $L_i$ with odd $a_i$ and vice versa. Let $S_{odd}=S\cap L_{odd}$ and $S_{even}=S\cap L_{even}$ we can see that $|S|-|N(S)|=|S_{odd}|-|N(S_{odd})|+|S_{even}|-|N(S_{even})|$, so we can calculate the two parts separately. 378 379 For $\max |S_{odd}|-|N(S_{odd})|$, if adding an element to $S_{odd}$ doesn't make $N(S_{odd})$ bigger, we can always add it. So we only need to consider $S_{odd}$ that for every odd value $x$, all the elements in $S_{odd}$ with value $x$ forms a suffix of all appearances of $x$ in array $a$. 380 381 We can define $dp_{i,j}$ as the maximum $|S_{odd}|-|N(S_{odd})|$ when only considering elements with value $\leq i$ in $S_{odd}$ and $N(S_{odd})$ (where $i$ is always odd), and the elements with value $i$ forms the suffix starting from position $j$. Since $\sum cnt$ is bounded by $O(n)$, we have a total of $O(n)$ states. The dp transitions between $i$ and $i+2$ can be done easily in linear time, so the total complexity is $O(n)$. 382 383 **Solution** 384 385 ``` 386 #include <bits/stdc++.h> 387 388 using namespace std; 389 390 const int N = 1e6 + 5; 391 bool vis[N]; 392 int a[N], n; 393 vector<int> pos[N * 2]; 394 int solve() 395 { 396 int i, p, ans = 0; 397 vector<int> tmp; 398 for(i = 1; i < 2 * n; i++) 399 { 400 if(i & 1) 401 { 402 p = 0; 403 for(auto o: pos[i]) 404 { 405 while(p < pos[i + 1].size() && pos[i + 1][p] < o) 406 p++; 407 if(p < pos[i + 1].size()) 408 vis[pos[i + 1][p++]] = 1; 409 } 410 } 411 else 412 { 413 p = pos[i + 1].size(); 414 reverse(pos[i].begin(), pos[i].end()); 415 for(auto o: pos[i]) 416 { 417 while(p && pos[i + 1][p - 1] > o) 418 p--; 419 if(p) 420 vis[pos[i + 1][--p]] = 1; 421 } 422 } 423 tmp.clear(); 424 for(auto o: pos[i + 1]) 425 if(vis[o]) 426 ans++; 427 else 428 tmp.emplace_back(o); 429 pos[i + 1] = tmp; 430 } 431 return ans; 432 } 433 434 int main() 435 { 436 int t, i, ans; 437 scanf("%d", &t); 438 while(t--) 439 { 440 scanf("%d", &n); 441 for(i = 1; i <= n; i++) 442 scanf("%d", a + i); 443 for(i = 1; i <= n; i++) 444 vis[i] = 0; 445 for(i = 1; i <= 2 * n; i++) 446 pos[i].clear(); 447 for(i = 1; i <= n; i++) 448 pos[a[i]].emplace_back(i); 449 ans = n - solve(); 450 reverse(a + 1, a + n + 1); 451 for(i = 1; i <= n; i++) 452 vis[i] = 0; 453 for(i = 1; i <= 2 * n; i++) 454 pos[i].clear(); 455 for(i = 1; i <= n; i++) 456 pos[a[i]].emplace_back(i); 457 ans -= solve(); 458 printf("%d\n", ans); 459 } 460 return 0; 461 } 462 ``` 463 464 **Solution (Hall-dp)** 465 466 ``` 467 #include <bits/stdc++.h> 468 469 using namespace std; 470 471 const int N = 1e6 + 5, inf = 1e9; 472 int a[N], lp[N], rp[N], Lp[N], m; 473 vector<int> pos[N * 2], dp[N * 2], tmp; 474 int solve() 475 { 476 int i, j, u, v, p; 477 dp[1].resize(pos[1].size()); 478 for(i = 0; i < pos[1].size(); i++) 479 dp[1][i] = i; 480 for(i = 1; i < m; i += 2) 481 { 482 u = pos[i].size() - 1; 483 v = pos[i + 2].size() - 1; 484 tmp.clear(); 485 tmp.resize(u + 1); 486 dp[i + 2].clear(); 487 dp[i + 2].resize(v + 1); 488 for(j = 0; j <= u; j++) 489 tmp[j] = dp[i][j] - rp[pos[i][j]]; 490 for(j = u; j > 0; j--) 491 tmp[j - 1] = max(tmp[j - 1], tmp[j]); 492 for(j = 0; j <= v; j++) 493 { 494 p = pos[i + 2][j]; 495 if(j) 496 dp[i + 2][j] = dp[i + 2][j - 1]; 497 if(Lp[p] < u) 498 dp[i + 2][j] = max(dp[i + 2][j], j + tmp[Lp[p] + 1]); 499 dp[i + 2][j] = max(dp[i + 2][j], j - lp[p] + dp[i][Lp[p]]); 500 } 501 } 502 return dp[m].back(); 503 } 504 505 int main() 506 { 507 int t, n, i, ans; 508 scanf("%d", &t); 509 while(t--) 510 { 511 scanf("%d", &n); 512 m = 0; 513 ans = n; 514 for(i = 1; i <= n; i++) 515 { 516 scanf("%d", a + i); 517 m = max(m, a[i]); 518 ans -= 2 * (a[i] & 1); 519 } 520 m |= 1; 521 for(i = 1; i <= m; i++) 522 pos[i] = {0}; 523 for(i = 1; i <= n; i++) 524 { 525 pos[a[i]].emplace_back(i); 526 lp[i] = (a[i] > 1 ? pos[a[i] - 1].size() - 1 : 0); 527 rp[i] = (a[i] < m ? pos[a[i] + 1].size() - 1 : 0); 528 Lp[i] = (a[i] > 2 ? pos[a[i] - 2].size() - 1 : 0); 529 } 530 ans += solve(); 531 reverse(a + 1, a + n + 1); 532 for(i = 1; i <= m; i++) 533 pos[i] = {0}; 534 for(i = 1; i <= n; i++) 535 { 536 pos[a[i]].emplace_back(i); 537 lp[i] = (a[i] > 1 ? pos[a[i] - 1].size() - 1 : 0); 538 rp[i] = (a[i] < m ? pos[a[i] + 1].size() - 1 : 0); 539 Lp[i] = (a[i] > 2 ? pos[a[i] - 2].size() - 1 : 0); 540 } 541 ans += solve(); 542 printf("%d\n", ans); 543 } 544 return 0; 545 } 546 ``` 547 548 [2165E — Rainbow Branch](https://codeforces.com/contest/2165/problem/E) 549 550 idea & solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire") 551 552 Our testers had vastly different opinions on the difficulty on this problems, some were able to solve within 20mins, and others failed to solve within a sufficiently long time. We eventually decided to put it at E, and it seems to have did its work. 553 554 **Hint 1** 555 556 The answer is increasing, try solve for the maximum number of colors for a certain inconvenience $d$. 557 558 **Hint 2** 559 560 Every color is a connected component. 561 562 **Hint 3** 563 564 There exists a diameter-midpoint like structure. 565 566 **Hint 4** 567 568 The optimal answer has a certain structure, try finding it. 569 570 **Tutorial** 571 572 We switch the answer and the parameter, and solve for the maximum number of colors for a given diameter $d$. 573 574 A simple intuition is that each color should be a connected component, this is also easily provable: If some color is not connected, we can choose one of its "outermost" components (a more rigorous definition would be the leaves of the auxiliary tree of its components), and change it to the color of its adjacent component. In doing this, the number of different components is decreased, and our inconvenience has not increased. Therefore, after enough changes, each color will be a connected component. 575 576 The problem asks for a diameter-like value, therefore, we can try to find a diameter-midpoint-like structure: 577 578 * When $d$ is odd, there exists a color component such that the distance to all other vertices does not exceed $\frac{d-1}2$. 579 * When $d$ is even, there exists a vertex such that the distance to all other vertices does not exceed $\frac d2$. 580 581 Now, observe that we can "push" colors away from the midpoint and out to the leaves, to increase the number of color used, our optimal solution would look something like this: 582 583  584 585 Therefore, the optimal solution is: 586 587 * For odd $d$, remove the outermost $(d-1)/2$ levels of leaves. 588 * For even $d$, remove the outermost $d/2-1$ levels of leaves, and choose a maximum degree vertex in the remaining tree. 589 590 Time Complexity: $O(n\log n)$ or $O(n)$. 591 592 **Solution** 593 594 ``` 595 #include <bits/stdc++.h> 596 597 using namespace std; 598 599 const int N = 3e5 + 5; 600 vector<int> e[N]; 601 int val[N], cnt[N], deg[N], h[N], d; 602 queue<int> q; 603 int del(int x) 604 { 605 cnt[deg[x]]--; 606 cnt[--deg[x]]++; 607 return deg[x]; 608 } 609 610 int main() 611 { 612 int t, n, i, u, v, k, c; 613 scanf("%d", &t); 614 while(t--) 615 { 616 scanf("%d", &n); 617 for(i = 1; i <= n; i++) 618 e[i].clear(); 619 for(i = 1; i < n; i++) 620 { 621 scanf("%d%d", &u, &v); 622 e[u].emplace_back(v); 623 e[v].emplace_back(u); 624 } 625 for(i = 0; i <= n; i++) 626 { 627 val[i] = 1e9; 628 cnt[i] = 0; 629 h[i] = 1; 630 } 631 for(i = 1; i <= n; i++) 632 cnt[deg[i] = e[i].size()]++; 633 for(i = 1; i <= n; i++) 634 if(deg[i] == 1) 635 q.push(i); 636 c = 0; 637 d = n; 638 while(!cnt[d]) 639 d--; 640 val[1] = min(val[1], 1); 641 val[d] = min(val[d], 2); 642 while(!q.empty()) 643 { 644 k = q.front(); 645 q.pop(); 646 for(auto o: e[k]) 647 if(del(o) == 1) 648 { 649 h[o] = h[k] + 1; 650 q.push(o); 651 } 652 ++c; 653 while(!cnt[d]) 654 d--; 655 val[c + 1] = min(val[c + 1], 2 * h[k] + 1); 656 val[c + d] = min(val[c + d], 2 * h[k] + 2); 657 } 658 for(i = n - 1; i >= 1; i--) 659 val[i] = min(val[i], val[i + 1]); 660 for(i = 1; i < n; i++) 661 printf("%d ", val[i]); 662 printf("\n"); 663 } 664 return 0; 665 } 666 ``` 667 668 [2165F — Arctic Acquisition](https://codeforces.com/contest/2165/problem/F) 669 670 idea & solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire") 671 672 No, we did not propose a paper problem. We knew of the paper on permutation pattern matching in advance, but we assumed the paper would not help much in solving the problem, either due to coding complexity, or constants hidden by the notation that would make it impractical. I'll admit that I did not read the paper in full (procrastination), but from what I gathered, it seemed that understanding the paper would be harder than solving the problem in itself. 673 674 If I am mistaken, please let me know. 675 676 **Hint 1** 677 678 We only need to calculate the minimum $r$ for each $l$, try breaking $21435$ into smaller parts. 679 680 **Hint 2** 681 682 When we fix the $21$-part, we need to append a $435$-part such that $val_3 \gt val_2$, and $index_4 \gt index_1$. (Here the footnotes refer to the value order, rather than index order.) 683 684 Therefore, we need to find $435$-subsequences that are Left-Right-Min minimal, that is, there does not exist another $435$-subsequence that is better in all three aspects. 685 686 **Hint 3** 687 688 The number of such $435$-subsequences is small. Try analyzing what kind of subsequence are minimal. 689 690 **Hint 4** 691 692 Perform scanline on the value of "$3$" from large to small, at most one $435$ will be added each time. 693 694 **Tutorial** 695 696 It suffices to find the minimal $r$ such that $[l,r]$ contains a $21435$-avoiding subsequence for every $l$. 697 698 We will refer to the elements by value order, instead of index order, in the following text, i.e. "$2$"-element refers to the leftmost element, with the second smallest value. 699 700 When we have fixed $l$, the "$2$"-element will be fixed, the "$1$"-element will just be the next element that is smaller than it, therefore, we only need to append a $435$-subsequence to it. 701 702 As we need to minimize $r$, and $val_3 \gt val_2,index_4 \gt index_1$ should be satisfied, we will need to consider all Left-Right-Min minimal $435$'s, that is, the ones where there does not exist another $435$ that is better in all three aspects. 703 704 To analyze this, we can try performing scanline on the $val_3$ from large to small, we can perform some substitutions to reduce the number of $435$'s we need to consider. 705 706 Through this, we can find a surprisingly strong restriction on minimal $435$'s: For each $i$ being considered as the "$3$"-element, the "$5$"-element must be $nxt(i)$, the closest element to the right of $i$, with value greater than $a_i$. 707 708 We perform substitutions as follows: 709 710  711 712 The three cases corresponds to: 713 714 * Left: $val_5 \lt val_{nxt(i)}$, by definition, $index_5 \gt index_{nxt(i)}$, substitute "$5$" by $nxt(i)$. 715 * Middle: $val_5 \gt val_{nxt(i)},val_4 \lt val_{nxt(i)}$, substitute "$5$" by $nxt(i)$. 716 * Right: $val_5 \gt val_{nxt(i)},val_4 \gt val_{nxt(i)}$, substitute $i$ by $nxt(i)$. 717 718 When "$3$" and "$5$" are fixed, "$4$" is also fixed. Therefore, there are at most $n$ minimal $435$'s, and they can be found by simple data structure techniques. 719 720 After finding the minimal $435$'s, the problem can be reduced to simple 2D-queries. 721 722 Time Complexity: $O(n\log n)$. 723 724 **Solution** 725 726 ``` 727 #include <bits/stdc++.h> 728 #define N 1000011 729 using namespace std; 730 int T,n,a[N],id[N]; 731 int R[N]; 732 struct sgt 733 { 734 int D,mx[N*4]; 735 int query(int l,int r) 736 { 737 l+=D-1;r+=D+1;int ans=0; 738 while(l^r^1) 739 { 740 if(!(l&1))ans=max(ans,mx[l^1]); 741 if(r&1)ans=max(ans,mx[r^1]); 742 l>>=1;r>>=1; 743 } 744 return ans; 745 } 746 void modi(int k,int p) 747 { 748 k+=D;mx[k]=p; 749 while(k>>=1)mx[k]=max(mx[k<<1],mx[k<<1|1]); 750 } 751 void clear() 752 { 753 D=1;while(D<=n+10)D<<=1; 754 for(int i=0;i<D+D;++i)mx[i]=0; 755 } 756 }T1,T2; 757 int pl[N],res[N],curr[N]; 758 int Rmn[N]; 759 void proc() 760 { 761 for(int i=1;i<=n;++i)R[i]=Rmn[i]=i+1,id[a[i]]=i,pl[i]=0; 762 for(int i=n;i;--i)while(R[i]<=n&&a[R[i]]<a[i])R[i]=R[R[i]]; 763 for(int i=n;i;--i)while(Rmn[i]<=n&&a[Rmn[i]]>a[i])Rmn[i]=Rmn[Rmn[i]]; 764 T1.clear(); 765 for(int i=1;i<=n;++i) 766 { 767 if(R[i]<=n) 768 { 769 int k=T1.query(a[i]+1,a[R[i]]-1); 770 pl[i]=k; 771 } 772 T1.modi(a[i],i); 773 } 774 T2.clear(); 775 for(int i=1;i<=n;++i)curr[i]=res[i]=0; 776 for(int i=n;i;--i) 777 { 778 int x=id[i],y=Rmn[x]; 779 if(y<=n) 780 { 781 int rr=n+1-T2.query(y+1,n); 782 if(rr<=n)res[rr]=max(res[rr],x); 783 } 784 if(pl[x])T2.modi(pl[x],curr[pl[x]]=max(curr[pl[x]],n+1-R[x])); 785 } 786 for(int i=1;i<=n;++i)res[i]=max(res[i],res[i-1]); 787 } 788 int main() 789 { 790 scanf("%d",&T);while(T--) 791 { 792 scanf("%d",&n); 793 for(int i=1;i<=n;++i)scanf("%d",a+i); 794 proc(); 795 long long ans=0; 796 for(int i=1;i<=n;++i)ans+=res[i]; 797 printf("%lld\n",ans); 798 } 799 } 800 ```