codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![ ](/predownloaded/15/2f/152fdc20fbe23ebf70ac67a70cd282414903adee.png)
    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