1987.md (24662B)
1 Source: https://codeforces.com/blog/entry/131053 2 3 Hope you liked the problems! We apologize for the (very?) weak tests in H. 4 5 Editorials for problems will be added over time (and hints), for now, please take a look at the available hints and model solutions. 6 7 **Easter eggs** 8 9 **A** 10 11 ForceCodes is a reference CrossCode, you should try it. 12 13 **C** 14 15 Basil is one of the characters in OMORI, you should also try it. 16 17 **D** 18 19 "World is Mine" is one of Hatsune Miku's most well known songs, and a fan-made MV has a lot of cakes in it) I originally wanted to make the characters names Miku and Sweetheart(from OMORI), but decided to stick to Alice and Bob to keep the statement clean. 20 21 **E** 22 23 The epigraph is a reference to KonoSuba. 24 25 **H** 26 27 The epigraph is a quote from Celeste (you should try it), and the title is a reference to one of it's locations, Mirror Temple, but only now there are fumo dolls in it) 28 29 [1987A - Upload More RAM](/contest/1987/problem/A) 30 31 **Hints** 32 33 **Hint 1** 34 35 Your strategy is to upload more RAM as soon as you can upload. 36 37 **Hint 2** 38 39 You will upload on the seconds $1, k + 1, 2k + 1, 3k + 1 \ldots$. 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 #define all(x) (x).begin(), (x).end() 51 #define allr(x) (x).rbegin(), (x).rend() 52 53 const char nl = '\n'; 54 typedef long long ll; 55 typedef long double ld; 56 57 using namespace std; 58 59 void solve() { 60 int n, k; 61 cin >> n >> k; 62 cout << 1 + (n - 1) * k << nl; 63 } 64 65 int main() { 66 ios::sync_with_stdio(0); cin.tie(0); 67 68 int t; 69 cin >> t; 70 while (t--) { 71 solve(); 72 } 73 } 74 ``` 75 76 **Feedback** 77 78 * Good problem 79 * Average problem 80 * Bad problem 81 82 [1987B - K-Sort](/contest/1987/problem/B) 83 84 **Hints** 85 86 **Hint 1** 87 88 Try solving the problem if instead of paying $k + 1$ coins, you pay $k$ coins. 89 90 **Hint 2** 91 92 What if you pay only $1$ coin per operation? 93 94 **Hint 3** 95 96 Can you add the answers to the $k$ coins per operation problem and $1$ coin per operation problem to get the answer? 97 98 **Tutorial** 99 100 Tutorial is loading... 101 102 **Solution** 103 104 ``` 105 #include <bits/stdc++.h> 106 107 #define all(x) (x).begin(), (x).end() 108 #define allr(x) (x).rbegin(), (x).rend() 109 110 const char nl = '\n'; 111 typedef long long ll; 112 typedef long double ld; 113 114 using namespace std; 115 116 void solve() { 117 int n; 118 cin >> n; 119 120 vector<int> a(n); 121 for (int i = 0; i < n; i++) cin >> a[i]; 122 123 ll pref_max = 0, s = 0, mx = 0; 124 for (int i = 0; i < n; i++) { 125 pref_max = max(pref_max, (ll) a[i]); 126 127 ll d = pref_max - a[i]; 128 s += d; 129 mx = max(mx, d); 130 } 131 132 cout << s + mx << nl; 133 } 134 135 int main() { 136 ios::sync_with_stdio(0); cin.tie(0); 137 138 int T; 139 cin >> T; 140 while (T--) { 141 solve(); 142 } 143 } 144 ``` 145 146 **Feedback** 147 148 * Good problem 149 * Average problem 150 * Bad problem 151 152 [1987C - Basil's Garden](/contest/1987/problem/C) 153 154 **Hints** 155 156 **Hint 1** 157 158 When will $h_n$ first become equal to zero? 159 160 **Hint 2** 161 162 When will $h_{n-1}$ first become equal to zero? 163 164 **Hint 3** 165 166 Consider solving from right to left. 167 168 **Hint 4** 169 170 Suppose you want to find when $h_i$ will fist be equal to zero. Try splitting into the cases $h_i = h_{i+1}$ at some point (before both are zero) and when that is not true. 171 172 **Tutorial** 173 174 Tutorial is loading... 175 176 **Solution** 177 178 ``` 179 #include <bits/stdc++.h> 180 181 #define all(x) (x).begin(), (x).end() 182 #define allr(x) (x).rbegin(), (x).rend() 183 184 const char nl = '\n'; 185 typedef long long ll; 186 typedef long double ld; 187 188 using namespace std; 189 190 void solve() { 191 int n; 192 cin >> n; 193 194 vector<int> h(n); 195 for (auto &x: h) cin >> x; 196 197 int ans = h[n - 1]; 198 for (int i = n - 2; i >= 0; i--) { 199 ans = max(ans + 1, h[i]); 200 } 201 202 cout << ans << nl; 203 } 204 205 int main() { 206 ios::sync_with_stdio(0); cin.tie(0); 207 208 int T; 209 cin >> T; 210 while (T--) solve(); 211 } 212 ``` 213 214 **Feedback** 215 216 * Good problem 217 * Average problem 218 * Bad problem 219 220 [1987D - World is Mine](/contest/1987/problem/D) 221 222 **Hints** 223 224 **Hint 1** 225 226 Alice's optimal strategy is simple (and kind of fixed). 227 228 **Hint 2** 229 230 Alice always eats the least tasty cake that she can eat. 231 232 **Hint 3** 233 234 Convert the given array to it's count array $c_i$, for example, the array $[1, 5, 1, 2, 1, 5, 1]$ becomes $[4, 1, 2]$. 235 236 **Hint 4** 237 238 Consider a set of $k$ indices that Bob will choose to eat ($c_{i_1} + ... + c_{i_k}$ cakes in total). What are the necessary conditions for him to be able to do that? 239 240 **Hint 5** 241 242 For a set of $k$ indices $1 \le i_1 \le i_2 \le \ldots \le i_k \le |c|$, the condition $\sum_{j=1}^{p}{c_{i_j}} \le i_p - p$ must hold for all $1 \le p \le k$. 243 244 **Tutorial** 245 246 Tutorial is loading... 247 248 **Solution** 249 250 ``` 251 #include <bits/stdc++.h> 252 253 #define all(x) (x).begin(), (x).end() 254 #define allr(x) (x).rbegin(), (x).rend() 255 256 const char nl = '\n'; 257 typedef long long ll; 258 typedef long double ld; 259 260 using namespace std; 261 262 const int inf = 1e9; 263 264 void solve() { 265 vector<int> a; 266 { 267 int n; 268 cin >> n; 269 270 map<int, int> cnt; 271 while (n--) { 272 int x; 273 cin >> x; 274 cnt[x]++; 275 } 276 277 for (auto const &[k, v]: cnt) { 278 a.push_back(v); 279 } 280 } 281 282 int n = a.size(); 283 vector<int> dp(n + 1, inf); 284 dp[0] = 0; 285 286 for (int i = 1; i <= n; i++) { 287 vector<int> ndp = dp; 288 289 for (int k = 1; k <= n; k++) { 290 int nv = dp[k - 1] + a[i - 1]; 291 292 if (nv <= i - k) { 293 ndp[k] = min(ndp[k], nv); 294 } 295 } 296 297 dp = ndp; 298 } 299 300 int ans = n; 301 while (dp[ans] >= inf) ans--; 302 cout << n - ans << nl; 303 } 304 305 int main() { 306 ios::sync_with_stdio(0); cin.tie(0); 307 308 int T; 309 cin >> T; 310 while (T--) solve(); 311 } 312 ``` 313 314 **Feedback** 315 316 * Good problem 317 * Average problem 318 * Bad problem 319 320 [1987E - Wonderful Tree!](/contest/1987/problem/E) 321 322 **Hints** 323 324 **Hint 1** 325 326 Let $b_v = \displaystyle{\sum_{u \in L}{a_u} - a_v}$ if $L$ is not empty and $+\infty$ otherwise. What does the operation do to the values of $b$? What does the objective change to? 327 328 **Hint 2** 329 330 Let $v$ be an ancestor of $w$ and $d_v \lt d_w$ ($d$ is the depth array). Then, you can add $1$ to $b_v$ and subtract $1$ from $b_w$ in $d_w - d_v$ operations. Let this be our new operation on a pair of vertices $(v, w)$. 331 332 **Hint 3** 333 334 Suppose one optimal sequence of operations uses it on $(v_1, w_1)$ and $(v_2, w_2)$, and the paths $v_1 \rightarrow w_1$ and $v_2 \rightarrow w_2$ intersect. Let $d_{v1} \le d_{v2}$. Then, if $d_{w1} \le d_{w2}$, it is not less optimal to apply the operation on $(v_1, w_2)$ and $(v_2, w_1)$. 335 336 **Hint 4** 337 338 Pick the closest vertex to $v$ while $b_v \lt 0$. 339 340 **Tutorial** 341 342 Tutorial is loading... 343 344 **Solution** 345 346 ``` 347 #include <bits/stdc++.h> 348 349 #define all(x) (x).begin(), (x).end() 350 #define allr(x) (x).rbegin(), (x).rend() 351 352 const char nl = '\n'; 353 typedef long long ll; 354 typedef long double ld; 355 356 using namespace std; 357 358 const ll inf = 1e15; 359 360 void solve() { 361 int n; 362 cin >> n; 363 364 vector<int> a(n); 365 for (auto &x: a) cin >> x; 366 367 vector<int> d(n); 368 vector<vector<int>> g(n); 369 for (int i = 1; i < n; i++) { 370 int p; 371 cin >> p; 372 p--; 373 374 g[p].push_back(i); 375 d[i] = d[p] + 1; 376 } 377 378 vector<ll> b(n); // b[v] = sum(a[u]) - a[v] 379 for (int v = 0; v < n; v++) { 380 if (g[v].empty()) { 381 b[v] = inf; 382 } else { 383 b[v] = -a[v]; 384 385 for (int u: g[v]) { 386 b[v] += a[u]; 387 } 388 } 389 } 390 391 ll ans = 0; 392 for (int v = n - 1; v >= 0; v--) { 393 queue<int> q; 394 395 q.push(v); 396 while (!q.empty()) { 397 int i = q.front(); 398 q.pop(); 399 400 for (int u: g[i]) { 401 ll delta = min(-b[v], b[u]); 402 403 if (delta > 0) { 404 b[v] += delta; 405 b[u] -= delta; 406 ans += delta * (d[u] - d[v]); 407 } 408 409 q.push(u); 410 } 411 } 412 } 413 414 cout << ans << nl; 415 } 416 417 int main() { 418 ios::sync_with_stdio(0); cin.tie(0); 419 420 int T; 421 cin >> T; 422 while (T--) { 423 solve(); 424 } 425 } 426 ``` 427 428 **Feedback** 429 430 * Good problem 431 * Average problem 432 * Bad problem 433 434 [1987F1 - Interesting Problem (Easy Version)](/contest/1987/problem/F1) and [1987F2 - Interesting Problem (Hard Version)](/contest/1987/problem/F2) 435 436 **Hints** 437 438 **Hint 1** 439 440 Does the operation have any connection to balanced bracket sequences? 441 442 **Tutorial** 443 444 Tutorial is loading... 445 446 **Solution (F2)** 447 448 ``` 449 #include <bits/stdc++.h> 450 451 #define all(x) (x).begin(), (x).end() 452 #define allr(x) (x).rbegin(), (x).rend() 453 454 const char nl = '\n'; 455 typedef long long ll; 456 typedef long double ld; 457 458 using namespace std; 459 460 const int inf = 1e9; 461 462 void solve() { 463 int n; 464 cin >> n; 465 466 vector<int> a(n); 467 for (int i = 0; i < n; i++) cin >> a[i]; 468 469 470 vector<vector<int>> dp(n + 1, vector<int> (n + 1, inf)); 471 472 for (int i = 0; i <= n; i++) { 473 dp[i][i] = 0; 474 } 475 476 for (int le = 1; le <= n; le++) { 477 for (int l = 0; l + le <= n; l++) { 478 if (a[l] % 2 != (l + 1) % 2) continue; 479 if (a[l] > l + 1) continue; 480 int v = (l + 1 - a[l]) / 2; 481 482 int r = l + le; 483 for (int m = l + 1; m < r; m += 2) { // index of the closing bracket 484 if (dp[l + 1][m] <= v) { 485 int new_val = max(v, dp[m + 1][r] - (m - l + 1) / 2); 486 dp[l][r] = min(dp[l][r], new_val); 487 } 488 } 489 } 490 } 491 492 vector<int> dp2(n + 1); 493 for (int i = 0; i < n; i++) { 494 dp2[i + 1] = dp2[i]; 495 496 for (int j = 0; j < i; j++) { 497 if (dp[j][i + 1] <= dp2[j]) { 498 dp2[i + 1] = max(dp2[i + 1], dp2[j] + (i - j + 1) / 2); 499 } 500 } 501 } 502 503 cout << dp2[n] << nl; 504 } 505 506 int main() { 507 ios::sync_with_stdio(0); cin.tie(0); 508 509 int T; 510 cin >> T; 511 while (T--) { 512 solve(); 513 } 514 } 515 ``` 516 517 **Feedback (F1)** 518 519 * Good problem 520 * Average problem 521 * Bad problem 522 523 **Feedback (F2)** 524 525 * Good problem 526 * Average problem 527 * Bad problem 528 529 [1987G1 - Spinning Round (Easy Version)](/contest/1987/problem/G1) 530 531 **Hints** 532 533 Meow? (Waiting for something to happen?) 534 535 **Tutorial (by errorgorn)** 536 537 Consider that the edges are directed from $i \to l_i$ or $i \to r_i$ respectively. So that edges point from vertices with smaller values to vertices with larger values. That is $a \to b$ implies that $p_a \lt p_b$. 538 539 Notice that by definition, every vertex must have only $1$ edge that is going out of it. Therefore, if we consider the diameter to be something like $v_1 \to v_2 \to v_3 \to \ldots \to v_k \leftarrow \ldots \leftarrow v_{d-1} \leftarrow v_{d}$, since it is impossible for there to be some $\leftarrow v_i \to$ since each vertex has exactly one edge going out of it. 540 541 Therefore, it makes that we can split the path into 2 distinct parts: - $v_1 \to v_2 \to v_3 \to \ldots \to v_k$ - $v_d \to v_{d-1} \to \ldots \to v_{k}$ 542 543 I claim that I can choose some $m$ such that the path $v_1 \to v_2 \to v_3 \to \ldots \to v_{k-1}$ and $v_d \to v_{d-1} \to \ldots \to v_{k+1}$ are in the range $[1,m]$ and $[m+1,n]$ or vice versa. That we are able to cut the array into half and each path will stay on their side. 544 545  546 547 The red line shown above is the cutting line, as described. Proof is at the bottom under Proof 1 for completeness. 548 549 Now, we want to use this idea to make a meet in the middle solutions where we merge max stacks from both sides. Specifically: - maintain a max stack of elements as we are sweeping from $i=1\ldots n$. - for each element on the max stack, maintain the maximum size of a path that is rooted on that element. 550 551 Here is an example with $p=[4,1,5,3,2,6]$ 552 553 * $i=1$: $s=[(4,1)]$ 554 * $i=2$: $s=[(4,2),(1,1)]$ 555 * $i=3$: $s=[(5,3)]$ 556 * $i=4$: $s=[(5,3),(3,1)]$ 557 * $i=5$: $s=[(5,3),(3,2),(2,1)]$ 558 * $i=6$: $s=[(6,4)]$ 559 560 When we insert a new element $x$, we pop all $(p_i,val)$ with $p_i \lt p_x$ and add in $(x,\max(val)+1)$ into the stack. Now, all elements of the stack has to updated with $s_{i,1} := \max(s_{i,1},s_{i+1,1}+1)$, which is really updating a suffix of $s_{*,1}$ with $val+k,\ldots,val+1,val$. 561 562 Firstly, it is clear that the $2$ vertices we merge, should have the biggest $p_i$ value, since a bigger $p_i$ value implies a bigger path size. 563 564 What we care about is the biggest path size possible only using vertices on $[1,i]$, which we denote array $best$. In the above example, $best = [1,2,3,3,4]$. We really only care about obtaining the array $best$ and not $s$. We can find this array in $O(n \log n)$ using segment trees or even in $O(n)$. 565 566 However, we cannot directly take the biggest values on each side. Consider $p=[2,1\mid,3,4]$. On the left and right side, the max stacks are $[2,1]$ and $[4,3]$ respectively, but we cannot connect $2$ with $4$ since the $3$ is blocking the $2$. 567 568 Suppose $a_1,a_2,\ldots,a_s$ are the prefix maximums while $b_1,b_2,\ldots,b_t$ are the suffix maximums. 569 570 Then, if the dividing line is at $a_i \leq m \lt a_{i+1}$, we will merge $a_i$ on the left side with $a_{i+1}$ on the right side. Similarly, if the dividing line is at $b_i \leq m \lt b_{i+1}$, we will merge $b_i$ on the left side with $b_{i+1}$ on the right side. 571 572 So, if $a_i \leq m \lt a_{i+1}$, it is equivalent to merging the best path on $[1,m]$ and $(m,a_{i+1})$ since then $a_{i+1}$ will be the root of the best path on the right side. It is similar for $b_i \leq m \lt b_{i+1}$. 573 574 Actually, we can prove that instead of $(m,a_{i+1})$, $(m,a_{i})$ is enough, and the proof is left as an exercise. 575 576 The total complexity becomes $O(n \log n)$ or $O(n)$ depending on how quickly array $best$ is found for subarrays. 577 578 ### Proof 1 579 580 Suppose that there are 2 paths $a_1 \to a_2 \to \ldots \to a_s$ and $b_1 \to b_2 \to \ldots \to b_t$, $a_1 \lt b_1$, and $a_s = b_t$ but they do not intersect at any vertices other vertices. Then we will prove that there is no such case where $a_s' \gt b_t'$. 581 582 Suppose that it is true that we can find some $a_{s'} \gt b_{t'}$. 583 584 Let $(s',t')$ be the minimum counterexample so that $a_{s'} \gt b_{t'}$ but $a_{s'-1} \lt b_{t}$. Therefore, we have $a_{s'-1} \lt b_t \lt a_{s'}$. By definition, that $r_{a_{s'-1}} = a_{s'}$, we have $p_{b_t} \lt p_{a_{s'-1}}$. 585 586 Then, $a_s$ cannot be in between $a_{s'-1}$ and $a_{s'}$ or else $r_{a_{s'-1}} = a_{s} \neq a_{s'}$. But, then we need to find a path from $b_{t'}$ to $b_{t}=a_{s}$ which does not touch either $a_{s'-1}$ or $a_{s'}$ which is impossible. 587 588 **Solution** 589 590 ``` 591 #include <bits/stdc++.h> 592 using namespace std; 593 594 #define ii pair<int,int> 595 #define fi first 596 #define se second 597 598 #define pub push_back 599 #define pob pop_back 600 601 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 602 #define sz(x) (int)(x).size() 603 604 int n; 605 int arr[400005]; 606 string s; 607 608 int ans[2][400005]; 609 int t[400005]; 610 vector<int> stk[2]; 611 612 vector<ii> process(int l,int r,int val[]){ 613 vector<ii> v; 614 int curr=0; 615 616 rep(x,l,r+1){ 617 ii res={x,0}; 618 while (!v.empty() && arr[v.back().fi]<arr[x]){ 619 int t=v.back().se; v.pob(); 620 if (!v.empty()) v.back().se=max(v.back().se,t+1); 621 res.se=max(res.se,t+1); 622 } 623 v.pub(res); 624 625 curr=max(curr,res.se+sz(v)); 626 val[x]=curr; 627 } 628 629 return v; 630 } 631 632 signed main(){ 633 ios::sync_with_stdio(0); 634 cin.tie(0); 635 cout.tie(0); 636 cin.exceptions(ios::badbit | ios::failbit); 637 638 int TC; 639 cin>>TC; 640 while (TC--){ 641 cin>>n; 642 rep(x,1,n+1) cin>>arr[x]; 643 cin>>s; 644 645 rep(z,0,2){ 646 auto v=process(1,n,ans[z]); 647 stk[z].clear(); 648 for (auto [a,b]:v) stk[z].pub(a); 649 reverse(arr+1,arr+n+1); 650 } 651 652 int mx=ans[0][stk[0][0]]+ans[1][n-stk[0][0]+1]-1; 653 654 rep(z,0,2){ 655 rep(x,0,sz(stk[z])-1){ 656 process(stk[z][x],stk[z][x+1],t); 657 rep(y,stk[z][x],stk[z][x+1]) mx=max(mx,t[y]+ans[z^1][n-y]); 658 } 659 660 reverse(arr+1,arr+n+1); 661 } 662 663 cout<<mx-1<<endl; 664 } 665 } 666 ``` 667 668 **Feedback** 669 670 * Good problem 671 * Average problem 672 * Bad problem 673 674 [1987G2 - Spinning Round (Hard Version)](/contest/1987/problem/G2) 675 676 **Hints** 677 678 **Hint 1** 679 680 Consider $dp[l_i][r_i] = $ a set of pairs $(a, b)$ of possible depths of two paths that do not intersect and start from $l_i$ and $r_i$ respectively. 681 682 **Hint 2** 683 684 You only need to store only a couple of pairs in $dp[l_i][r_i]$. 685 686 **Tutorial** 687 688 Tutorial is loading... 689 690 **Solution** 691 692 ``` 693 #include <bits/stdc++.h> 694 695 #define all(x) (x).begin(), (x).end() 696 #define allr(x) (x).rbegin(), (x).rend() 697 698 const char nl = '\n'; 699 typedef long long ll; 700 typedef long double ld; 701 702 using namespace std; 703 704 array<vector<int>, 2> get_l_and_r(vector<int> &p) { 705 int n = p.size(); 706 707 vector<int> l(n), r(n); 708 709 stack<int> s; 710 for (int i = 0; i < n; i++) { 711 while (!s.empty() && p[s.top()] < p[i]) s.pop(); 712 713 if (s.empty()) l[i] = -1; 714 else l[i] = s.top(); 715 716 s.push(i); 717 } 718 719 s = {}; 720 for (int i = n - 1; i >= 0; i--) { 721 while (!s.empty() && p[s.top()] < p[i]) s.pop(); 722 723 if (s.empty()) r[i] = n; 724 else r[i] = s.top(); 725 726 s.push(i); 727 } 728 729 return {l, r}; 730 } 731 732 int ans_l_edge(array<int, 2> d, array<int, 2> e) { 733 return d[0] + 1 + max(d[1], e[0]); 734 } 735 736 int ans_r_edge(array<int, 2> d, array<int, 2> e) { 737 return e[1] + 1 + max(d[1], e[0]); 738 } 739 740 array<int, 2> add_l_edge(array<int, 2> d, array<int, 2> e) { 741 return {max({d[0], d[1] + 1, e[0] + 1}), e[1]}; 742 } 743 744 array<int, 2> add_r_edge(array<int, 2> d, array<int, 2> e) { 745 return {d[0], max({d[1] + 1, e[0] + 1, e[1]})}; 746 } 747 748 vector<array<int, 2>> process_dp(vector<array<int, 2>> &dp) { 749 array<int, 2> max_a = {-1, -1}, max_b = {-1, -1}, max_s = {-1, -1}; 750 751 for (auto [a, b]: dp) { 752 if (a > max_a[0] || (a == max_a[0] && b > max_a[1])) { 753 max_a = {a, b}; 754 } 755 756 if (b > max_b[1] || (b == max_b[1] && a > max_b[0])) { 757 max_b = {a, b}; 758 } 759 760 if (a + b > max_s[0] + max_s[1]) { 761 max_s = {a, b}; 762 } 763 } 764 765 return {max_a, max_b, max_s}; 766 } 767 768 void add_to_map(map<array<int, 2>, int> &dp_ind, int &len_dp, array<int, 2> a) { 769 if (!dp_ind.count(a)) { 770 dp_ind[a] = len_dp++; 771 } 772 } 773 774 void solve() { 775 int n; 776 cin >> n; 777 778 vector<int> p(n); 779 for (int i = 0; i < n; i++) cin >> p[i]; 780 781 string s; 782 cin >> s; 783 784 auto [l, r] = get_l_and_r(p); 785 786 for (int i = 0; i < n; i++) { 787 if (p[i] == n) continue; 788 789 if (l[i] == -1 && s[i] == 'L') { 790 cout << -1 << nl; 791 return; 792 } 793 794 if (r[i] == n && s[i] == 'R') { 795 cout << -1 << nl; 796 return; 797 } 798 } 799 800 int ans = 0; 801 802 vector<int> q(n + 1); 803 for (int i = 0; i < n; i++) { 804 q[p[i]] = i; 805 } 806 807 int len_dp = 0; 808 map<array<int, 2>, int> dp_ind; 809 810 for (int x = 1; x <= n; x++) { 811 int i = q[x]; 812 int tl = l[i], tr = r[i]; 813 814 add_to_map(dp_ind, len_dp, {tl, i}); 815 add_to_map(dp_ind, len_dp, {i, tr}); 816 add_to_map(dp_ind, len_dp, {tl, tr}); 817 } 818 819 vector<vector<array<int, 2>>> dp(len_dp, {{0, 0}}); 820 for (int x = 1; x <= n; x++) { 821 int i = q[x]; 822 int tl = l[i], tr = r[i]; 823 824 int ind_l = dp_ind[{tl, i}]; 825 int ind_r = dp_ind[{i, tr}]; 826 int ind_c = dp_ind[{tl, tr}]; 827 828 for (auto const &d: dp[ind_l]) { 829 for (auto const &e: dp[ind_r]) { 830 ans = max(ans, d[1] + e[0]); 831 832 if (tl >= 0 && s[i] != 'R') { 833 ans = max(ans, ans_l_edge(d, e)); 834 dp[ind_c].push_back(add_l_edge(d, e)); 835 } 836 837 if (tr <= n - 1 && s[i] != 'L') { 838 ans = max(ans, ans_r_edge(d, e)); 839 dp[ind_c].push_back(add_r_edge(d, e)); 840 } 841 } 842 } 843 844 dp[ind_c] = process_dp(dp[ind_c]); 845 } 846 847 cout << ans << nl; 848 } 849 850 int main() { 851 ios::sync_with_stdio(0); cin.tie(0); 852 853 int T; 854 cin >> T; 855 while (T--) { 856 solve(); 857 } 858 } 859 ``` 860 861 **Feedback** 862 863 * Good problem 864 * Average problem 865 * Bad problem 866 867 [1987H - Fumo Temple](/contest/1987/problem/H) 868 869 Please try solving the problem with a deterministic solution :) 870 871 **Hints** 872 873 **Hint 1** 874 875 Think of the query result as some number between $|i - i_0| + |j - j_0|$ and $|i - i_0| + |j - j_0| + (|i - i_0| + 1) \cdot (|j - j_0| + 1)$. 876 877 **Hint 2** 878 879 Try solving for $n = 1$. 880 881 **Hint 3** 882 883 Try solving in $n \log_2(m)$ queries (might be useful later). 884 885 **Hint 4** 886 887 Try to either decrease $n$ by a bit, or decrease $m$ by a lot. 888 889 **Hint 5** 890 891 One way to do that would be to either decrease $n$ by $3$ or decrease $m$ by a lot. 892 893 **Hint 6** 894 895 Make all the queries in the middle row of a three row strip. 896 897 **Hint 7** 898 899 "Binary search" base case for small $m$. 900 901 **Tutorial** 902 903 Tutorial is loading... 904 905 **Solution** 906 907 ``` 908 #include <bits/stdc++.h> 909 910 #define all(x) (x).begin(), (x).end() 911 #define allr(x) (x).rbegin(), (x).rend() 912 913 const char nl = '\n'; 914 typedef long long ll; 915 typedef long double ld; 916 917 using namespace std; 918 919 int ans_x = 0, ans_y = 0, cnt_q = 0; 920 // Coordinates are flipped 921 int query(int x, int y) { 922 cnt_q++; 923 924 int res = 0; 925 cout << "? " << y << ' ' << x << endl; 926 cout.flush(); 927 928 cin >> res; 929 930 if (res < 0) { 931 exit(0); 932 } 933 934 if (res == 0) { 935 ans_x = x; 936 ans_y = y; 937 } 938 939 return res; 940 } 941 942 /* Explanation: 943 * Splits the stripe of three into |a-O-a-b-O-b-a-O-a|. 944 * O are the three query points (all in the same column). 945 * Cons: hard to correctly account for errors in a non-bruteforce way. 946 * Pros: gives a better constant factor (3 / 4 of the original length) 947 * Number of queries: n + 3 * 21 + 25 * ceil(log(25, 2)) + eps 948 * Though the binary search part uses less queries than that */ 949 950 void f(int lx, int rx, int ly, int ry) { 951 int n = rx - lx + 1; 952 953 // Bruteforce base case (uses binary search) 954 if (n <= 25) { // can be n <= 22 or above 955 for (int x = lx; x <= rx; x++) { 956 int lb = ly, ub = ry; 957 958 while (lb <= ub) { 959 int res = query(x, lb); 960 961 int low_y = ((res - 1) + 1) / 2, high_y = res; 962 963 int new_lb = lb + max(1, low_y), new_ub = min(ub, lb + high_y); 964 lb = new_lb; 965 ub = new_ub; 966 } 967 } 968 969 return; 970 } 971 972 973 // Here, (2a - 1) + (2b - 1) + (2a - 1) = n 974 int a = 3 * (n + 3) / 16; 975 int y = min(ry, ly + 1); 976 977 int x1 = lx + a - 1; 978 x1 = max(x1, lx); 979 x1 = min(x1, rx); 980 981 int x2 = (lx + rx) / 2; 982 x2 = max(x2, x1 + 1); 983 x2 = min(x2, rx); 984 985 int x3 = rx - a + 1; 986 x3 = max(x3, x2 + 1); 987 x3 = min(x3, rx); 988 989 int m = min(3, ry - ly + 1); 990 vector<vector<bool>> good(n, vector<bool> (m, true)); 991 992 int new_lx = lx, new_rx = rx; 993 int new_ly = ly, new_ry = ry; 994 995 for (int x: {x1, x2, x3}) { 996 int res = query(x, y); 997 998 new_lx = max(new_lx, x - res); 999 new_rx = min(new_rx, x + res); 1000 1001 new_ly = max(new_ly, y - res); 1002 new_ry = min(new_ry, y + res); 1003 1004 for (int i = 0; i < n; i++) { 1005 for (int j = 0; j < m; j++) { 1006 int r_x = lx + i, r_y = ly + j; 1007 1008 int dx = abs(r_x - x); 1009 int dy = abs(r_y - y); 1010 1011 int d = dx + dy; 1012 int S = (dx + 1) * (dy + 1); 1013 1014 // d <= res <= d + S must hold 1015 if (res < d || d + S < res) { 1016 good[i][j] = false; 1017 } 1018 } 1019 } 1020 } 1021 1022 bool has_good = false; 1023 for (auto vx: good) { 1024 for (auto vy: vx) { 1025 if (vy) { 1026 has_good = true; 1027 } 1028 } 1029 } 1030 good.clear(); 1031 good.shrink_to_fit(); 1032 1033 if (has_good) { 1034 f(new_lx, new_rx, new_ly, new_ry); 1035 } else { 1036 f(lx, rx, ly + m, ry); 1037 } 1038 } 1039 1040 void solve() { 1041 int n, m; 1042 cin >> n >> m; 1043 ans_x = 0; ans_y = 0; cnt_q = 0; 1044 1045 f(1, m, 1, n); 1046 1047 cout << "! " << ans_y << ' ' << ans_x << endl; 1048 cout.flush(); 1049 1050 cerr << n << ' ' << cnt_q << " | " << n + 225 << endl; 1051 } 1052 1053 int main() { 1054 ios::sync_with_stdio(0); cin.tie(0); 1055 1056 int T; 1057 cin >> T; 1058 while (T--) { 1059 solve(); 1060 } 1061 } 1062 ``` 1063 1064 **Feedback** 1065 1066 * Good problem 1067 * Average problem 1068 * Bad problem