2101.md (45166B)
1 Source: https://codeforces.com/blog/entry/142788 2 3 Thank you for participating! We hope you enjoyed the problems and, most importantly, had fun! 4 5 ## [2102A - Dinner Time](/contest/2102/problem/A "Codeforces Round 1024 (Div. 2)") 6 7 **Hints** 8 9 **Hint 1** 10 11 If you have the first $p$ elements, what happens to the rest? 12 13 **Hint 2** 14 15 What happens if $n\%p\neq0$? 16 17 **Hint 3** 18 19 How can the fact that we can also use negative numbers be useful? 20 21 **Solution** 22 23 The first thing to realize is that if the first $p$ elements of the array are determined, the rest will be unique ($a_i = a_{i-p}$ to hold the sum). If $p$ divides $n$, there will be $\frac{n}{p}$ blocks, each summing to $q$, so their total sum which is $q\cdot \frac{n}{p}$ should be equal to $m$. If not, the incomplete block that is created at the end can be used to cover any difference in sum, so it's always possible! 24 25 **Code (Python 3)** 26 27 ``` 28 t = int(input()) 29 30 for _ in range(t): 31 n, m, p, q = map(int, input().split()) 32 33 if n % p == 0 and (n // p) * q != m: 34 print("NO") 35 else: 36 print("YES") 37 ``` 38 39 **Bonus** 40 41 This problem was supposed to be for cyclic arrays, and also required construction, but due to D2A difficulty it was adjusted! 42 43 *Do you have a solution for the cyclic array version? Comment it below* 44 45 ## [2102B - The Picky Cat](/contest/2102/problem/B "Codeforces Round 1024 (Div. 2)") 46 47 **Hints** 48 49 **Hint 1** 50 51 Does the initial sign and order of elements matter? 52 53 **Hint 2** 54 55 If an element is before the median in the sorted array, can you shift it forward? 56 57 **Hint 3** 58 59 What if it is initially after the median? 60 61 **Solution** 62 63 Before starting, we take the absolute value of all elements since their signs do not matter. Then, if the first element of the array is equal to or smaller than the $\left\lfloor \frac{n}{2}\right\rfloor + 1$ smallest element of the array, the answer is possible. Else, it is impossible. The proof is as follows: 64 65 * If the first element is equal to or smaller than the $\left\lceil\frac{n}{2}\right\rceil$ smallest element of the array, we can negate the big values until the first element becomes the $\left\lceil\frac{n}{2}\right\rceil$ smallest element of the array, hence becoming the median. 66 * If the first element is equal to the $\left\lfloor \frac{n}{2}\right\rfloor + 1$ smallest element of the array, we can negate the entire array, which results in the first element becoming the $\left\lceil\frac{n}{2}\right\rceil$ smallest element of the array. 67 * Otherwise, if the first element of the array is larger than the $\left\lfloor \frac{n}{2}\right\rfloor + 1$ smallest element of the array, negating values smaller than it has no effect, while negating values larger than it just makes the first element further away from the median position. You can verify that negating the first element itself does not help either by using similar cases. 68 69 **Code (Python 3)** 70 71 ``` 72 t = int(input()) 73 74 for _ in range(t): 75 n = int(input()) 76 a = list(map(int, input().split())) 77 78 pairs = [(abs(a[i]), i) for i in range(n)] 79 pairs.sort() 80 81 ans = [0] * n 82 83 for i in range(n // 2 + 1): 84 _, index = pairs[i] 85 ans[index] = 1 86 87 if ans[0]: 88 print("YES") 89 else: 90 print("NO") 91 ``` 92 93 **Bonus** 94 95 Would it be easier to calculate the answer for all indices and just output for the first index? 96 97 *What's up with the name of the problem?* 98 99 ## [2101A - Mex in the Grid](/contest/2101/problem/A "Codeforces Round 1024 (Div. 1)") 100 101 **Hints** 102 103 **Hint 1** 104 105 What is the MEX, if $0$ is not there? 106 107 **Hint 2** 108 109 When is the MEX equal to $k$? 110 111 **Hint 3** 112 113 If we want a subgrid to be included in as many other subgrids as possible, what shape should it have? What about its place? 114 115 **Solution** 116 117 The first fact to notice is that if the subgrid does not contain $0$, then the MEX is $0$ and we can ignore such subgrids. If the MEX is going to be $k$, it means **all** the values from $0$ to $k-1$ are included in the subgrid. For each $0\le k\le n^2$, we count how many subgrids have a MEX of at least $k$, aiming to maximize this. 118 To find the total sum of all MEX values, for each $k$ we count the number of subgrids that contain all the values from $0$ to $k-1$. Summing these counts gives us the final result. 119 120 We claim that if our subgrid is nearly square (either a perfect square or a difference of $1$ in lengths), and is placed in the middle of the grid, then the answer is maximized. 121 122 **Proof**: The multiplication of two numbers with the same sum is maximized when they are as close to each other as possible. Therefore, for each subgrid, if we consider the empty rows above and below it and separately consider the columns on its right and left, if one is fixed, the place is optimized to be in the middle. Now, similarly, we can say that it is optimal if the length and height of the subgrid are close to each other as well, as increasing one will cause the other one to decrease. With these two observations combined, a subgrid having the above properties is optimal when it's a *nearly* square subgrid in the middle of the grid. 123 124 Any ordering with this property works; an easy example is a *spiral shape* that starts from the center of the grid and turns around itself. 125 126 **Code (Python 3)** 127 128 ``` 129 def magical_spiral(n): 130 arr = [[-1] * n for _ in range(n)] 131 132 if n % 2 == 0: 133 x, y = n // 2 - 1, n // 2 - 1 134 else: 135 x, y = n // 2, n // 2 136 137 arr[x][y] = 0 138 value = step = 1 139 140 dir = [(0, 1), (1, 0), (0, -1), (-1, 0)] 141 142 while value < n * n: 143 for d in range(4): 144 steps = step 145 146 step += d % 2; dx, dy = dir[d] 147 148 for _ in range(steps): 149 x += dx; y += dy 150 151 if 0 <= x < n and 0 <= y < n and arr[x][y] == -1: 152 arr[x][y] = value 153 value += 1 154 if value >= n * n: 155 break 156 157 if value >= n * n: 158 break 159 160 for row in arr: 161 print(" ".join(str(num) for num in row)) 162 print() 163 164 t = int(input()) 165 166 for _ in range(t): 167 n = int(input()) 168 169 magical_spiral(n) 170 ``` 171 172 **Bonus** 173 174 We had the idea of dividing this problem into two subtasks, in which the second subtask requires you to **count** the sum of MEX of all subgrids! 175 176 *Do you have a solution for this? Comment it below* 177 178 ## [2101B - Quartet Swapping](/contest/2101/problem/B "Codeforces Round 1024 (Div. 1)") 179 180 **Hints** 181 182 **Hint 1** 183 184 Is it possible for an element to change its index parity after some operations? 185 186 **Hint 2** 187 188 What else is not effected by the operation? 189 190 **Hint 3** 191 192 How to combine the above two properties under the time limit? 193 194 **Solution** 195 196 The first observation is that the parity of the position of the elements doesn't change with the operations. Thus, if an element is at an odd or even index in the initial permutation, it will retain the same parity in the final permutation. As long as we have four elements left, we can freely adjust them within their index parity zone, but what about the last three ones? We can see that the parity of the number of inversions is fixed, so by counting the inversions of the initial permutation, the order of the last four elements will be uniquely determined. 197 198 **Code (C++)** 199 200 ``` 201 #include <bits/stdc++.h> 202 203 #define pb push_back 204 #define int long long 205 #define F first 206 #define S second 207 #define sz(a) (int)a.size() 208 #define pii pair<int,int> 209 #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++) 210 #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--) 211 #define all(a) a.begin(),a.end() 212 213 using namespace std ; 214 const int maxn = 1e6 + 10 ; 215 int a[maxn] , n , fen[maxn] ; 216 217 void upd(int x){ 218 while(x <= n){ 219 fen[x]++; 220 x += x&-x; 221 } 222 } 223 224 int que(int x){ 225 int ans =0 ; 226 while(x){ 227 ans += fen[x] ; 228 x -= x&-x; 229 } 230 return ans ; 231 } 232 233 int f(vector<int> x){ 234 rep(i , 0, n)fen[i] =0; 235 int ans =0 ; 236 per(i , sz(x)-1 , 0){ 237 ans += que(x[i]); 238 upd(x[i]) ; 239 } 240 241 return ans ; 242 } 243 244 signed main(){ 245 ios::sync_with_stdio(0) ; cin.tie(0); 246 247 int T ; 248 cin >> T ; 249 250 while(T--){ 251 vector <int> a1 , a2 ; 252 253 cin >> n ; 254 rep(i ,1 ,n){ 255 int x; cin >> x; 256 257 if (i%2==1) { 258 a1.pb(x); 259 } else { 260 a2.pb(x); 261 } 262 } 263 264 bool v = (f(a1)%2 != f(a2)%2); 265 266 sort(all(a1)); sort(all(a2)); 267 268 int x1 = 0, x2 =0; 269 270 rep (i ,1 , n) { 271 if (i%2==1) { 272 a[i] = a1[x1] ; x1++; 273 } else { 274 a[i] = a2[x2] ; x2++; 275 } 276 } 277 278 if (v) { 279 swap(a[n] , a[n-2]) ; 280 } 281 282 rep(i ,1 ,n) cout << a[i] << " "; 283 cout << "\n"; 284 } 285 } 286 ``` 287 288 **Bonus** 289 290 This problem was one of the first problems that we had, and the intended constraits were $n\le 3000$ as a D1A, but later was moved to D1B with $n\le 2\cdot 10^5$! 291 292 *Do you know how to count the parity of inversions without counting the number of inversions?* 293 294 ## [2101C - 23 Kingdom](/contest/2101/problem/C "Codeforces Round 1024 (Div. 1)") 295 296 **Hints** 297 298 **Hint 1** 299 300 Does it matter if there are $2$ occurance of a number or $200$? 301 302 **Hint 2** 303 304 What greedy approaches can you think of? 305 306 **Hint 3** 307 308 Are they fast enough? 309 310 **Solution** 311 312 The first observation is that we only care about the first and last occurrences of each number in the final array, as anything in between doesn't change the maximum distance. Instead of counting the distances directly, the main idea of this problem is to break them down into pieces. For example, the distance of a pair $(i, j)$ such that $1\le i \lt j\le n$ and $a_i = a_j$ and also these indices are the farthest possible, instead of adding up $j-i$, we count one for each index in between $i$ and $j$. In Another word, for each index $i$, we count how many *begins* are in or before $i$, and how many *ends* are after $i$, adding up these values for each index gives us the sum of distances. 313 314 For each prefix and suffix of our array, we count the maximum number of different *begins* that we can get greedily. It can be proven that if we try to match each $a_i$ with the biggest unmatched number left, we'll end up getting the maximum number of different matches possible. Doing so can be calculated in many different ways, one using sets is shown in the implementation below. 315 316 After that, for each $1\le i \lt n$, we have a bound for the number of pairs that these indices can be in between of, as we calculated the maximum distinct matches possible for both sides (one prefix and one suffix). It can be proven that there exists an array $b$ meeting the problem conditions such that the bound for each index is held, and therefore summing up all values gives us the final answer. 317 318 **Code (C++)** 319 320 ``` 321 #include <bits/stdc++.h> 322 323 #define int long long 324 325 // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 326 // #pragma GCC optimize("O3") 327 // #pragma GCC optimize("unroll-loops") 328 329 #define F first 330 #define S second 331 #define mp make_pair 332 #define pb push_back 333 #define all(x) x.begin(), x.end() 334 #define kill(x) cout << x << "\n", exit(0); 335 #define pii pair<int, int> 336 #define pll pair<long long, long long> 337 #define endl "\n" 338 339 340 341 using namespace std; 342 typedef long long ll; 343 // typedef __int128_t lll; 344 typedef long double ld; 345 346 const int MAXN = (int)1e6 + 7; 347 const int MOD = (int)1e9 + 7; 348 const ll INF = (ll)1e18 + 7; 349 350 int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, p, q, ans, flag; 351 int arr[MAXN], f[MAXN][2]; 352 set<int> st; 353 354 void solve() { 355 cin >> n; 356 357 for (int i=1; i<=n; i++) cin >> arr[i]; 358 359 for (int j=0; j<2; j++) { 360 st.clear(); 361 for (int i=1; i<=n; i++) st.insert(i); 362 363 for (int i=(j? n : 1); (j?i>1 : i<n); (j? i-- : i++)) { 364 auto it = st.upper_bound(arr[i]); 365 366 if (it != st.begin()) it--, st.erase(*it); 367 368 f[i][j] = n-st.size(); 369 } 370 } 371 372 ans = 0; 373 for (int i=1; i<n; i++) ans += min(f[i][0], f[i+1][1]); 374 375 cout << ans << endl; 376 } 377 378 int32_t main() { 379 #ifdef LOCAL 380 freopen("inp.in", "r", stdin); 381 freopen("res.out", "w", stdout); 382 #else 383 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 384 #endif 385 386 cin >> t; 387 388 while (t--) solve(); 389 390 return 0; 391 } 392 ``` 393 394 **Bonus** 395 396 We thought every greedy approach for this problem is wrong, and the intended solution used to be a $O(n^3)$ DP, but later realized we were wrong! 397 398 Can you think of a *rational* DP idea that despite the time limit can solve this question? 399 400 ## [2101D - Mani and Segments](/contest/2101/problem/D "Codeforces Round 1024 (Div. 1)") 401 402 **Hints** 403 404 **Hint 1** 405 406 What are some characteristics of a *cute* subarray? 407 408 **Hint 2** 409 410 Is *cuteness* a monotone property? 411 412 **Hint 3** 413 414 How to find the maximal *cute* subarray for a fixed index $i$? 415 416 **Solution** 417 418 The first observation is that a subarray is *cute*, iff there is an index $i$, such that it is the one and **only** share of the LIS and LDS, and all other elements belong to either LIS or LDS. 419 420 ***Proof***: We know that there cannot be two elements belonging to both LIS and LDS, and if there is none, the property won't be held. Therefore, we conclude that there is *exactly* one element shared between the LIS and LDS. 421 422 Diving deeper into the shared element, we can see that the smaller elements before it must all be ascending, and the bigger elements after it must also all be ascending (as this will make our LIS). Similarly, all the bigger elements before it and all the smaller elements after it should be descending. This gives us a good pattern, and we can easily see that any subarray *included* within a *cute* subarray is cute itself (call this monotonic property). 423 424 For counting the total number of *cute* subarrays, we calculate the values of $R_i$ and $L_i$ for each index. Let $L_i$ be the **biggest** index before $i$, such that the condition above is met. Similarly define $R_i$ as the $smallest$ index after $i$. If we can somehow calculate this values for all indices, then we'll end up with $n$ segments (for each $1\le i\le n$), and a subarray is *cute* iff it's included in **at least** one segment. This is a very classic problem, so the solution won't be discussed here. 425 426 The only detail left is how to calculate the values of $L_i$ and $R_i$? We'll discuss the process of calculating the $R_i$ here, but the $L_i$ follows a very similar pattern. We claim that $R_i = min(R_{i+1}, f(i))$. In here $f(i)$ is defined as follow: 427 428 * if $a_i \gt a_{i+1}$: then $f(i)$ is minimum index $j$, such that $a_{i+1}\le a_j\le a_i$. 429 * if $a_i \lt a_{i+1}$: in this case $f(i)$ is minimum $j$ such that $a_i\le a_j\le a_{i+1}$. 430 431 ***Proof***: The fact that $R_i\le R_{i+1}$ can easily be concluded from the fact thay *cuteness* is a monotonic property. Also going back to the conditions described above, we can see that $f(i)$ is basically the first index that will ruin our condition, so based on the definition of $R_i$, we can say that $R_i = min(R_{i+1}, f(i))$. 432 433 The calculation of $L_i$ and $R_i$ can both be implemented using a *Segment Tree* or a *Monotonic Stack*; both implementations are included below. After we have those values, we count the number of subarrays included in at least one segment, and that would be our final answer. 434 435 **Codes** 436 437 **Segment Tree Approach (C++)** 438 439 ``` 440 #include <bits/stdc++.h> 441 442 #define int long long 443 444 // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 445 // #pragma GCC optimize("O3") 446 // #pragma GCC optimize("unroll-loops") 447 448 449 #define F first 450 #define S second 451 #define mp make_pair 452 #define pb push_back 453 #define all(x) x.begin(), x.end() 454 #define kill(x) cout << x << "\n", exit(0); 455 #define pii pair<int, int> 456 #define pll pair<long long, long long> 457 #define endl "\n" 458 459 460 461 using namespace std; 462 typedef long long ll; 463 typedef long double ld; 464 465 466 const int MAXN = (int)1e6 + 7; 467 const int MOD = 998244353; 468 const int INF = (int)1e9 + 7; 469 470 471 int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, q, ans, flag; 472 int arr[MAXN], L[MAXN], R[MAXN]; 473 474 475 /* Segment Tree */ 476 #define mid ((l+r)>>1) 477 #define lid (mid<<1) 478 #define rid (lid|1) 479 480 481 int seg[MAXN<<2]; 482 483 484 void build(int l=0, int r=n, int id=1) { 485 if (l+1 == r) { 486 if (!flag) seg[id] = INF; 487 else seg[id] = -INF; 488 489 return; 490 } 491 492 build(l, mid, lid); 493 build(mid, r, rid); 494 495 if (!flag) seg[id] = min(seg[lid], seg[rid]); 496 else seg[id] = max(seg[lid], seg[rid]); 497 } 498 499 500 void upd(int ind, int k, int l=0, int r=n, int id=1) { 501 if (l+1 == r) { 502 seg[id] = k; 503 return; 504 } 505 506 if (ind < mid) upd(ind, k, l, mid, lid); 507 else upd(ind, k, mid, r, rid); 508 509 if (!flag) seg[id] = min(seg[lid], seg[rid]); 510 else seg[id] = max(seg[lid], seg[rid]); 511 } 512 513 514 int get(int s, int t, int l=0, int r=n, int id=1) { 515 if (l >= r || s >= t) { 516 if (!flag) return INF; 517 else return -INF; 518 } 519 520 if (s <= l && t >= r) return seg[id]; 521 if (t <= mid) return get(s, t, l, mid, lid); 522 if (s >= mid) return get(s, t, mid, r, rid); 523 524 if (!flag) return min(get(s, t, l, mid, lid), get(s, t, mid, r, rid)); 525 else return max(get(s, t, l, mid, lid), get(s, t, mid, r, rid)); 526 } 527 528 /* Segment Tree */ 529 530 531 void solve() { 532 cin >> n; 533 534 for (int i=1; i<=n; i++) { 535 cin >> arr[i]; 536 } 537 538 fill(L, L+n+7, 1); 539 fill(R, R+n+7, n); 540 541 542 flag = 0; 543 build(); 544 545 for (int i=n-2; i>=1; i--) { 546 upd(arr[i+2]-1, i+2); 547 548 R[i] = min(R[i], get(min(arr[i], arr[i+1]), max(arr[i], arr[i+1]))-1); 549 } 550 551 flag = 1; 552 build(); 553 554 for (int i=3; i<=n; i++) { 555 upd(arr[i-2]-1, i-2); 556 557 L[i] = max(L[i], get(min(arr[i], arr[i-1]), max(arr[i], arr[i-1]))+1); 558 } 559 560 for (int i=n-1; i>=1; i--) R[i] = min(R[i], R[i+1]); 561 for (int i=2; i<=n; i++) L[i] = max(L[i], L[i-1]); 562 563 ans = R[1]; 564 565 for (int i=2; i<=n; i++) { 566 ans += R[i-1]-i+1; 567 ans += (i-L[i]+1)*(R[i]-R[i-1]); 568 } 569 570 cout << ans << endl; 571 } 572 573 574 575 int32_t main() { 576 #ifdef LOCAL 577 freopen("inp.in", "r", stdin); 578 freopen("res.out", "w", stdout); 579 #else 580 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 581 #endif 582 583 cin >> t; 584 585 while (t--) solve(); 586 587 return 0; 588 } 589 ``` 590 591 **Monotonic Stack Approach (C++)** 592 593 ``` 594 #include <bits/stdc++.h> 595 596 #define pb push_back 597 #define int long long 598 #define F first 599 #define S second 600 #define sz(a) (int)a.size() 601 #define pii pair<int,int> 602 #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++) 603 #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--) 604 #define all(a) a.begin(),a.end() 605 606 using namespace std ; 607 const int maxn = 5e5 + 10 , mod = 1e9 + 7; 608 int a[maxn] , ri[maxn] , le[maxn] , bl[maxn] , br[maxn] , sl[maxn] , sr[maxn] ; 609 610 611 signed main(){ 612 ios::sync_with_stdio(0) ; cin.tie(0); 613 614 int T; 615 cin >> T; 616 617 while(T--) { 618 int n; cin >> n; 619 620 rep(i ,1, n) { 621 cin >> a[i]; 622 } 623 624 vector <int> s , b; 625 626 rep(i , 1 ,n){ 627 while(sz(s) && a[s.back()] > a[i])s.pop_back() ; 628 while(sz(b) && a[b.back()] < a[i])b.pop_back() ; 629 630 sl[i] = (sz(s) ? s.back() : 0); 631 bl[i] = (sz(b) ? b.back() : 0); 632 s.pb(i); b.pb(i) ; 633 } 634 635 s.clear(); 636 b.clear(); 637 638 per(i , n , 1){ 639 while(sz(s) && a[s.back()] > a[i])s.pop_back() ; 640 while(sz(b) && a[b.back()] < a[i])b.pop_back() ; 641 sr[i] = (sz(s) ? s.back() : n+1); 642 br[i] = (sz(b) ? b.back() : n+1); 643 s.pb(i); b.pb(i) ; 644 } 645 646 ri[n] = n; 647 per(i , n-1 ,1){ 648 ri[i] = ri[i+1]; 649 if(a[i] > a[i+1] && a[br[i+1]] < a[i]){ 650 ri[i] = min(ri[i] , br[i+1]-1); 651 } 652 653 if(a[i] < a[i+1] && a[sr[i+1]] > a[i]){ 654 ri[i] = min(ri[i] , sr[i+1]-1); 655 } 656 } 657 658 659 le[1] = 1 ; 660 rep(i , 2,n){ 661 le[i] = le[i-1] ; 662 if(a[i] > a[i-1] && a[bl[i-1]] < a[i]){ 663 le[i] = max(le[i] , bl[i-1]+1); 664 } 665 if(a[i] < a[i-1] && a[sl[i-1]] > a[i]){ 666 le[i] = max(le[i] , sl[i-1]+1); 667 } 668 } 669 670 int ans = ri[1] ; 671 rep(i , 2 , n){ 672 ans = (ans + (i-1 - le[i] + 1) * (ri[i] - ri[i-1]) + ri[i]-i+1) ; 673 } 674 cout << ans << "\n" ; 675 } 676 } 677 ``` 678 679 **Bonus** 680 681 We ended up having two D1D difficulty problems, but in the end chose this one as it was more *cute*! 682 683 We believe this was one of the *cleanest* problems we had. However, both the statement and solution made it look too classic, so we had a hard time making sure this idea had not been used elsewhere! 684 685 *Do you have a different approach than ours? Tell us in the comments.* 686 687 ## [2101E - Kia Bakes a Cake](/contest/2101/problem/E "Codeforces Round 1024 (Div. 1)") 688 689 **Hints** 690 691 **Hint 1** 692 693 Can we see any node twice in our walk? 694 695 **Hint 2** 696 697 What is the upper bound on the length of the path? 698 699 **Hint 3** 700 701 How do we approach this using dynamic programming? 702 703 **Hint 4** 704 705 How to optimize the DP? 706 707 **Solution** 708 709 The length of each two nodes in a tree is *always* less than the number of nodes, and therefore the maximum weight that we can see in our constructed graph has an upper bound of $n-1$. Because the weight of any *nice* path is doubled every time, the maximum length of any *nice* path won't exceed $log_2(n)$. 710 711 The next observation is that we cannot see any node twice in a nice path (in other words, there are no cycles). 712 713 **Proof**: Let's assume that a cycle exists. We know that the weight of each edge is always greater than the sum of all previous edges, so even without any waste, $\sum_{i=0}^{k} 2^i \lt 2^{k+1}$. This tells us no matter how far we get, because we're taking more steps in the last edge than the sum of all previous ones, we can never end up in the first node. Therefore, every *nice* path is a simple path, and no cycles can be made. 714 715 Now, let's define $dp_{i, j}$ as the **maximum weight** of any edge to start a simple path from vertex $j$ and take $i$ steps, and $0$ if not possible. The idea here is to build the nicest path reversly, from the end to the beginning. We can update this $dp$ and build the paths backwards, and this will give us an $O(n^2\cdot log(n))$ solution as $i\le log_2(n)$. 716 717 To optimize this, we use the suffix trick on centroid decomposition and keep the maximum two suffixes every time, to update $dp_{i, ?}$ in increasing order of $i$ accordingly. This would result in a $O(n\cdot log(n)^3)$ implementation, which can be further optimized to $O(n\cdot log(n)^2)$ using the fact that we can use *counting sort* for sorting as we have an upper bound of $n$. Both implementations are included below. 718 719 **Codes** 720 721 **O(n*log(n)^2) implementation** 722 723 ``` 724 #include <bits/stdc++.h> 725 726 using namespace std; 727 728 typedef long long ll; 729 typedef long double ld; 730 typedef pair<int,int> pii; 731 typedef pair<ll,ll> pll; 732 733 #define F first 734 #define S second 735 #define endl '\n' 736 #define Mp make_pair 737 #define pb push_back 738 #define pf push_front 739 #define size(x) (ll)x.size() 740 #define all(x) x.begin(), x.end() 741 #define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n" 742 743 const int N = 2e5 + 100, lg = 18; 744 const ll Mod = 1e9 + 7; 745 const ll inf = 1e18 + 10; 746 747 ll MOD(ll a, ll mod=Mod) { 748 a%=mod; (a<0)&&(a+=mod); return a; 749 } 750 751 ll poww(ll a, ll b, ll mod=Mod) { 752 ll res = 1; 753 while(b > 0) { 754 if(b%2 == 1) res = MOD(res * a, mod); 755 b /= 2; 756 a = MOD(a * a, mod); 757 } 758 return res; 759 } 760 761 int t, n, a[N], dp[lg + 1][N], gl, subt[N], mark[N]; 762 int h[N], T[N], pd[N], tag[N]; 763 vector<int> adj[N], centAdj[N]; 764 765 void init(int v, int p=0) { 766 subt[v] = 1, h[v] = (p == 0 ? 0 : h[p] + 1); 767 for(int u : adj[v]) { 768 if(u == p || mark[u] == 1) continue; 769 init(u, v); 770 subt[v] += subt[u]; 771 } 772 } 773 774 int findCent(int v, int p=0) { 775 for(int u : adj[v]) { 776 if(u == p || mark[u] == 1) continue; 777 if(subt[u] > subt[gl]/2) return findCent(u, v); 778 } 779 return v; 780 } 781 782 int createCentTree(int v) { 783 gl = v; 784 init(v); 785 int cent = findCent(v); 786 init(cent); 787 788 mark[cent] = 1; 789 for(int u : adj[cent]) { 790 if(mark[u] == 1) continue; 791 centAdj[cent].pb(createCentTree(u)); 792 } 793 794 return cent; 795 } 796 797 struct node { 798 pii mx1, mx2; 799 node() { 800 mx1 = {-1e9, -1}; mx2 = {-1e9, -2}; 801 } 802 } suff[N]; 803 804 node util(node y, pii x) { 805 if(y.mx1 < y.mx2) swap(y.mx1, y.mx2); 806 if(y.mx1 < x) swap(y.mx1, x); 807 808 if(y.mx2 < x) swap(y.mx2, x); 809 if(y.mx1.S == y.mx2.S) swap(y.mx2, x); 810 811 return y; 812 } 813 814 vector<int> vec; 815 void dfs1(int v, int p=0) { 816 // update v by gl 817 if(2*h[v] <= T[gl]) pd[v] = max(pd[v], h[v]); 818 // update gl by v 819 if(2*h[v] <= T[v]) pd[gl] = max(pd[gl], h[v]); 820 821 if(p == 0) tag[v] = 0; 822 else if(p == gl) { 823 tag[v] = v; 824 } else tag[v] = tag[p]; 825 826 if(tag[v] != 0 && T[v] - h[v] * 2 >= 0) vec.pb(v); 827 828 for(int u : adj[v]) { 829 if(u == p || mark[u] == 1) continue; 830 dfs1(u, v); 831 } 832 } 833 834 void dfs2(int v, int p=0) { 835 if(p != 0) { 836 if(suff[2*h[v]].mx1.S != tag[v]) { 837 pd[v] = max(pd[v], suff[2*h[v]].mx1.F + h[v]); 838 } else { 839 pd[v] = max(pd[v], suff[2*h[v]].mx2.F + h[v]); 840 } 841 } 842 843 for(int u : adj[v]) { 844 if(u == p || mark[u] == 1) continue; 845 dfs2(u, v); 846 } 847 } 848 849 void solve(int v) { 850 init(v, 0); 851 852 gl = v; 853 dfs1(v); 854 855 for(auto it : vec) { 856 int wh = min(T[it] - 2*h[it], 2*subt[v]); 857 suff[wh] = util(suff[wh], {h[it], tag[it]}); 858 } 859 860 for(int i=2*subt[v]-1; i>=1; i--) { 861 suff[i] = util(suff[i], suff[i+1].mx1); 862 suff[i] = util(suff[i], suff[i+1].mx2); 863 } 864 865 dfs2(v); 866 867 vec.clear(); 868 for(int i=0; i<=2*subt[v]+1; i++) suff[i] = node(); 869 mark[v] = 1; 870 for(int u : centAdj[v]) { 871 solve(u); 872 } 873 } 874 875 void work() { 876 cin>>n; 877 878 for(int i=1; i<=n; i++) { 879 char ch; cin>>ch; 880 a[i] = (ch == '1'); 881 } 882 883 for(int v,u,i=1; i<n; i++) { 884 cin>>v>>u; adj[v].pb(u); adj[u].pb(v); 885 } 886 887 int rt = createCentTree(1); 888 fill(mark, mark+n+2, 0); 889 fill(h, h+n+2, 0); 890 891 for(int i=1; i<=n; i++) dp[0][i] = (a[i]==1 ? 2*n : -1); 892 893 for(int i=1; i<=lg; i++) { 894 for(int j=1; j<=n; j++) { 895 if(a[j] == 1) T[j] = dp[i-1][j]; 896 else T[j] = -1; 897 } 898 899 solve(rt); 900 901 for(int j=1; j<=n; j++) { 902 tag[j] = mark[j] = 0; 903 dp[i][j] = pd[j]; 904 pd[j] = 0; 905 } 906 } 907 908 for(int i=1; i<=n; i++) { 909 if(a[i] == 0) {cout<<-1<<' '; continue;} 910 for(int j=lg; j>=0; j--) { 911 if(dp[j][i] >= 1) { 912 cout<<j+1<<' '; 913 break; 914 } 915 } 916 } 917 cout<<endl; 918 } 919 920 void reset_work() { 921 for(int i=0; i<=lg; i++) for(int j=1; j<=n; j++) dp[i][j] = 0; 922 923 gl = 0; 924 for(int i=0; i<=n+1; i++) { 925 adj[i].clear(); 926 centAdj[i].clear(); 927 h[i] = T[i] = pd[i] = tag[i] = 0; 928 subt[i] = mark[i] = 0; 929 } 930 931 return; 932 } 933 934 int main() { 935 ios_base::sync_with_stdio(false), cin.tie(0); 936 937 cin>>t; 938 939 while(t--) { 940 work(); 941 reset_work(); 942 } 943 944 return 0; 945 } 946 ``` 947 948 **O(n*log(n)^3) implementation** 949 950 ``` 951 #include <bits/stdc++.h> 952 using namespace std; 953 954 using ll = long long; 955 using ld = long double; 956 using pii = pair<int, int>; 957 using pll = pair<long long, long long>; 958 using ull = unsigned long long; 959 960 #define X first 961 #define Y second 962 #define SZ(x) int(x.size()) 963 #define all(x) x.begin(), x.end() 964 #define mins(a,b) (a = min(a,b)) 965 #define maxs(a,b) (a = max(a,b)) 966 #define pb push_back 967 #define Mp make_pair 968 #define lc id<<1 969 #define rc lc|1 970 #define mid ((l+r)>>1) 971 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 972 973 const ll INF = 1e9 + 23; 974 const ll MOD = 1e9 + 7; 975 const int MXN = 7e4+2; 976 const int LOG = 18; 977 978 int n; 979 string s; 980 vector<int> g[MXN]; 981 int dp[LOG][MXN]; 982 983 bool dead[MXN]; 984 int sz[MXN]; 985 int get_sz(int v, int p=0) { 986 sz[v] = 1; 987 for(int u : g[v]) 988 if(!dead[u] && u!=p) 989 sz[v] += get_sz(u, v); 990 return sz[v]; 991 } 992 int centroid(int v, int N, int p=0) { 993 for(int u : g[v]) 994 if(!dead[u] && u!=p && sz[u]+sz[u]>N) 995 return centroid(u, N, v); 996 return v; 997 } 998 999 vector<pair<int, int>> U; 1000 vector<pair<int, int>> G; 1001 int h[MXN], par[MXN]; 1002 1003 void dfs(int i, int v, int p=0) { 1004 if(s[v-1]=='1') { 1005 G.pb({h[v]<<1, v}); 1006 if(dp[i-1][v]>=2*h[v]) U.pb({dp[i-1][v]-2*h[v], v}); 1007 } 1008 for(int u : g[v]) 1009 if(!dead[u] && u!=p) 1010 par[u] = par[v], 1011 h[u] = h[v]+1, 1012 dfs(i, u, v); 1013 } 1014 1015 void solve(int i, int v) { 1016 dead[v=centroid(v,get_sz(v))] = 1; 1017 U.clear(); 1018 G.clear(); 1019 h[v] = 0; 1020 par[v] = v; 1021 if(s[v-1]=='1') { 1022 G.pb({h[v]<<1, v}); 1023 if(dp[i-1][v]>=2*h[v]) U.pb({dp[i-1][v]-2*h[v], v}); 1024 } 1025 for(int u : g[v]) 1026 if(!dead[u]) { 1027 par[u] = u; 1028 h[u] = 1; 1029 dfs(i, u); 1030 } 1031 sort(all(U), greater<>()); 1032 sort(all(G), greater<>()); 1033 int mx1=0, mx2=0, ptr=0; 1034 for(auto [lim, u] : G) { 1035 while(ptr<SZ(U) && U[ptr].X>=lim) { 1036 if(mx1 && par[mx1]==par[U[ptr].Y]) { 1037 if(h[U[ptr].Y]>h[mx1]) mx1 = U[ptr].Y; 1038 } 1039 else if(mx2 && par[mx2]==par[U[ptr].Y]) { 1040 if(h[U[ptr].Y]>h[mx2]) mx2 = U[ptr].Y; 1041 if(h[mx2]>h[mx1]) swap(mx1, mx2); 1042 } 1043 else { 1044 if(!mx1 || h[U[ptr].Y]>h[mx1]) mx2=mx1, mx1=U[ptr].Y; 1045 else if(!mx2 || h[U[ptr].Y]>h[mx2]) mx2=U[ptr].Y; 1046 } 1047 ptr++; 1048 } 1049 if(mx1) { 1050 if(mx1 && par[mx1]!=par[u]) maxs(dp[i][u], h[mx1]+h[u]); 1051 else if(mx2) maxs(dp[i][u], h[mx2]+h[u]); 1052 } 1053 } 1054 for(int u : g[v]) 1055 if(!dead[u]) 1056 solve(i, u); 1057 } 1058 1059 void Main() { 1060 cin >> n >> s; 1061 for(int i=1; i<=n; i++) g[i].clear(); 1062 for(int i=1,u,v; i<n; i++) { 1063 cin >> u >> v; 1064 g[u].pb(v); 1065 g[v].pb(u); 1066 } 1067 for(int i=1; i<=n; i++) 1068 if(s[i-1]=='1') 1069 dp[0][i] = 2*n-2; 1070 else 1071 dp[0][i] = -1; 1072 for(int i=1; i<LOG; i++) { 1073 fill(dead+1, dead+n+1, 0); 1074 fill(dp[i]+1, dp[i]+n+1, -1); 1075 solve(i, 1); 1076 } 1077 for(int i=1; i<=n; i++) 1078 if(s[i-1]=='1') { 1079 for(int j=LOG-1; j>=0; j--) 1080 if(dp[j][i]!=-1) { 1081 cout << j+1 << ' '; 1082 break; 1083 } 1084 } 1085 else cout << "-1 "; 1086 cout << '\n'; 1087 } 1088 1089 int32_t main() { 1090 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 1091 int T = 1; 1092 cin >> T; 1093 while(T--) Main(); 1094 return 0; 1095 } 1096 ``` 1097 1098 **Bonus** 1099 1100 We aimed to kill $log(n)^3$ implementations but then ended up making some correct $log(n)^2$ ones *TLE*, and gave up! 1101 1102 *What was your favorite part about this problem? Comment it below.* 1103 1104 ## [2101F - Shoo Shatters the Sunshine](/contest/2101/problem/F "Codeforces Round 1024 (Div. 1)") 1105 1106 **Hints** 1107 1108 **Hint 1** 1109 1110 What are some properties of such colored trees? 1111 1112 **Hint 2** 1113 1114 Is the farthest blue and red node unique? 1115 1116 **Hint 3** 1117 1118 Should we look for an $O(n^2)$ solution or optimizes a slower one? 1119 1120 **Solution** 1121 1122 **Note**: For the purpose of this editorial, the diameter of a colored tree is defined as a simple path with maximum coolness which has a blue and red node on each side. 1123 1124 Let's say a node is *special* iff the distance of the farthest blue node from it plus the distance of the farthesrt red node is equal to the length of the diameter of the tree. We also define a *special* edge as an edge such that the distances of the farthes red nodes on both sides are equal, and the distances of the blue nodes on each side are also equal to each other. Something like this: 1125 1126  1127 1128 We can see that the sum of distances of the farthest blue and green plus one is the length of the diameter. We claim that if there is no special node in a colored tree, then there must be a special edge. 1129 1130 **Proof**: If there is no special node in a tree, then that means the farthest red and blue node for each vertex are on one side of it. We know that if there is at least one blue and one red colored node, then we have a valid diameter, so considering each node *on* that diameter, becuase it is not a special node the farthest blue and red of it must be on one side, and this leasds us towards a speical edge, the formal proof is described later when discussing $T'$. 1131 1132 Let's make some more observations. It's easy to see that the diameter of a tree is not necessarily unique, but an interesting fact is that every two valid diameters **must** intersect with each other. 1133 1134 **Proof**: if not, consider the tree is rooted from the blue/red node of one diameter, this would trivially show us a new blue and red node that has a distance longer than our current diameter and therefore a contradiction. 1135 1136 This gives us the idea that the intersection of *all* valid diameters is a non-empty simple path on the tree. 1137 1138 **Proof**: Consider two diameters and take their intersection, then add the rest one by one and take the intersection of the intersections. If there are any two pairs with intersections that do not intersect, this means there exists a pair of valid diameters which do not intersect with each other, and this is against our hypothesis. 1139 1140 Before continuing, you must have an idea so far that we are aiming to count the trees with special node based on their node, and others based on their special edge, but there is still ***a lot*** to discuss. 1141 1142 Going back to the special nodes, it's easy to see that they must must be on our diameter, and what makes this more interesting is that they must be on all diameters! So, taking the simple path that was the intersection of all valid diameters, we know that all of our special nodes lie on this path. 1143 1144 Getting deeper on special nodes, we can see that for a non-special node such as $v$, the farthest blue and red are both on the same subtree if we root the tree from $v$. This makes the sum of distances to farthest red plus the farthest blue result in a number **always** bigger than the actual length of our diameter (as there is a shared part). Call the child in which both the farthest red and blue lie on a *cool* child. 1145 1146 Let's create another graph based on our tree (call it $T'$) that has identical nodes to the tree, and directed edges. For each non-special node, give a directed edge from the identical vertex in $T'$ to its *cool* child. It's easy to see that special nodes would not have any incoming edges to them in this new graph, but every non-special node has *at least* one. 1147 1148 We can use this graph to formally prove almost everything. Let's start with the fact that why any tree without a special node has a special edge? 1149 1150 **Proof**: No special edge means that there are $n$ nodes in our tree that each have an outgoing edge, therefore $n$ directed edges as well. Our initial tree had only $n-1$ edge, so therefore based on the pigeonhole principle, there must be an edge in the initial tree, that two directed edges pass above it. It's trivial that those edges cannot have the same direction, and therefore this will lead us to a directed cycle of length two. Well, think about it, this is exactly what a *special* edge is! 1151 1152 So if no special node is there, now we know that there is **at least** one special edge there somewhere. Well, it appears that we also cannot have more than one special edge in a colored tree. 1153 1154 **Proof**: If so, we know that both of them must appear *on* the diameter, and considering their placement, this will contradict the fact that the distance of red and blue from both sides must be equal. 1155 1156 Combining both above observations, now we know that if there is no special node in the colored tree, then there is **exactly one** special edge there somewhere. 1157 1158 Now let's solve the first sub-problem, which is how to solve the problem if there is no special node. Define $f(v, a, b)$ for a node $v$ as the number of colourings which the farthest blue has a distance of $a$, and the farthest red has a distance of $b$. How to calculate $f$? Define $g(v, a, b)$ as the same thing, but this time for the distance of ***at most*** $a$ for blue and ***at most*** $b$ for red. It's easy to see that if we somehow calculate $g(v, a, b)$, then the following equation holds: \begin{equation} f(v, a, b) = g(v, a, b) — g(v, a-1, b) — g(v, a, b-1) + g(v, a-1, b-1) \end{equation} And here's how we find $g(v, a, b)$: 1159 1160 \begin{equation} g(v, a, b) = 3^{p\cdot q}\cdot 1^r \end{equation} Where $p$ is the number of nodes such as $u$ that have a distance less than or equal to $a$, $q$ is the number of nodes that have a distance bigger than $a$ but less than or equal to $b$, and $r$ is the number of nodes that have a distance more than $b$. Formally: 1161 1162 $p = \#\{u \mid d(u, v) \le a \}$ $q = \#\{ u \mid a \lt d(u, v) \le b \}$ $r = \#\{ u \mid b \lt d(u, v) \}$ 1163 1164 This will so far give us an $O(n^3)$ solution, dw we'll optimize it further later. Now we count the result for each edge of the tree, considering it will be a special edge in some colourings. Call both sides of the edge $u$ and $v$ just like the diagram shown above. Assuming we have $f$ calculated for all nodes, the answer is: \begin{equation} \sum_{a=0}^{n} \sum_{b=0}^{n} f(u, a, b) \cdot f(v, a, b) \cdot (a + b + 1) \end{equation} We're halfway there! Before the optimizing part, the only question left is what if there is a special node? 1165 1166 Let's define a *super-special* node a node that is special, and not only does it have the farthest blue and red on different sides, but also either a blue node with distance one less than the farthest blue, or a red node with distance one less than the farthest red. 1167 1168 Using the same observations that we made earlier and a deeper understanding of $T'$, you can prove that there is **at least** one super-special node, also **at most** one super-special node, and therefore always exactly one super-special node if there exists at least one special node. For such trees, we aim to calculate the answer for them based on their super-special node. 1169 1170 Make the tree rooted from an arbitrary node. Define $dp_{v, i, a, b, j}$ as if you're in vertext $v$, you iterated $i$ children, so far the farthest blue node has a distance of $a$, the farthest red node has a distance of $b$, and $j=0$ if these two don't belong to one subtree (if possible, preferably $0$), and $1$ otherwise. Iterate over new subtrees and use the $f$ function defined before to end up with a computable $O(n^4)$ implementation! 1171 1172 Now add another dimension $k$ to the above DP to keep track of if there is any blue node with distance one less than the farthest blue, or a red node with distance one less than the farthest red. Note that this really doesn't change anything. 1173 1174 The above DP, though correct, won't give us a good solution and is only explained for gaining deeper insight. After truly understanding what is going on and what we are looking for, we can break down the same idea and calculate it manually, which will result in a $O(n^2)$ solution in the end. The primary fact to notice is that if the number of edges between two farthest red vertices is even, then it can be proven that the middle vertex of this path is a special node, and if odd, the middle edge is a special edge. As explaining everything in detail takes forever, try to prove the things we missed yourself and ask if you encountered any issues. 1175 1176 **Code (C++)** 1177 1178 ``` 1179 #include <bits/stdc++.h> 1180 using namespace std; 1181 1182 using ll = long long; 1183 using ld = long double; 1184 using pii = pair<int, int>; 1185 using pll = pair<long long, long long>; 1186 using ull = unsigned long long; 1187 1188 #define X first 1189 #define Y second 1190 #define SZ(x) int(x.size()) 1191 #define all(x) x.begin(), x.end() 1192 #define mins(a,b) (a = min(a,b)) 1193 #define maxs(a,b) (a = max(a,b)) 1194 #define pb push_back 1195 #define Mp make_pair 1196 #define lc id<<1 1197 #define rc lc|1 1198 #define mid ((l+r)>>1) 1199 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 1200 1201 const ll INF = 1e9 + 23; 1202 const ll MOD = 998244353; 1203 const int MXN = 3006; 1204 const int LOG = 23; 1205 1206 template<typename T> 1207 inline T md(T x) { return x — (x>=MOD ? MOD : 0); } 1208 template<typename T> 1209 inline void fix(T &x) { x = md(x); } 1210 1211 int n; 1212 vector<int> g[MXN]; 1213 vector<int> H[MXN]; 1214 int cnt[MXN], pscnt[MXN]; 1215 ll red[MXN], redb[MXN]; 1216 ll two[MXN], thr[MXN], itwo[MXN]; 1217 ll ans; 1218 ll ps[MXN]; 1219 1220 void dfs(int v, int h=0, int p=-1) { 1221 cnt[h]++; 1222 H[h].back()++; 1223 for(int u : g[v]) 1224 if(u!=p) 1225 dfs(u, h+1, v); 1226 } 1227 1228 void Main() { 1229 cin >> n; 1230 for(int i=1; i<=n; i++) g[i].clear(); 1231 ans = 0; 1232 for(int i=0, u,v; i<n-1; i++) { 1233 cin >> u >> v; 1234 g[u].pb(v); 1235 g[v].pb(u); 1236 } 1237 for(int v=1; v<=n; v++) { 1238 for(int adj=-1; adj<SZ(g[v]); adj++) { 1239 for(int i=0; i<n; i++) H[i].clear(), cnt[i]=0; 1240 if(adj==-1) { 1241 cnt[0]++; 1242 for(int u : g[v]) { 1243 for(int i=0; i<n; i++) H[i].pb(0); 1244 dfs(u, 1, v); 1245 } 1246 } 1247 else { 1248 if(g[v][adj]<v) continue; 1249 for(int i=0; i<n; i++) H[i].pb(0); 1250 dfs(v, 0, g[v][adj]); 1251 for(int i=0; i<n; i++) H[i].pb(0); 1252 dfs(g[v][adj], 0, v); 1253 } 1254 pscnt[0] = cnt[0]; 1255 for(int i=1; i<n; i++) pscnt[i] = pscnt[i-1] + cnt[i]; 1256 red[0] = 1; 1257 redb[0] = 1; 1258 for(int i=1; i<n; i++) { 1259 red[i] = two[cnt[i]]-1; 1260 for(int a : H[i]) 1261 fix(red[i] += MOD-(two[a]-1)); 1262 redb[i] = md(thr[cnt[i]]-two[cnt[i]]+MOD); 1263 for(int a : H[i]) 1264 fix(redb[i] += MOD-(thr[a]-two[a]+MOD)*two[cnt[i]-a]%MOD); 1265 } 1266 for(int i=0; i<n; i++) { 1267 ps[i] = red[i]*two[i==0?0:pscnt[i-1]]%MOD*(i+(adj!=-1))%MOD; 1268 if(i) fix(ps[i] += ps[i-1]); 1269 } 1270 for(int j=0; j<n; j++) 1271 fix(ans += thr[j==0?0:pscnt[j-1]] 1272 *(thr[cnt[j]]-two[cnt[j]]+MOD)%MOD 1273 *itwo[pscnt[j]]%MOD 1274 *(ps[n-1]-ps[j]+MOD)%MOD); 1275 for(int i=0; i<n; i++) { 1276 ps[i] = red[i]*two[i==0?0:pscnt[i-1]]%MOD; 1277 if(i) fix(ps[i] += ps[i-1]); 1278 } 1279 for(int j=0; j<n; j++) 1280 fix(ans += thr[j==0?0:pscnt[j-1]] 1281 *(thr[cnt[j]]-two[cnt[j]]+MOD)%MOD 1282 *itwo[pscnt[j]]%MOD 1283 *j%MOD 1284 *(ps[n-1]-ps[j]+MOD)%MOD); 1285 for(int i=0; i<n; i++) { 1286 ps[i] = redb[i] 1287 *thr[i==0?0:pscnt[i-1]]%MOD 1288 *itwo[pscnt[i]]%MOD 1289 *(i+(adj!=-1))%MOD; 1290 if(i) fix(ps[i] += ps[i-1]); 1291 } 1292 for(int j=1; j<n; j++) 1293 fix(ans += two[pscnt[j-1]]%MOD 1294 *(two[cnt[j]]-1)%MOD 1295 *ps[j-1]%MOD); 1296 for(int i=0; i<n; i++) { 1297 ps[i] = redb[i] 1298 *thr[i==0?0:pscnt[i-1]]%MOD 1299 *itwo[pscnt[i]]%MOD; 1300 if(i) fix(ps[i] += ps[i-1]); 1301 } 1302 for(int j=1; j<n; j++) 1303 fix(ans += two[pscnt[j-1]]%MOD 1304 *(two[cnt[j]]-1)%MOD 1305 *j%MOD 1306 *ps[j-1]%MOD); 1307 for(int i=0; i<n; i++) { 1308 fix(ans += (redb[i]-red[i]+MOD)*thr[i==0?0:pscnt[i-1]]%MOD*(i+i+(adj!=-1))%MOD); 1309 } 1310 } 1311 } 1312 cout << ans << '\n'; 1313 } 1314 1315 int32_t main() { 1316 cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 1317 int T = 1; 1318 cin >> T; 1319 two[0] = 1; 1320 for(int i=1; i<MXN; i++) two[i] = two[i-1]*2%MOD; 1321 thr[0] = 1; 1322 for(int i=1; i<MXN; i++) thr[i] = thr[i-1]*3%MOD; 1323 itwo[0] = 1; 1324 for(int i=1; i<MXN; i++) itwo[i] = itwo[i-1]*((MOD+1)/2)%MOD; 1325 while(T--) Main(); 1326 return 0; 1327 } 1328 ``` 1329 1330 **Bonus** 1331 1332 The intended solution was the $O(n^3)$ discussed with some further optimizations, but then a new $O(n^2)$ solution showed up that changed everything! We thought of dividing the problem into two subtasks, but didn't do so, as the observation required for the $O(n^2)$ solution was quite beautiful. 1333 1334 Also, we would like to thank [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") for his contributions to this problem.