2211.md (48737B)
1 Source: https://codeforces.com/blog/entry/152448 2 3 **Rating Predictions** 4 5 | Predictor | A | B | C | D | E | F | G | H | 6 | --- | --- | --- | --- | --- | --- | --- | --- | --- | 7 | [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") | 800 | 1300 | (1400-2000) | 1700 | 2100 | 2400 | 2600 | 3500 | 8 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 1400 | (1400-1900) | 1800 | 2200 | 2600 | 3000 | 3500 | 9 | [dinohaur](/profile/dinohaur "Grandmaster dinohaur") | 800 | 1200 | (1400-1700) | 2100 | 2300 | 2600 | 2900 | 3300 | 10 | [_istil](/profile/_istil "Grandmaster _istil") | 800 | 1200 | (1300-1800) | 1900 | 2300 | 2500 | 2800 | 3300 | 11 | [Dragos](/profile/Dragos "Grandmaster Dragos") | 800 | 1400 | (1400-1900) | 1800 | 2100 | 2400 | 2800 | 3500 | 12 | [Argentum47](/profile/Argentum47 "Expert Argentum47") | 800 | 1300 | (1400-2000) | 1900 | 2200 | 2500 | ? | ? | 13 | [simplelife](/profile/simplelife "Expert simplelife") | 800 | 1200 | (1200-1800) | 1600 | 2000 | 2500 | 6700 | 6700 | 14 | [AksLolCoding](/profile/AksLolCoding "Master AksLolCoding") | 800 | 1000 | (1100-1800) | 1600 | 1900 | 2400 | ? | ? | 15 | [nik_exists](/profile/nik_exists "Specialist nik_exists") | 800 | 1100 | (1100-?) | 1800 | 2000 | ? | ? | ? | 16 17 #### [2211A - Antimedian Deletion](/contest/2211/problem/A) 18 19 Problem Credits: [nifeshe](/profile/nifeshe "Grandmaster nifeshe"), [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") 20 21 **Hint 1** 22 23 You are allowed to delete two elements in any valid subarray, but you only need to keep one. 24 25 **Solution** 26 27 A lower bound for the answer for each element is $2$ (or $1$ if $n=1$), as if the array size is $2$ or less, then no operations are even possible. 28 29 This bound is achievable for any element in any permutation. We can choose our subarray of size $3$ arbitrarily. Suppose $x$ is the value we want to keep in the array. If $x$ is the minimum element, we can delete the largest element. Otherwise, we can delete the smallest element. 30 31 **Code** 32 33 ``` 34 def solve(): 35 n = int(input()) 36 a = list(map(int, input().split())) 37 if n==1: 38 print("1\n") 39 else: 40 for i in range(n): 41 print("2 ") 42 print("\n") 43 44 t = int(input()) 45 for i in range(t): 46 solve() 47 ``` 48 49 **Rate The Problem!** 50 51 * Good Problem 52 * Okay Problem 53 * Bad Problem 54 * Didn't Solve 55 56 #### [2211B - Mickey Mouse Constructive](/contest/2211/problem/B) 57 58 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") 59 60 **Hint 1** 61 62 Since the array consists only of $1$ and $-1$, the growth rate of the cumulative sum must be $1$ or $-1$. In other words, you can't skip a number. What can you say about a lower bound of the answer from this? 63 64 **Solution** 65 66 For an array $a$, denote $p_i=a_1+a_2+\ldots+a_i$. Define $p_0=0$. We can see that the sum of the subarray from $l$ to $r$ is $p_r-p_{l-1}$. 67 68 Let's lower bound our answer. First, suppose that $x \ne y$. Without loss of generality that $x \ge y$ (so $p_{x+y} \gt 0$). Fix $d$ to be a divisor of $|x-y|$. Since our array contains only $1$ and $-1$ (and thus $p_i$ changes by only $1$ or $-1$ every time), and that $p_0=0$ while $p_{x+y}=x-y$, there must exist an index $i$ where $p_i=d$ (this is the discrete version of the Intermediate Value Theorem). Let this index be $i_1$. By the same logic, there must be an index $i_2$ between $i_1$ and $x+y$ such that $p_{i_2}=2\cdot d$. Continuing this process, we can see that for every divisor $d$ of $x-y$, there must exist at least one valid partition with all subarrays having equal sum. Therefore, a lower bound for the answer is the number of divisors of $x-y$. The case of $x \le y$ is analogous. 69 70 Then, can we reach this lower bound? It turns out the construction $[1, 1, \ldots, 1, -1, -1, \ldots, -1]$ reaches this lower bound. For a fixed divisor $d$, there is only one valid index $i$ each time, except for $x-y$, of which there are two indices. However, since the last subarray in the partition must reach $n$, this doesn't matter to us. 71 72 This solves the case for $x \ne y$. But what about $x=y$? Our above analysis of Intermediate Value Theorem breaks, as the start and final value are both $0$. The answer is at least $1$, since the full array is valid. We can reach this lower bound using the same construction above (as there does not exist any indices other than $0$ and $x+y$ with $p_i=0$). 73 74 **Code** 75 76 ``` 77 import sys 78 input = sys.stdin.readline 79 80 t = int(input()) 81 for _ in range(t): 82 x, y = map(int, input().split()) 83 s = x - y 84 85 a = [] 86 for _ in range(x): 87 a.append(1) 88 for _ in range(y): 89 a.append(-1) 90 91 ans = 0 92 for i in range(1, abs(s) + 1): 93 if s % i == 0: 94 ans += 1 95 96 if s == 0: 97 ans = 1 98 99 print(ans) 100 print(*a) 101 ``` 102 103 **Rate The Problem!** 104 105 * Good Problem 106 * Okay Problem 107 * Bad Problem 108 * Didn't Solve 109 110 #### [2211C1 - Equal Multisets (Easy Version)](/contest/2211/problem/C1) 111 112 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") 113 114 Special thanks to [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") for suggesting this subtask. 115 116 **Hint 1** 117 118 Consider the cases of $k=n$ and $k=n-1$. What do you notice? 119 120 **Solution** 121 122 Our first observation is that $b$ has to be a permutation (after replacing all $-1$'s). This is because since $a$ is a permutation, and each element appears in at least one valid subarray, if $b$ is not a permutation then at least one element does not exist in $b$, meaning that the answer must be no. 123 124 It may help to visualize this problem using some examples first: 125 126 * If $k=n$, then the answer is only YES if there are no repeat elements in $b$. 127 * What if $k=n-1$? Now, the requirements are more strict. If you have $b_1 \ne a_1$, $a_1$ would need to appear somewhere later. But then this means that in the subarray $[2,n-1]$, $a_1$ appears in the subarray in $b$ but not in $a$. Similarly, $a_n$ must be the same as $b_n$. We can see that the remaining $n-2$ elements are allowed to be any rearrangement of the middle $n-2$ elements in $a$. 128 129 Continuing on to $k=n-2$, using the same logic, we see that the first and last $2$ elements of $a$ must match with the first and last $2$ elements of $b$, with the middle $n-4$ numbers being allowed to be anything. 130 131 We now see that this forms a pattern: the first $n-k$ elements and the last $n-k$ elements in $a$ and $b$ must match, and the middle $2k-n$ elements must be rearrangements of each other. If $2k \lt n$, then we must have $a=b$ naturally. Let's now show that it works. 132 133 Consider the union of all size $k$ intervals: starting from $[1,k]$, then $[2,k+1]$, and so on. The interval that is inside all of these intervals is the union of $[1,k]$ and $[n-k+1,n]$ (intuitively, we can see this is true because $[1,k]$ is the leftmost interval, and $[n-k+1,n]$ is the rightmost one. Therefore, any point inside both of these intervals must be shared among all length $k$ intervals). The length of the intersection is $\max(2k-n,0)$. Any point not in this common interval must be the same in $a$ and $b$, as there exists an interval that doesn't contain it. 134 135 **Rate The Problem!** 136 137 * Good Problem 138 * Okay Problem 139 * Bad Problem 140 * Didn't Solve 141 142 #### [2211C2 - Equal Multisets (Hard Version)](/contest/2211/problem/C2) 143 144 Problem credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") 145 146 **Hint 1** 147 148 Consider the transition from the interval $[l,r]$ to $[l+1,r+1]$. What do you "gain"? What do you "lose"? 149 150 **Solution** 151 152 We need to take a different approach from problem C1. Consider transferring from the interval $[l,r]$ to $[l+1,r+1]$. In the multiset of $b$, we need to "lose" the element $a_l$ and "gain" the element $a_r$. At first glance, this seems very restrictive: is there even any cases where $a_l \ne b_l, a_r \ne b_r$ and this can still work out? 153 154 In fact, the only other case that doesn't break the condition is if $a_l=a_r$ and $b_l=b_r$. Otherwise, you would need $b_r$ to "recover" the lost element from $a_r$ and also whatever element was lost at $b_l$ at the same time, which is impossible (if $a_l=a_r$, then $a_r$ "recovered" the element $a_l$ in the multiset). 155 156 This motivates us to split the arrays $a$ and $b$ into $k$ subsequences, depending on their indices modulo $k$. In each subsequence, if all elements of $a$ are the same, then all elements of $b$ must be the same. Otherwise, we must have $a_i=b_i$ for each index in the subsequence. 157 158 There is one more requirement: we need to ensure that the first $k$ elements of $a$ and $b$ can match. Our transition conditions ensure that if $[l,r]$ works, then $[l+1,r+1]$ also does. But we would need the "base" interval $[1,k]$ to work first (this process is much like the process of induction). Once we fill in values of $b$ that is required in our previous step, all we need to do is ensure that no number in the first $k$ indices appears more often in $b$ than $a$. 159 160 **Code** 161 162 ``` 163 #include <bits/stdc++.h> 164 using namespace std; 165 #define int long long 166 167 void solve() { 168 int n, k; cin >> n >> k; 169 vector<int> a(n), b(n); 170 for (auto &x : a) cin >> x; 171 for (auto &x : b) cin >> x; 172 173 vector<bool> vis(n); 174 vector<int> pos(k); 175 map<int, int> cnt; 176 for (int i = 0; i < k; i++) { 177 pos[i] = a[i]; 178 for (int j = i + k; j < n; j += k) { 179 if (pos[i] != a[j]) pos[i] = -1; 180 } 181 if (pos[i] != -1) cnt[pos[i]]++; 182 183 if (pos[i] == -1) { 184 for (int j = i; j < n; j += k) { 185 if (b[j] != -1 && b[j] != a[j]) { 186 cout << "NO" << "\n"; 187 return; 188 } 189 } 190 } 191 } 192 193 map<int, int> cnt2; 194 vector<int> ans(k); 195 for (int i = 0; i < k; i++) { 196 if (pos[i] != -1) { 197 set<int> d; 198 for (int j = i; j < n; j += k) 199 d.insert(b[j]); 200 d.erase(-1); 201 202 if (d.size() >= 2) { 203 for (int j = i; j < n; j += k) 204 if (b[j] != -1 && b[j] != a[j]) { 205 cout << "NO" << "\n"; 206 return; 207 } 208 } 209 if (d.size() == 1) 210 cnt2[*d.begin()]++; 211 } 212 } 213 214 for (auto [k, x] : cnt2) { 215 if (x > cnt[k]) { 216 cout << "NO" << "\n"; 217 return; 218 } 219 } 220 221 cout << "YES" << "\n"; 222 223 } 224 225 signed main() { 226 int T; 227 cin >> T; 228 while (T--) 229 solve(); 230 } 231 ``` 232 233 **Rate The Problem!** 234 235 * Good Problem 236 * Okay Problem 237 * Bad Problem 238 * Didn't Solve 239 240 #### [2211D - AND-array](/contest/2211/problem/D) 241 242 Problem credits: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 243 244 **Hint 1** 245 246 How is the checker implemented? In other words, given $a$ find $f(a)$. 247 248 **Hint 2** 249 250 Let $\text{cnt}_l$ be the number of $i$ such that $a_i$ has the bit $l$ set. $f(a)$ only depends on the array $\text{cnt}$. 251 252 **Hint 3** 253 254 $f(a)_k = \sum\limits_{l = 0}^{28} 2^l \cdot \binom{\text{cnt}_l}{k}$. 255 256 **Hint 4** 257 258 Look at $b_n$. This value tells us all the bits $l$ that have $\text{cnt}_l = n$. 259 260 **Hint 5** 261 262 We can remove all the bits in $b_n$: for all set bits in $b_n$ and $1 \le k \lt n$ set $b_k = b_k - \binom{n}{k} \cdot 2^l$. After that no bit occurs $n$ times in $a$, so set $n = n - 1$. 263 264 **Hint 6** 265 266 Since $a$ is guaranteed to exist, each bit will be removed at most once, so the time complexity is $O(n \log A)$. 267 268 **Solution** 269 270 Given $a$, how can we find $f(a)$? Consider each bit separately: assume $a_i$ is either $0$ or $1$. If there are $m$ ones in $a$, then $f(a)_k = \binom{m}{k}$ — the number of ways to pick $k$ ones from $m$, since every index in the subsequence has to be a $1$. 271 272 This can be generalized to all $a$: let $\text{cnt}_l$ be the number of $i$ such that $a_i$ has the bit $l$ set. $f(a)$ only depends on the array $\text{cnt}$, and $f(a)_k = \sum\limits_{l = 0}^{28} 2^l \cdot \binom{\text{cnt}_l}{k}$. 273 274 Now we need to restore $a$ from $f(a)$. Look at $b_n$. This value tells us all the bits $l$ that have $\text{cnt}_l = n$. 275 276 We can remove all the bits in $b_n$: for all set bits in $b_n$ and $1 \le k \lt n$ set $b_k = b_k - \binom{n}{k} \cdot 2^l$. 277 278 After that no bit occurs $n$ times, and since $f(a)$ only depends on the array $\text{cnt}$, we can assume that $n = n - 1$ and repeat the same procedure. This way we can uniquely determine the array $\text{cnt}$. 279 280 The only thing left is the actually find any feasible $a$. We can do that the following way: for all bits $l$ and $i$ in $[1, \text{cnt}_l]$ set the $l$-th bit in $a_i$. This $a$ corresponds to the found array $\text{cnt}$. 281 282 The only concern is the time complexity. However, since the answer is guaranteed to exist we will delete each bit at most once, so the final solution is $O(n \log A)$. 283 284 **Code** 285 286 ``` 287 #include <bits/stdc++.h> 288 289 using namespace std; 290 291 const int mod = 1e9 + 7; 292 const int MAX = 2e5 + 5; 293 const int LG = 29; 294 295 int binpow(int x, int n) { 296 int ans = 1; 297 while(n) { 298 if(n & 1) ans = (long long) ans * x % mod; 299 n >>= 1; 300 x = (long long) x * x % mod; 301 } 302 return ans; 303 } 304 305 int fact[MAX], inv[MAX]; 306 307 int C(int n, int k) { 308 if(n < k || k < 0) return 0; 309 return (long long) fact[n] * inv[k] % mod * inv[n - k] % mod; 310 } 311 312 void solve() { 313 int n; 314 cin >> n; 315 vector<int> b(n); 316 for(auto &i : b) { 317 cin >> i; 318 } 319 320 vector<int> cnt(LG); 321 for(int i = n - 1; ~i; i--) { 322 for(int l = 0; l < LG; l++) { 323 if(b[i] >> l & 1) { 324 cnt[l] = i + 1; 325 326 for(int j = 0; j <= i; j++) { 327 int subtract = (long long) C(i + 1, j + 1) * (1 << l) % mod; 328 b[j] -= subtract; 329 if(b[j] < 0) b[j] += mod; 330 } 331 } 332 } 333 } 334 335 vector<int> a(n); 336 for(int l = 0; l < LG; l++) { 337 for(int i = 0; i < cnt[l]; i++) { 338 a[i] |= 1 << l; 339 } 340 } 341 for(auto i : a) cout << i << " "; cout << '\n'; 342 } 343 344 signed main() { 345 fact[0] = 1; for(int i = 1; i < MAX; i++) fact[i] = (long long) fact[i - 1] * i % mod; 346 inv[MAX - 1] = binpow(fact[MAX - 1], mod - 2); 347 for(int i = MAX - 1; i; i--) inv[i - 1] = (long long) inv[i] * i % mod; assert(inv[0] == 1); 348 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 349 int tests = 1; 350 cin >> tests; 351 for(int test = 0; test < tests; test++) { 352 solve(); 353 } 354 } 355 ``` 356 357 **Rate The Problem!** 358 359 * Good Problem 360 * Okay Problem 361 * Bad Problem 362 * Didn't Solve 363 364 #### [2211E - Minimum Path Cover](/contest/2211/problem/E) 365 366 Problem credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") 367 368 **Hint 1** 369 370 The reason why most naive DP approaches fail is because you cannot factorize $2\cdot 10^5$ numbers of scale $10^{18}$ fast. How do you avoid this? 371 372 **Hint 2** 373 374 The solution to the problem does not change if "each node is covered by exactly one path" was replaced by "each node is covered by at least one path" 375 376 **Solution** 377 378 Read the hints. 379 380 The most naive approach is something like $dp(node,x)$ to the minimum number of paths used to cover the subtree of $node$, such that the path from $node$ has GCD $x$. With potentially up to $d(a_{node})$ different states of DP at each node (where $d(x)$ is the number of divisors of $x$), this will easily get the Time Limit Exceeded verdict. 381 382 However, we take advantage of the fact that in a tree, each node can have only one parent. In other words, there can only be one path going upwards starting at each node. For simplicity, assume that each path must end as a prime number (if the path instead ends with something like $6$, it is counted as both ending in $2$ and $3$). We can then perform a DP like $dp(node,x)$ being the smallest number of paths to cover the subtree of $node$, assuming that the path going up from $node$ is $x$ (where $x$ must be prime). 383 384 Unfortunately, finding the prime factors of the numbers is still impossible. However, what if we don't need to? Consider a greedy strategy where you extend every path from the children of node $x$ upwards if the GCD does not become $1$. (because of our analysis above, the solution to the problem does not change if "each node is covered by exactly one path" is replaced by "each node is covered by at least one path"). While we cannot store all possible values of a path, we *can* store the LCM of all such paths. It's not hard to show that storing the LCM is functionally the same as storing all possible values of a path. 385 386 So the solution is as follows: let $dp(x)$ represent the minimum number of paths to cover the subtree of $x$, and let $val(x)$ be the LCM of all paths that can pass through $x$. When trying to find the answers for $x$, we first set $val(x)=1$. For each child $c$ of $x$, set $val(x)=\text{LCM}(val(x), val(c))$. Set $dp(x)$ to be the sum of $dp(c)$, and add $1$ if $val(x)=1$ (as well as updating $val(x)=a_x$). This solution is very simple and runs in $O(n \log A)$ 387 388 Since the values of $a_i$ are large, we must calculate LCM as $a/\text{GCD}(a,b)\cdot b$ instead of $(a\cdot b)/\text{GCD}(a,b)$. However, note that the calculations will never overflow $64$-bit integers, as they are upper bounded by $a_i$. 389 390 As an alternative to maintaining the LCM, you can actually maintain the set of possible GCD values, but ensure that they are pairwise coprime. This solution is expected to run in $O(n \log ^2{A})$ 391 392 **Rate The Problem!** 393 394 * Good Problem 395 * Okay Problem 396 * Bad Problem 397 * Didn't Solve 398 399 **Code** 400 401 ``` 402 #include <bits/stdc++.h> 403 using namespace std; 404 #define rep(i,a,n) for (int i=(a);i<(n);i++) 405 #define per(i,a,n) for (int i=(n)-1;i>=(a);i--) 406 #define pb push_back 407 #define eb emplace_back 408 #define mp make_pair 409 #define all(x) (x).begin(),(x).end() 410 #define fi first 411 #define se second 412 #define SZ(x) ((int)(x).size()) 413 typedef vector<int> VI; 414 typedef basic_string<int> BI; 415 typedef long long ll; 416 typedef pair<int,int> PII; 417 typedef double db; 418 mt19937 mrand(random_device{}()); 419 const ll mod=676767677; 420 int rnd(int x) { return mrand() % x;} 421 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 422 // head 423 424 const int N=201000; 425 int n,dp[N]; 426 ll d[N],v[N]; 427 ll a[N]; 428 void solve() { 429 scanf("%d",&n); 430 per(i,1,n+1) { 431 int k; 432 scanf("%lld",&a[i]); 433 scanf("%d",&k); 434 VI s; 435 dp[i]=0; 436 bool val=0; 437 rep(j,0,k) { 438 int x; 439 scanf("%d",&x); 440 s.pb(x); 441 dp[i]+=dp[x]; 442 d[x]=gcd(v[x],a[i]); 443 val|=d[x]>1; 444 } 445 if (val) { 446 ll z=1; 447 for (auto x:s) if (d[x]>1) z=lcm(z,d[x]); 448 v[i]=z; 449 } else { 450 dp[i]+=1; 451 v[i]=a[i]; 452 } 453 printf("%d\n",dp[i]); 454 fflush(stdout); 455 } 456 } 457 458 int _; 459 int main() { 460 for (scanf("%d",&_);_;_--) { 461 solve(); 462 } 463 } 464 ``` 465 466 #### [2211F - Learning Binary Search](/contest/2211/problem/F) 467 468 Problem credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") 469 470 Unfortunately, it seems like there are a lot of cheaters on this problem. We will do the best to clear them out, but keep in mind this is out of our control. 471 472 **Hint 1** 473 474 Consider what the contribution of a number is. 475 476 **Hint 2** 477 478 Come up with $O(nm)$ or $O(n^2)$ solution first. There is an identity that can simplify. 479 480 **Solution 1** 481 482 Simulate the binary search so we get the weight of each index. Now, we want to partition it into $m$ segments (potentially empty) where the weight of each segment is the minimum number that it covers. 483 484 Suppose we fix the number $x$, as well as the interval that it covers $[l,r]$. This means that we need to cover the interval $[1,l-1]$ with the numbers $1$ through $x-1$, and the interval $[r+1,n]$ with the numbers $x+1$ through $m$. Denote $y=m-x$. Then, using stars and bars, we get the number of ways to fill other numbers as: 485 486 $\binom{l+x-3}{x-2}\binom{y+n-r-1}{y-1}$ 487 488 This sum is to be taken over all $x$ from $2$ to $m-1$ (ignore the edge cases of $x=1$ and $x=m$ for now). Using Vandermonde's identity, this simplifies to 489 490 $\binom{y+n+x-(r-l)-3}{x+y-3}$ 491 492 As a further optimization, note that everything above is a constant except for $r-l$, which is dependent on the size of the interval. Therefore, we are motivated to loop over the size of $r-l$. Note that the above should also be multiplied by the minimum weight on the interval from $l$ to $r$. Therefore, our problem is now trying to find the sum of minimum of all length $k$ subarrays for all $k$ from $1$ to $n$. 493 494 To solve this subproblem, we can use a monotonic stack to calculate the bounds in which $i$ is the minimum (to break ties, we use strict inequality on one side but not the other). Then, noting that the contribution of an index for $k$ increases by $1$ until some point, then decreases by $1$. This can be optimized by creating the $2$-nd order difference array. The problem is solved in $O(n)$ time. 495 496 Thanks to [Dragos](/profile/Dragos "Grandmaster Dragos") for writing up the following solution. 497 498 **Solution 2** 499 500 First, let’s count nondecreasing arrays. 501 502 How many nondecreasing arrays of length $n$ have last element exactly $m$? 503 504 This is a classical problem. Instead of looking at the array itself, look at its difference variables: $d_1 = a_1 - 1$ and $d_i = a_i - a_{i-1}$ for $i \ge 2$. Since the array is nondecreasing, every $d_i$ is non-negative, and $d_1 + d_2 + \cdots + d_n = a_n - 1 = m - 1.$ So this becomes the standard stars-and-bars count. 505 506 What about arrays where the last element is $\le m$? 507 508 This is equivalent to having $n$ non-negative variables with sum $\le m-1$. The standard trick is to introduce one extra variable that absorbs the remaining value, so this becomes counting $n+1$ non-negative variables with sum exactly $m-1$. 509 510 Now let’s solve the original problem. We simulate the binary search and go through all intervals $[l,r]$ that can appear in the recursion tree. For each such interval, let $mid = \lfloor (l+r)/2 \rfloor$. We count how many arrays make the search terminate at this state, and multiply that count by the current depth of the search. 511 512 Suppose we are at interval $[l,r]$. To terminate here, we need $a_{mid}$ to be the searched value. Also, if $l \gt 1$ then the search must previously have inspected position $l-1$ and concluded that its value is smaller than the target, so we need $a_{l-1} \lt a_{mid}$. Similarly, if $r \lt n$ then we need $a_{mid} \lt a_{r+1}$. Since we are already counting only nondecreasing arrays, these are the only extra constraints that matter. 513 514 So we are left with the following question: how many good arrays satisfy $a_{l-1} \lt a_{mid} \lt a_{r+1}$? 515 516 Let $S = \binom{n+m-1}{n}$ be the number of all good arrays. We now remove the bad arrays by inclusion-exclusion. 517 518 The bad arrays are those with $a_{l-1} = a_{mid}$ or $a_{mid} = a_{r+1}$. The condition $a_{l-1} = a_{mid}$ means that every difference variable corresponding to positions $l, l+1, \dots, mid$ must be $0$. So we can count such arrays by simply removing those variables from the stars-and-bars count. Similarly, the condition $a_{mid} = a_{r+1}$ means that every difference variable corresponding to positions $mid+1, mid+2, \dots, r+1$ must be $0$, and we count those in the same way. 519 520 Finally, we add back the arrays counted twice, namely those with $a_{l-1} = a_{mid} = a_{r+1}$, which is equivalent to forcing all difference variables for positions $l, l+1, \dots, r+1$ to be $0$. 521 522 One last thing to note is that if $l=1$ (or $r=n$), then the corresponding boundary restriction does not exist, so we do not subtract that case. 523 524 Since there are $O(n)$ intervals, and each interval can be computed in $O(1)$, the final complexity is $O(n)$. 525 526 **Code (Solution 1)** 527 528 ``` 529 #include <bits/stdc++.h> 530 531 using namespace std; 532 533 // using namespace std; 534 using ll = long long; 535 #define vt vector 536 #define int long long 537 #define add push_back 538 #define FOR(i,a,b) for (int i = (a); i < (b); ++i) 539 #define F0R(i,a) FOR(i,0,a) 540 #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) 541 #define R0F(i,a) ROF(i,0,a) 542 const ll mod = 676767677; 543 const ll inf = 1e18; 544 template<typename T> using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>; //defines min_pq 545 546 mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); 547 int rand_num(int l, int r) { 548 return rnd()%(r-l+1)+l; 549 } 550 int bexpo(int b, int e) { 551 int ans = 1; 552 while(e) { 553 if(e&1) ans=ans*b%mod; 554 e>>=1; 555 b=b*b%mod; 556 } 557 return ans; 558 } 559 signed main() { 560 ios_base::sync_with_stdio(false); 561 cin.tie(0); 562 // freopen("input.txt" , "r" , stdin); 563 // freopen("output.txt" , "w", stdout); 564 int t; 565 cin >> t; 566 vt<int> fact(2e6+5), ifact(2e6+5); 567 fact[0]=ifact[0]=1; 568 FOR(i, 1, 2e6+5) { 569 fact[i]=fact[i-1]*i%mod; 570 ifact[i]=bexpo(fact[i], mod-2); 571 } 572 auto nck = [&](int n, int k)->int{ 573 if(k<0 || k>n) { 574 return 0; 575 } 576 return fact[n]*ifact[k]%mod*ifact[n-k]%mod; 577 }; 578 while(t--) { 579 int n,m; 580 cin >> n >> m; 581 vt<int> time(n); 582 auto fill = [&](auto self, int l, int r, int start)->void{ 583 if(l>r) return; 584 int mid = (l+r)/2; 585 time[mid]=start; 586 self(self, l, mid-1, start+1); 587 self(self, mid+1, r, start+1); 588 }; 589 fill(fill, 0, n-1, 1); 590 vt<int> l(n,-1),r(n, n); 591 stack<int> s; 592 F0R(i, n) { 593 while(s.size() && time[s.top()]>time[i]) { 594 r[s.top()]=i; 595 s.pop(); 596 } 597 s.push(i); 598 } 599 while(s.size()) s.pop(); 600 R0F(i, n) { 601 while(s.size() && time[s.top()]>=time[i]) { 602 l[s.top()]=i; 603 s.pop(); 604 } 605 s.push(i); 606 } 607 // cout << time << " " << l << " " << r << endl; 608 vt<int> v(n+10); 609 F0R(i, n) { 610 // cout << i << endl; 611 int left = i-l[i]-1; 612 int right = r[i]-i-1; 613 if(left>right) swap(left,right); 614 v[1]+=time[i]; 615 v[left+2]-=time[i]; 616 v[right+2]-=time[i]; 617 v[left+right+3]+=time[i]; 618 } 619 FOR(i, 1, n+1) v[i]+=v[i-1]; 620 FOR(i, 1, n+1) v[i]+=v[i-1]; 621 // cout << v << endl; 622 int ans = 0; 623 FOR(sz, 1, n+1) { 624 int out = n-sz; 625 ans+=v[sz]*nck(out+m-2, m-3)%mod; 626 } 627 int mn = inf; 628 F0R(i, n) { 629 mn=min(mn, time[i]); 630 ans+=nck(n-i-1+m-2, m-2)*mn; 631 ans%=mod; 632 } 633 mn = inf; 634 R0F(i, n) { 635 mn=min(mn, time[i]); 636 ans+=nck(i+m-2, m-2)*mn; 637 ans%=mod; 638 } 639 cout << ans << endl; 640 } 641 return 0; 642 ``` 643 644 } 645 646 **Code (Solution 2)** 647 648 ``` 649 #include <bits/stdc++.h> 650 using namespace std; 651 typedef long long ll; 652 typedef vector<int> vi; 653 typedef pair<int, int> pii; 654 typedef pair<double, double> pdd; 655 #define pb push_back 656 #define mp make_pair 657 #define fs first 658 #define sc second 659 #define rep(i, from, to) for (int i = from; i < (to); ++i) 660 #define all(x) x.begin(), x.end() 661 #define sz(x) (int)(x).size() 662 #define FOR(i, to) for (int i = 0; i < (to); ++i) 663 typedef vector<vector<int>> vvi; 664 typedef vector<vector<pii>> vvpi; 665 typedef vector<ll> vll; 666 typedef vector<vll> vvll; 667 typedef vector<pair<int, int>> vpi; 668 typedef pair<ll, ll> pll; 669 #define MOD 676767677 670 671 template<int MODX> 672 struct ModInt { 673 unsigned x; 674 ModInt() : x(0) { } 675 ModInt(signed sig) : x(((sig%MODX)+MODX)%MODX) { } 676 ModInt(signed long long sig) : x(((sig%MODX)+MODX)%MODX) { } 677 int get() const { return (int)x; } 678 ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; } 679 680 ModInt &operator+=(ModInt that) { if ((x += that.x) >= MODX) x -= MODX; return *this; } 681 ModInt &operator-=(ModInt that) { if ((x += MODX - that.x) >= MODX) x -= MODX; return *this; } 682 ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MODX; if (x < 0) x += MODX; return *this; } 683 ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MODX - 2); } 684 685 ModInt operator+(ModInt that) const { return ModInt(*this) += that; } 686 ModInt operator-(ModInt that) const { return ModInt(*this) -= that; } 687 ModInt operator*(ModInt that) const { return ModInt(*this) *= that; } 688 ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } 689 bool operator<(ModInt that) const { return x < that.x; } 690 friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; } 691 }; 692 typedef ModInt<MOD> mint; 693 694 // N ~ 10^6 695 class Combinations { 696 public: 697 vector<mint> inv, fact, ifact; 698 699 Combinations(int N) { 700 inv.resize(N+10), fact.resize(N+10), ifact.resize(N+10); 701 inv[1] = fact[0] = fact[1] = ifact[0] = ifact[1] = 1; 702 for(int i=2;i<=N;++i) { 703 inv[i] = inv[MOD%i] * (MOD - MOD/i); 704 fact[i] = fact[i-1]*i; 705 ifact[i] = ifact[i-1]*inv[i]; 706 } 707 } 708 // a > b 709 mint comb(ll a, ll b) { 710 if(a < b) return mint(0); 711 return fact[a] * ifact[b] * ifact[a-b]; 712 } 713 }; 714 715 Combinations comb(2010100); 716 717 // Stars and bars 718 mint SB(int K, int S) { 719 return comb.comb(S+K-1, K-1); 720 } 721 722 int n,m; 723 mint ret = 0; 724 void dfs(int l, int r, int depth) { 725 if (l > r) return; 726 // Last two checked positions. 727 int lp = l - 1; 728 int rp = r + 1; 729 730 int mid = (l + r)/2; 731 mint TOT = SB(n+1, m); 732 ret += TOT * depth; 733 // If we saw a position for which ARR[l-1] < ARR[mid] 734 if (lp != -1) { 735 ret -= SB(n+1 - (mid - lp), m) * depth; 736 } 737 738 // If we saw a position for which a[mid] < a[r+1] 739 if (rp != n) { 740 ret -= SB(n+1 - (rp - mid), m) * depth; 741 } 742 743 // If we saw both a[l-1] < a[mid] < a[r+1] add the double counted arrays back 744 if (lp != -1 && rp != n) { 745 ret += SB(n + 1 - (rp - lp), m) * depth; 746 } 747 dfs(mid+1, r, depth+1); 748 dfs(l, mid-1, depth+1); 749 } 750 751 int main() { 752 cin.sync_with_stdio(0); 753 cin.tie(0); 754 int T; 755 cin >> T; 756 while(T--) { 757 cin >> n >> m; 758 --m; 759 ret = 0; 760 dfs(0, n-1, 1); 761 cout << ret << "\n"; 762 } 763 return 0; 764 } 765 ``` 766 767 **Bonus** 768 769 Solve this problem for $n,m \lt =10^6$ but there is no limit on sum of $n$ or $m$ across all test cases. 770 771 **Rate The Problem!** 772 773 * Good Problem 774 * Okay Problem 775 * Bad Problem 776 * Didn't Solve 777 778 #### [2211G - Rational Bubble Sort](/contest/2211/problem/G) 779 780 Problem credits: [chromate00](/profile/chromate00 "Expert chromate00"). Special thanks: [BurnedChicken](/profile/BurnedChicken "Legendary Grandmaster BurnedChicken") 781 782 **Hint 1** 783 784 Consider the graph of prefix sums. 785 786 **Solution** 787 788 Let's take the prefix sums $b_i=a_1+a_2+\ldots+a_i$ instead of $a_i$ (including $b_0=0$), and consider what it means when $a_i$ is sorted in non-decreasing order. We can see that $a_i$ being non-decreasing is equivalent to the points $(i,b_i)$ forming a chain that is convex from below. The operation on index $i$ makes the segment from $(i-1,b_{i-1})$ to $(i+1,b_{i+1})$ completely straight, and to sort $a$ we need to be able to make the chain convex using the operation. 789 790 Notice the following observation. 791 792 * Observation: any chain $(i-1,b_{i-1}),(i,b_i),\ldots,(j,b_j)$ can be made arbitrarily close to the line from $(i-1,b_{i-1})$ to $(j,b_j)$. 793 794 In other words, $a_i,a_{i+1},\ldots,a_j$ can be made arbitrarily close to their average value. 795 796 Because their mean is constant when we don't perform operations outside this range, we can easily reason about their variance. Let's say their mean is $\mu$. Then, $(a_i-\mu)^2+(a_{i+1}-\mu)^2 \ge 2 \cdot (\frac{a_i+a_{i+1}}{2}-\mu)^2$ due to the convexity of the function $f(x)=(x-\mu)^2$. Equality holds if and only if $a_i=a_{i+1}$. In other words, as long as there is at least one unequal adjacent pair (unless all $j-i+1$ values are equal, there definitely will be one), the variance can decrease indefinitely (that is, arbitrarily close to $0$). The variance becomes $0$ if and only if all $j-i+1$ values are equal. 797 798 Now, let's see if there is a point $(i,b_i)$ strictly below the line from $(0,0)$ to $(n,b_n)$. Then, we can make the segments almost straight from $(0,0)$ to $(i,b_i)$ and from $(i,b_i)$ to $(n,b_n)$. The fact that we can make a segment almost (yet not completely) straight is important. After we make them straight enough, let's call their slopes $\mu_{1,l}$ and $\mu_{1,r}$, and we can perform the operation on index $i$ so that the segment from $(i-1,b_{i-1})$ to $(i+1,b_{i+1})$ is straight. This slope $s_{1,1}$ certainly satisfies $\mu_l \lt s_{1,1} \lt \mu_r$. If this does not hold, then we could certainly go back, make the segments flatter, and it will definitely hold at some point when we perform the operation on index $i$. 799 800 We'll now set $l=i-1$, $r=i+1$, and maintain an invariant that the segment $[l,r]$ is convex. If we perform the operation on indices $i-1$ and $i+1$, we get two slopes $s_{2,1}$ and $s_{2,2}$ such that $\mu_{2,l} \lt s_{2,1} \lt s_{2,2} \lt \mu_{2,r}$, where $\mu_{2,l}$ is the slope from $(0,0)$ to $(l-1,b_{l-1})$ and $\mu_{2,r}$ is the slope from $(r+1,b_{r+1})$ to $(n,b_n)$. We have now expanded the segment to $[l-1,r+1]$ while maintaining convexity. 801 802 Repeating this process, we can expand $[l,r]$ to $[0,n]$, and the chain can become entirely convex. 803 804 Now the only case left is when all points are either on or above the line from $(0,0)$ to $(n,b_n)$. We can only make them non-decreasing by making them all equal. However, if two consecutive points are above the line, we can't put them right on the line because we're still moving a point to somewhere above the line. However, if only one point $(i,b_i)$ is above the line, we can make the segment from $(i-1,b_{i-1})$ to $(i+1,b_{i+1})$ completely straight. Therefore, if there are no two consecutive points above the line, we can perform the operation on all points above the line, and the chain will be completely straight. We have shown that the outlined two cases are the only cases in which we can make $a$ sorted in non-decreasing order. 805 806 The problem is solved in $\mathcal{O}(n)$ time. 807 808 **Code** 809 810 ``` 811 #include<bits/stdc++.h> 812 using namespace std; 813 using ll=long long; 814 using pii=pair<int,int>; 815 816 #define all(a) a.begin(),a.end() 817 #define pb push_back 818 #define sz(a) ((int)a.size()) 819 820 signed main(){ 821 ios_base::sync_with_stdio(0),cin.tie(0); 822 int t;cin>>t; 823 while(t--) 824 { 825 ll n; cin >> n; 826 vector<ll> a(n); 827 for(int i=0; i<n; ++i) cin >> a[i]; 828 vector<ll> sum(n+1); 829 for(int i=0; i<n; ++i) sum[i+1]=sum[i]+a[i]; 830 vector<ll> exact(n+1); 831 exact[0]=exact[n]=1; 832 bool found=0; 833 for(int i=1; i<n; ++i){ 834 if(1ll*sum[i]*(n-i)<1ll*(sum[n]-sum[i])*i){ 835 cout << "Yes\n"; 836 found=1;break; 837 } 838 if(1ll*sum[i]*(n-i)==1ll*(sum[n]-sum[i])*i){ 839 exact[i]=1; 840 } 841 } 842 if(found)continue; 843 for(int i=0; i+1<=n; ++i){ 844 if(!exact[i]&&!exact[i+1]){ 845 cout << "No\n"; 846 found=1;break; 847 } 848 } 849 if(found)continue; 850 cout << "Yes\n"; 851 } 852 } 853 ``` 854 855 **Rate The Problem!** 856 857 * Good Problem 858 * Okay Problem 859 * Bad Problem 860 * Didn't Solve 861 862 #### [2211H - Median Deletion](/contest/2211/problem/H) 863 864 Problem credits: [nifeshe](/profile/nifeshe "Grandmaster nifeshe") 865 866 **Hint 1** 867 868 We can reduce a fixed subarray $[l, r]$ of $p$ to two elements: the minimum and the maximum. 869 870 **Hint 2** 871 872 The answer is at most $5$. Try to determine whether we can get the answer of $4$. 873 874 **Hint 3** 875 876 Consider the minimum/maximum in $[1, i - 1]$ and minimum/maximum in $[i + 1, n]$. There is only one non-trivial case: $[1, 4, 3, 5, 2, 6]$ for $p_i = 3$. 877 878 **Hint 4** 879 880 Let $a, b$ be the positions of prefix minimum and prefix maximum in $[1, i - 1]$ accordingly, and $c, d$ be the positions suffix minimum and suffix maximum. WLOG assume that $a \lt b$. The case is $a \lt b \lt i \lt c \lt d$, WLOG assume we have to remove $p_b$ using an element from $[i + 1, c - 1]$. 881 882 **Hint 5** 883 884 Apart from the trivial cases the condition is this: let $l = \max(a, b)$ and $r = \min(c, d)$, then the answer is $\le 4$ iff there is an element $l \le j \le r$ such that $p_j \lt \min(p_l, p_r)$ or $p_j \gt \max(p_l, p_r)$. 885 886 **Hint 6** 887 888 To determine if it's $3$ consider two cases: $\text{pos}_1 \lt i \lt \text{pos}_n$ and $\text{pos}_1 \lt \text{pos}_n \lt i$. The first case is significantly easier. 889 890 **Hint 7** 891 892 If the answer is at most $4$ when $\text{pos}_1 \lt i \lt \text{pos}_n$, we can reduce $[\text{pos}_1, \text{pos}_n]$ to only $[1, p_i, n]$. 893 894 **Hint 8** 895 896 If there is an extremum before $\text{pos}_1$ or after $\text{pos}_n$, we can't do anything about it. Now consider the $\text{pos}_1 \lt \text{pos}_n \lt i$ case. 897 898 **Hint 9** 899 900 The two main cases are: $[1, n, p_i, H, L]$ and $[1, n, p_i, L, H]$, where $L = p_c$ and $H = p_d$. Consider $[1, n, p_i, L, H]$ first. 901 902 **Hint 10** 903 904 We can remove any element bigger than $p_i$ using $n$. Since the answer is at least $4$, we can remove $L$. After that we remove $H$ using $n$, so the answer is $3$. Now consider $[1, n, p_i, H, L]$ 905 906 **Hint 11** 907 908 We could easily remove $H$ using $n$, however after that we wouldn't be able to remove $L$. It is sometimes possible to remove both, consider $p = [1, 7, 2, 6, 4, 5, 3]$ for $p_i = 4$. 909 910 **Hint 12** 911 912 We do $[1, 7, 2, 6, 4, 5, 3] \rightarrow [1, 7, 2, 6, 4, 3] \rightarrow [1, 7, 2, 4, 3] \rightarrow [1, 7, 2, 4, 3] \rightarrow [1, 7, 2, 4] \rightarrow [1, 7, 4]$. So we need to find indices $j$ and $k$ such that: $\text{pos}_n \lt k \lt j \lt i$, $p_k \lt L \lt p_i \lt H \lt p_j$, and we can first clear $[j + 1, i - 1]$ and then clear $[k + 1, j]$. Greedy does not work as we have to be able to clear the intervals. For example, for $p = [1, 8, 3, 7, 2, 5, 6, 4]$ and $p_i = 5$ the answer is $4$, not $3$, as we cannot remove $2$ after choosing $p_k = 3$ and $p_j = 7$. 913 914 **Hint 13** 915 916 Choose $k$ to be the minimum in $[\text{pos}_n, i]$, $j$ to be the maximum in $[k + 1, i]$, then you can always clear the intervals. 917 918 **Solution** 919 920 First of all, we trivially can never delete $1$ or $n$, since they are always the smallest and the largest elements. Furthermore, for a fixed subarray $[l, r]$, where $p_x$ is the minimum and $p_y$ is the maximum in the subarray, we can trivially turn it $[p_l, p_{l + 1}, \ldots, p_r]$ into $[p_x, p_y]$ or $[p_y, p_x]$ (depending on their order) by continuously applying operation on the subarray. We call that sequence operations **a reduction** of $[l, r]$. 921 922 From this immediately follows that the answer for any $p_i$ is at most $5$: leave at most $2$ elements in $[1, i - 1]$, leave $p_i$, and at most $2$ elements in $[i + 1, n]$. Moreover, if $p_i$ is not $1$ or $n$, the answer is at least $3$, since we can't delete $1$ or $n$. Therefore, the problem is determining whether the answer is $3$, $4$ or $5$ (for $p_i = 1$ or $p_i = n$ it is trivially $2$). 923 924 Let's try to determine if we can get an answer $\le 4$ first. Let's get rid of the trivial cases first: if $p_i$ is suffix/prefix minimum/maximum, one of $[1, i]$ or $[i, n]$ can be reduced to only $2$ elements, and the other part can be reduced to $2$ elements as well, so an answer of $4$ can be trivially achieved. 925 926 Now assume that $p_i$ is not a suffix/prefix minimum/maximum. Let $a, b$ be the positions of prefix minimum and prefix maximum in $[1, i - 1]$ accordingly, and $c, d$ be the positions suffix minimum and suffix maximum. WLOG assume that $a \lt b$, so the prefix minimum appears earlier than the prefix maximum. 927 928 Notice that since $i$ is not an extrema we must have $p_a, p_c \lt p_i \lt p_b, p_d$. Therefore, if $d \lt c$ we can reduce both $[1, i - 1]$ and $[i + 1, n]$, and then do an operation on $[p_b, p_i, p_d]$ which will delete either $p_b$ or $p_d$ and achieve an answer of $4$. 929 930 Therefore assume that the elements are positioned as $[\ldots, p_a, \ldots, p_b, \ldots, p_i, \ldots, p_c, \ldots, p_d, \ldots]$. Notice that we cannot remove $p_a$ or $p_d$ without removing $p_i$, $p_b$ or $p_c$. For example to delete $p_a$ we need an element greater than $p_a$, and the next one can only be located after $p_i$, so we have to remove either $p_b$ or $p_i$. 931 932 Therefore we need to remove $p_b$ or $p_c$. WLOG assume that we are trying to remove $p_b$ first. We cannot do that only with elements in $[1, i]$, so assume that we use an index $i \lt j \lt c$ for that. We perform an operation on $[p_b, p_i, p_j]$. This deletes $p_b$ iff $p_b \lt p_j$. 933 934 Therefore, there needs be an index $j$ satisfying $i \lt j \lt c$ and $p_j \gt p_b$ for $p_b$ to be deletable. For simplicity, take $j$ to be the maximum of $[i, c]$. Then we can achieve an answer of $4$ this way: reduce $[i + 1, c]$ which will leave us with $[p_j, p_c]$, reduce $[1, i - 1]$, reduce $[c, n]$. After this we end up with $[p_a, p_b, p_i, p_j, p_c, p_d]$. Remove $p_b$ in $[p_b, p_i, p_j]$ and then remove $p_j$ in $[p_j, p_c, p_d]$. At the end we will have $[p_a, p_i, p_c, p_d]$. 935 936 The case of removing $p_c$ is identical. Therefore we have a complete solution for determining whether the answer is $\le 4$. A simple way to frame it is this: let $l$ be $\max(a, b)$ and $r$ be $\min(c, d)$. The answer is $3$ or $4$ iff one of the following holds: $i = l$, $i = r$, $\max([p_l, p_{l + 1}, \ldots, p_r]) \gt \max(p_l, p_r)$ or $\min([p_l, p_{l + 1}, \ldots, p_r]) \lt \min(p_l, p_r)$. The last two conditions mean that there is an element that we can use to remove $p_l$ or $p_r$. 937 938 Now we have to determine if the answer is $3$ or $4$. From now assume that the condition above holds. Note that to get $3$ we have to end up with exactly $3$ elements: $1$, $n$ and $p_i$. Denote $\text{pos}_x = i$ as $i$ such that $p_i = x$. WLOG assume that $\text{pos}_1 \lt \text{pos}_n$. Consider two cases: $\text{pos}_1 \lt i \lt \text{pos}_n$ and $\text{pos}_n \lt i$. The case of $\text{pos}_1 \gt i$ is identical to $\text{pos}_n \lt i$. 939 940 Consider $\text{pos}_1 \lt i \lt \text{pos}_n$ first. Notice that we can remove everything in $[\text{pos}_1, \text{pos}_n]$ while keeping $p_i$. Since the answer is $\le 4$ we can leave at most $4$ elements in $[\text{pos}_1, \text{pos}_n]$, let them be $1$, $n$, $p_i$ and $p_j$. Then if $p_i \lt p_j$ we remove $p_j$ using $n$ and if $p_i \gt p_j$ we remove it using $1$. Therefore we only need to make sure that there is nothing left in $[1, \text{pos}_1 - 1]$ and $[\text{pos}_n + 1, n]$. 941 942 Remember that we already proved that if the prefix maximum of $[1, i]$ is in $[1, \text{pos}_1 - 1]$ we cannot remove it without removing $1$, and if the suffix minimum of $[i, n]$ is in $[\text{pos}_n + 1, n]$ we cannot remove it without removing $n$. 943 944 Therefore let $b$ be the index of prefix maximum in $[1, i]$ and $c$ be the index of prefix minimum in $[i, n]$. The answer is $3$ iff $b \ge \text{pos}_1$ and $c \le \text{pos}_n$ and $4$ otherwise. 945 946 Now the last case is $\text{pos}_1 \lt \text{pos}_n \lt i$. Let $a$ be the suffix minimum of $[i, n]$ and $b$ be the suffix maximum, and $p_a = L$ and $p_b = H$. 947 948 Let's get rid of trivial cases. If $a = i$ we can reduce $[\text{pos}_n, n]$ and then $[1, \text{pos}_n]$ to get an answer of $3$. If $b = i$ we need to remove $p_a$ with something in $[\text{pos}_n, i - 1]$. Similarly to our solution for $\le 4$ we need $\min(p_{\text{pos}}, \ldots, p_{i - 1}) \lt p_a$ for this, which is sufficient. 949 950 Now assume $a \neq i$ and $b \neq i$. If $a \lt b$, since the answer is $\le 4$ we can remove $p_a$ using $[\text{pos}_n, i - 1]$, so the case is the same as $a = i$ and is always $3$. 951 952 The only case left is $b \lt a$, which is $[1, n, p_i, H, L]$. We need to remove $H$ using $[\text{pos}_n, i - 1]$ and then remove $L$ using that same interval. Assume we will remove $H$ using $p_j$ and $L$ using $p_k$. 953 954 To do this we need to have $p_k \lt L \lt H \lt p_j$. Since we first remove $H$ then $L$, we need to clear $[j + 1, i - 1]$ without removing $p_k$, therefore we also need to have $k \lt j$. We also need to clear $[k + 1, j]$ after that to remove $L$. 955 956 Claim: it is optimal to choose $k$ to be the index of minimum in $[\text{pos}_n, i]$. Suppose we don't and the index of the minimum is $l$. 957 958 If we choose $k \lt l$ we cannot clear $[k + 1, j]$ since we cannot delete $l$: $[i + 1, b - 1]$ can't be used for that because it needs to be cleared to remove $H = p_b$, and $[1, \text{pos}_n - 1]$ can't be used as well because $n$ and $p_k$ cannot be removed. 959 960 Therefore, $p_k \ge p_l$ and $p_j \le \max(p_{l + 1}, \ldots, p_i)$. Notice that choosing $k$ and $j$ to be exactly these value is always optimal: we can clear $[j + 1, i - 1]$ by reducing $[k, i - 1]$, and then remove $p_j$ in $[n, p_k, p_j]$. Since we need to have $p_k \lt L \lt H \lt p_j$, minimizing $p_k$ and maximizing $p_j$ is needed. 961 962 Therefore, the condition is: let $k$ be the minimum in $[\text{pos}_n, i]$ and $j$ be the maximum in $[k + 1, i]$. Then the answer is $3$ iff $p_k \lt L \lt H \lt p_j$ and $4$ otherwise. This covers all the cases and solves the problem. 963 964 The final solution is $O(n)$ or $O(n \log n)$ depending on the implementation. It can be implemented without considering too much symmetrical cases, refer to the code below. 965 966 **Code** 967 968 ``` 969 #include <bits/stdc++.h> 970 971 using namespace std; 972 973 const int LG = 20; 974 975 vector<int> get_default(vector<int> p) { 976 int n = p.size(); 977 vector<int> pos(n + 1); 978 for(int i = 0; i < n; i++) pos[p[i]] = i; 979 980 vector<int> ans(n, 5); 981 982 int pos_1 = pos[1], pos_n = pos[n]; 983 if(pos_1 > pos_n) return ans; 984 985 vector<int> pos_suff_min(n, n - 1), pos_suff_max(n, n - 1); 986 for(int i = n - 2; ~i; i--) { 987 pos_suff_min[i] = pos_suff_min[i + 1]; 988 if(p[i] < p[pos_suff_min[i]]) pos_suff_min[i] = i; 989 990 pos_suff_max[i] = pos_suff_max[i + 1]; 991 if(p[i] > p[pos_suff_max[i]]) pos_suff_max[i] = i; 992 } 993 994 vector<int> pos_pref_min(n), pos_pref_max(n); 995 for(int i = 1; i < n; i++) { 996 pos_pref_min[i] = pos_pref_min[i - 1]; 997 if(p[i] < p[pos_pref_min[i]]) pos_pref_min[i] = i; 998 999 pos_pref_max[i] = pos_pref_max[i - 1]; 1000 if(p[i] > p[pos_pref_max[i]]) pos_pref_max[i] = i; 1001 } 1002 1003 vector<vector<int>> t_min(n, vector<int>(LG)); 1004 for(int i = 0; i < n; i++) t_min[i][0] = p[i]; 1005 for(int l = 1; l < LG; l++) { 1006 for(int i = 0; i + (1 << l) <= n; i++) { 1007 t_min[i][l] = min(t_min[i][l - 1], t_min[i + (1 << l - 1)][l - 1]); 1008 } 1009 } 1010 auto get_min = [&](int l, int r) { 1011 int L = __lg(r - l + 1); 1012 return min(t_min[l][L], t_min[r - (1 << L) + 1][L]); 1013 }; 1014 1015 vector<vector<int>> t_max(n, vector<int>(LG)); 1016 for(int i = 0; i < n; i++) t_max[i][0] = p[i]; 1017 for(int l = 1; l < LG; l++) { 1018 for(int i = 0; i + (1 << l) <= n; i++) { 1019 t_max[i][l] = max(t_max[i][l - 1], t_max[i + (1 << l - 1)][l - 1]); 1020 } 1021 } 1022 auto get_max = [&](int l, int r) { 1023 int L = __lg(r - l + 1); 1024 return max(t_max[l][L], t_max[r - (1 << L) + 1][L]); 1025 }; 1026 1027 for(int i = pos_1; i < n; i++) { 1028 if(p[i] == 1 || p[i] == n) { 1029 ans[i] = 2; 1030 continue; 1031 } 1032 if(i == 0 || i == n - 1) { 1033 ans[i] = 3; 1034 continue; 1035 } 1036 1037 int a = pos_pref_min[i], b = pos_pref_max[i]; 1038 int c = pos_suff_min[i], d = pos_suff_max[i]; 1039 int l = max(a, b), r = min(c, d); 1040 int min_all = get_min(l, r), max_all = get_max(l, r); 1041 if(l == i && r == i) { 1042 ans[i] = 3; 1043 continue; 1044 } 1045 1046 if(l == i || r == i) ans[i] = 4; 1047 if(abs(p[r] - p[l]) != max_all - min_all) ans[i] = 4; 1048 if(ans[i] != 4) continue; 1049 1050 // 1 p[i] n 1051 if(i < pos_n) { 1052 // H 1 p[i] n 1053 if(b < pos_1) continue; 1054 // 1 p[i] n L 1055 if(c > pos_n) continue; 1056 ans[i] = 3; 1057 continue; 1058 } 1059 1060 // 1 n p[i] 1061 1062 // 1 n p[i] H 1063 if(pos_suff_min[i] == i) ans[i] = 3; 1064 // 1 n p[i] L H, can't remove L 1065 if(get_min(l, i) > p[pos_suff_min[i]]) continue; 1066 // 1 n p[i] L, can remove L 1067 if(r == i) ans[i] = 3; 1068 // 1 n p[i] L H, first remove L, then H 1069 if(c < d) ans[i] = 3; 1070 1071 // 1 n p[i] H L, pick k and j 1072 int k = pos[get_min(pos_n, i)]; 1073 int j = pos[get_max(k, i)]; 1074 if(p[k] < p[c] && p[d] < p[j]) ans[i] = 3; 1075 } 1076 1077 for(auto &i : ans) i = min(i, n); 1078 return ans; 1079 } 1080 1081 vector<int> get(vector<int> p) { 1082 int n = p.size(); 1083 1084 vector<int> ans(n, n); 1085 for(int t_reverse = 0; t_reverse < 2; t_reverse++) { 1086 for(int t_invert = 0; t_invert < 2; t_invert++) { 1087 auto curr_ans = get_default(p); 1088 if(t_reverse) reverse(curr_ans.begin(), curr_ans.end()); 1089 for(int i = 0; i < n; i++) ans[i] = min(ans[i], curr_ans[i]); 1090 1091 for(auto &i : p) i = n + 1 - i; 1092 } 1093 reverse(p.begin(), p.end()); 1094 } 1095 return ans; 1096 } 1097 1098 void solve() { 1099 int n; 1100 cin >> n; 1101 vector<int> p(n); 1102 for(auto &i : p) { 1103 cin >> i; 1104 } 1105 1106 auto ans = get(p); 1107 for(auto i : ans) cout << i << " "; cout << '\n'; 1108 } 1109 1110 signed main() { 1111 ios_base::sync_with_stdio(0); cin.tie(0); 1112 int ttt = 1; 1113 cin >> ttt; 1114 while(ttt--) { 1115 solve(); 1116 } 1117 } 1118 ``` 1119 1120 **Rate The Problem!** 1121 1122 * Good Problem 1123 * Okay Problem 1124 * Bad Problem 1125 * Didn't Solve