1526.md (32867B)
1 Source: https://codeforces.com/blog/entry/91195 2 3 ## [1526A - Mean Inequality](/contest/1526/problem/A "Codeforces Round 723 (Div. 2)") 4 5 Setter: [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o") 6 Preparer: [errorgorn](/profile/errorgorn "International Master errorgorn") 7 8 **Hint 1** 9 10 Notice that the array size is even length. Usually in such problems, we would split the array into $2$ equal parts. Can you figure out what those $2$ parts are? 11 12 **Hint 2** 13 14 We sort the array and split it into the big half and the small half. 15 16 **Solution** 17 18 The main idea is that we can split the numbers into the two halves, the big half and small half, we can place the bigger half at the odd positions and the smaller half at the even positions. 19 20 This works because the smallest big number is larger than the biggest small number. Hence, the mean of any two small numbers is smaller than any big number, and the mean of any two big numbers is bigger than any small number. 21 22 **Code (C++)** 23 24 ``` 25 //雪花飄飄北風嘯嘯 26 //天地一片蒼茫 27 28 #include <bits/stdc++.h> 29 #include <ext/pb_ds/assoc_container.hpp> 30 #include <ext/pb_ds/tree_policy.hpp> 31 #include <ext/rope> 32 using namespace std; 33 using namespace __gnu_pbds; 34 using namespace __gnu_cxx; 35 #define ll long long 36 #define ii pair<ll,ll> 37 #define iii pair<ii,ll> 38 #define fi first 39 #define se second 40 #define endl '\n' 41 #define debug(x) cout << #x << " is " << x << endl 42 43 #define pub push_back 44 #define pob pop_back 45 #define puf push_front 46 #define pof pop_front 47 #define lb lower_bound 48 #define ub upper_bound 49 50 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 51 #define all(x) (x).begin(),(x).end() 52 #define sz(x) (int)(x).size() 53 54 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 55 //change less to less_equal for non distinct pbds, but erase will bug 56 57 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 58 59 int n; 60 int arr[55]; 61 62 int main(){ 63 ios::sync_with_stdio(0); 64 cin.tie(0); 65 cout.tie(0); 66 cin.exceptions(ios::badbit | ios::failbit); 67 68 int TC; 69 cin>>TC; 70 while (TC--){ 71 cin>>n; 72 rep(x,0,2*n) cin>>arr[x]; 73 74 sort(arr,arr+2*n); 75 76 rep(x,0,n) cout<<arr[x]<<" "<<arr[x+n]<<" "; 77 cout<<endl; 78 } 79 } 80 ``` 81 82 **Code (Python)** 83 84 ``` 85 [(lambda n: (lambda arr : [print(f'{arr[i]} {arr[i+n]}', end = ' \n'[i==n-1]) for i in range(n)])(sorted(list(map(int,input().split())))))(int(input())) for _ in range(int(input()))] 86 ``` 87 88 ## [1526B - I Hate 1111](/contest/1526/problem/B "Codeforces Round 723 (Div. 2)") 89 90 Setter: [errorgorn](/profile/errorgorn "International Master errorgorn") 91 Preparer: [errorgorn](/profile/errorgorn "International Master errorgorn") 92 93 **Hint 0** 94 95 Read the name of the problem ;) 96 97 **Hint 1** 98 99 $1111=11 \cdot 101$ 100 101 **Hint 2** 102 103 All numbers other than $11$ and $111$ are useless. 104 105 **Solution** 106 107 ## Method 1 108 109 Notice that $1111=11 \cdot 100+11$ and similarly $11111=111 \cdot 100 + 11$. This implies that we can construct $1111$ and all bigger numbers using only $11$ and $111$. So it suffices to check whether we can construct $X$ from $11$ and $111$ only. 110 111 Suppose $X=A \cdot 11 + B \cdot 111$, where $A,B \geq 0$. Suppose $B=C \cdot 11 + D$, where $D \lt 11$. Then $X=(A+C \cdot 111) \cdot 11 + D \cdot 111$. So we can just brute force all $11$ value of $D$ to check whether $X$ can be made. 112 113 ## Method 2 114 115 Since $\gcd(11,111)=1$, by the [Chicken McNugget Theorem](https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem), all numbers greater than $1099$ can be written as a sum of $11$ and $111$. We can use brute force to find the answer to all values less than or equal to $1099$ and answer yes for all other numbers. 116 117 **Code (C++)** 118 119 ``` 120 //雪花飄飄北風嘯嘯 121 //天地一片蒼茫 122 123 #include <bits/stdc++.h> 124 #include <ext/pb_ds/assoc_container.hpp> 125 #include <ext/pb_ds/tree_policy.hpp> 126 #include <ext/rope> 127 using namespace std; 128 using namespace __gnu_pbds; 129 using namespace __gnu_cxx; 130 #define ll long long 131 #define ii pair<ll,ll> 132 #define iii pair<ii,ll> 133 #define fi first 134 #define se second 135 #define endl '\n' 136 #define debug(x) cout << #x << " is " << x << endl 137 138 #define pub push_back 139 #define pob pop_back 140 #define puf push_front 141 #define pof pop_front 142 #define lb lower_bound 143 #define ub upper_bound 144 145 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 146 #define all(x) (x).begin(),(x).end() 147 #define sz(x) (int)(x).size() 148 149 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 150 //change less to less_equal for non distinct pbds, but erase will bug 151 152 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 153 154 int main(){ 155 ios::sync_with_stdio(0); 156 cin.tie(0); 157 cout.tie(0); 158 cin.exceptions(ios::badbit | ios::failbit); 159 160 int TC; 161 cin>>TC; 162 while (TC--){ 163 int n; 164 cin>>n; 165 166 rep(x,0,20){ 167 if (n%11==0){ 168 cout<<"YES"<<endl; 169 goto done; 170 } 171 172 n-=111; 173 if (n<0) break; 174 } 175 cout<<"NO"<<endl; 176 177 done:; 178 } 179 } 180 ``` 181 182 **Code (Python)** 183 184 ``` 185 [(lambda n : print("YES" if (n >= 111*(n%11)) else "NO"))(int(input())) for _ in range(int(input()))] 186 ``` 187 188 ## [1526C1 - Potions (Easy Version)](/contest/1526/problem/C1 "Codeforces Round 723 (Div. 2)") and [1526C2 - Potions (Hard Version)](/contest/1526/problem/C2 "Codeforces Round 723 (Div. 2)") 189 190 Setter: [errorgorn](/profile/errorgorn "International Master errorgorn") and [oolimry](/profile/oolimry "Master oolimry") 191 Preparer: [oolimry](/profile/oolimry "Master oolimry") 192 193 **Hint 1** 194 195 Try dp! 196 197 **Hint 2** 198 199 The dp states are position and number of potions drank. 200 201 **Hint 3** 202 203 Speedup dp or use greedy for full solution. 204 205 **Solution** 206 207 ## Method 1 — DP 208 209 Let's consider a dynamic programming solution. Let $dp[i][k]$ be the maximum possible health achievable if we consider only the first $i$ potions, and $k$ is the total number of potions taken. 210 211 The transition is as follows: $dp[i][k] = max(dp[i-1][k-1] + a_i, dp[i-1][k])$ if $dp[i-1][k-1] + a_i \geq 0$, and just $dp[i-1][k]$ otherwise. The first term represents the case if we take potion $i$ and the second term is when we ignore potion $i$. 212 213 This runs in $O(n^2)$ and passes the easy version. 214 215 ## Method 2 — Greedy 1 216 217 We iterate through the potions in non-decreasing order and drink the potion if we do not die. 218 219 For convenience, we define $c_i=a_i+i \cdot \epsilon$, where $\epsilon$ is a very small real number so that we can treat $c_i$ as distinct integers. We will show by exchange argument that our greedy is optimal. 220 221 Let $S$ be the set of potions that is an optimal solution. 222 223 Suppose $i \lt j$ and $c_i \lt c_j$. If $i \in S$ and $j \notin S$, then removing $i$ and adding $j$ into $S$ will still make $S$ a valid solution. 224 225 Now, suppose that position $i$ is not drunk. We can assume that there are no $k$ ($k \lt i$) such that $c_k \lt c_i$ and $k$ is drunk by the previous assertion. Suppose we add $i$ into $S$. If we reach a position $j$ (we possibly die at $j$) where $c_j \lt c_i$, then we can remove $j$ from $S$ and add $i$ to $S$. Otherwise, our greedy will also not choose $i$, as it was not chosen when we only consider indexes $k$ such that $c_k \lt c_i$. 226 227 Notice that we can arbitrarily define the way $\epsilon$ is added, so basically we can process $a_i$ in any non-increasing fashion. 228 229 Doing this naively is $O(n^2)$ as well. However, using a range add range max lazy propagation segment tree, we can check if a certain potion can be drunk without dying, and the solution runs in $O(n \log n)$. 230 231 ## Method 3 — Greedy 2 / DP 2 232 233 We process the potions from left to right. At the same time, we maintain the list of potions we have taken so far. When processing potion $i$, if we can take $i$ without dying, then we take it. Otherwise, if the most negative potion we've taken is more negative than potion $i$, then we can swap out potion $i$ for that potion. To find the most negative potion we've taken, we can maintain the values of all potions in a minimum priority_queue. This runs in $O(nlogn)$ as well 234 235 To prove that this works, let's consider best solution where we take exactly $k$ potions (best as in max total health). The solution involves taking the $k$ largest values in our priority queue. Then when considering a new potion, we should see whether swapping out the new potion for the $k$th largest potion will improve the answer. 236 237 Since the priority queue is strictly decreasing, there will be a cutoff $K$, where for $k$ at most $K$, the answer is not affected, and for larger than $K$, we swap out the $k$th largest potion. It turns out this process is equivalent to inserting the new potion's value into the priority_queue. For those positions at most $K$, they are not affected. For the positions larger than $K$, the elements get pushed back one space, meaning that the smallest element is undrinked. 238 239 This can also be seen as an efficient way to to transition from one layer of the $dp$ table to the next. 240 241 **Code (C++)** 242 243 ``` 244 #include <bits/stdc++.h> 245 using namespace std; 246 typedef pair<long long, long long> ii; 247 248 struct node{ 249 int s, e, m; 250 long long val = 0; long long lazy = 0; 251 node *l, *r; 252 253 node(int S, int E){ 254 s = S, e = E, m = (s+e)/2; 255 if(s != e){ 256 l = new node(s, m); 257 r = new node(m+1, e); 258 } 259 } 260 261 void apply(long long L){ 262 val += L; 263 lazy += L; 264 } 265 void push(){ 266 if(s == e) return; 267 l->apply(lazy); 268 r->apply(lazy); 269 lazy = 0; 270 } 271 272 void update(int S, int E, long long L){ 273 push(); 274 if(s == S && E == e){ 275 apply(L); 276 return; 277 } 278 else if(E <= m) l->update(S, E, L); 279 else if(S >= m+1) r->update(S, E, L); 280 else l->update(S, m, L), r->update(m+1, E, L); 281 val = min(l->val, r->val); 282 } 283 284 long long query(int S, int E){ 285 push(); 286 if(s == S && E == e) return val; 287 else if(E <= m) return l->query(S, E); 288 else if(S >= m+1) return r->query(S, E); 289 else return min(l->query(S, m), r->query(m+1, E)); 290 } 291 } *root; 292 293 int main(){ 294 ios_base::sync_with_stdio(false); cin.tie(0); 295 296 int n; cin >> n; 297 ii arr[n]; 298 for(int i = 0;i < n;i++){ 299 cin >> arr[i].first; 300 arr[i].second = i; 301 } 302 303 sort(arr,arr+n); 304 reverse(arr,arr+n); 305 int ans = 0; 306 root = new node(0, n-1); 307 for(int i = 0;i < n;i++){ 308 int pos = arr[i].second; 309 long long x = arr[i].first; 310 311 if(x + root->query(pos,n-1) >= 0){ 312 ans++; 313 root->update(pos,n-1,x); 314 } 315 } 316 317 cout << ans; 318 } 319 ``` 320 321 **Code 2 (C++)** 322 323 ``` 324 #include <bits/stdc++.h> 325 using namespace std; 326 327 int main(){ 328 ios_base::sync_with_stdio(false); cin.tie(0); 329 330 int n; cin >> n; 331 priority_queue<long long, vector<long long>, greater<long long> > pq; 332 long long S = 0; 333 334 for(int i = 1;i <= n;i++){ 335 long long x; cin >> x; 336 S += x; 337 pq.push(x); 338 339 while(S < 0){ 340 S -= pq.top(); 341 pq.pop(); 342 } 343 } 344 345 cout << (int) pq.size(); 346 } 347 ``` 348 349 **Code (Python)** 350 351 ``` 352 import heapq 353 H = [] 354 n=int(input()) 355 for i in list(map(int,input().split())): 356 tot = (tot+i if 'tot' in locals() or 'tot' in globals() else i) 357 tot -= ((heapq.heappush(H,i) if tot >= 0 else heapq.heappushpop(H,i)) or 0) 358 print(len(H)) 359 ``` 360 361 ## [1526D - Kill Anton](/contest/1526/problem/D "Codeforces Round 723 (Div. 2)") 362 363 Setter: [errorgorn](/profile/errorgorn "International Master errorgorn") 364 Preparer: [errorgorn](/profile/errorgorn "International Master errorgorn") 365 366 **Hint 1** 367 368 The time it takes for Anton's body to revert the string is related to inversion number. 369 370 **Solution** 371 372 We claim that in the optimal answer all characters of some type will appear consecutively. 373 374 **Proof** 375 376 Consider the character at position $i$ in string $s$. We define $C_i$ as the position in which that character will be in string $t$. For $s=\texttt{CAGCAA}$ and $t=\texttt{AAGCAC}$, $C={4,1,3,6,2,5}$. Then the minimum number of moves to transformed $s$ to $t$ is given by the inversion index of $C$. 377 378 Suppose we find a substring of $s$ where it is $\texttt{XXAA...AA[A]XX...XX[A]AA...AAXX}$, where characters $\texttt{X}$ can be either one of $\texttt{TCG}$. The square brackets are just for clarity of explanation. We will show that it our solution will not be worse if we merge these $2$ contiguous segments of $\texttt{A}$. 379 380 Consider transforming the string into $\texttt{XXAA...AAXX...XX[A][A]AA...AAXX}$ and $\texttt{XXAA...AA[A][A]XX...XXAA...AAXX}$. Let the difference in the number of moves be $D_1$ and $D_2$ respectively. And let the index of $\texttt{[A]}$s be $i$ and $j$ respectively. 381 382 Then $D_1=\sum\limits_{k=i+1}^{j-1} \sigma(C_k-C_i)$ and $D_2=\sum\limits_{k=i+1}^{j-1} \sigma(C_j-C_k)$, where $\sigma(x)=\frac{x}{|x|}$, or rather $\sigma$ is the [sign function](https://en.wikipedia.org/wiki/Sign_function). 383 384 I claim that $D_1+D_2 \geq 0$. Suppose that $D_1+D_2 \lt 0$, then there exist $k$ such that $\sigma(C_k-C_i)+\sigma(C_j-C_k) \lt 0$ which implies $C_k-C_i \lt 0$ and $C_j-C_k \lt 0$. However, this implies that $C_j \lt C_i$ which is clearly a contradiction. 385 386 Since $D_1+D_2 \geq 0$, either $D_1 \geq 0$ or $D_2 \geq 0$. WLOG, $D_1 \geq 0$. This implies that we turn $s$ into $\texttt{XXAA...AAXX...XX[A][A]AA...AAXX}$ without decreasing the number of moves to transform $s$ into $t$. Now, consider the rest of the $\texttt{A}$ on the left segment of $\texttt{A}$. We can move it too the right also. Recall that $D_1 + D_2 \geq 0$. In this case, we know that $D_2 \leq 0$ as it is the cost to move the left $\texttt{[A]}$ back to its original position. So $D_1 \geq 0$. Therefore, we have merged $2$ different segments of $A$ without decreasing the number of moves to transform $s$ into $t$. 387 388 So, we can try all $24$ possible strings and check the number of moves Anton's body needs to transform each string. The time limit is relaxed enough for a $O(n \log n)$ similar to [1430E - String Reversal](/contest/1430/problem/E "Educational Codeforces Round 96 (Rated for Div. 2)"). 389 390 But there is a $O(n)$ solution, the number of moves Anton's body needs to transform each string is given by the number of inversions in the string. But since we know that we only care about strings that have all the same characters appear consecutively, we can just keep a count of the number of inversions for each pair of characters. 391 392 **Code (C++)** 393 394 ``` 395 //雪花飄飄北風嘯嘯 396 //天地一片蒼茫 397 398 #include <bits/stdc++.h> 399 #include <ext/pb_ds/assoc_container.hpp> 400 #include <ext/pb_ds/tree_policy.hpp> 401 #include <ext/rope> 402 using namespace std; 403 using namespace __gnu_pbds; 404 using namespace __gnu_cxx; 405 #define ll long long 406 #define ii pair<ll,ll> 407 #define iii pair<ii,ll> 408 #define fi first 409 #define se second 410 #define endl '\n' 411 #define debug(x) cout << #x << " is " << x << endl 412 413 #define pub push_back 414 #define pob pop_back 415 #define puf push_front 416 #define pof pop_front 417 #define lb lower_bound 418 #define ub upper_bound 419 420 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 421 #define all(x) (x).begin(),(x).end() 422 #define sz(x) (int)(x).size() 423 424 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 425 //change less to less_equal for non distinct pbds, but erase will bug 426 427 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 428 429 int n; 430 string s; 431 int cnt[4]; 432 433 ll flips[4][4]; 434 435 map<char,int> id={{'A',0},{'N',1},{'O',2},{'T',3}}; 436 string cset="ANOT"; 437 438 int main(){ 439 ios::sync_with_stdio(0); 440 cin.tie(0); 441 cout.tie(0); 442 cin.exceptions(ios::badbit | ios::failbit); 443 444 int TC; 445 cin>>TC; 446 while (TC--){ 447 cin>>s; 448 n=sz(s); 449 450 memset(cnt,0,sizeof(cnt)); 451 memset(flips,0,sizeof(flips)); 452 453 rep(x,0,n){ 454 cnt[id[s[x]]]++; 455 } 456 rep(a,0,4){ 457 int curr=0; 458 rep(x,0,n){ 459 flips[a][id[s[x]]]+=curr; 460 if (id[s[x]]==a) curr++; 461 } 462 } 463 464 ll best=-1; 465 vector<int> ans; 466 467 vector<int> v={0,1,2,3}; 468 do{ 469 ll curr=0; 470 rep(x,0,4){ 471 rep(y,x+1,4){ 472 curr+=flips[v[y]][v[x]]; 473 } 474 } 475 476 if (curr>best){ 477 best=curr; 478 ans=v; 479 } 480 } while (next_permutation(all(v))); 481 482 for (auto &it:ans) rep(x,0,cnt[it]) cout<<cset[it]; 483 cout<<endl; 484 } 485 } 486 ``` 487 488 **Code (Python)** 489 490 ``` 491 import itertools 492 493 TC=int(input()) 494 495 m={"A":0,"N":1,"O":2,"T":3} 496 st="ANOT" 497 498 for _ in range(TC): 499 s=input() 500 arr=[] 501 502 for ch in s: 503 arr.append(m[ch]) 504 505 cnt=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] 506 cnt1=[0,0,0,0] 507 508 for i in arr: 509 for j in range(4): 510 cnt[j][i]+=cnt1[j] 511 cnt1[i]+=1 512 513 val=-1 514 best=[] 515 516 for perm in itertools.permutations([0,1,2,3]): 517 curr=0 518 for i in range(4): 519 for j in range(i+1,4): 520 curr+=cnt[perm[j]][perm[i]] 521 522 if (curr>val): 523 val=curr 524 best=perm 525 526 527 for i in range(4): 528 for j in range(cnt1[best[i]]): print(st[best[i]],end="") 529 530 print() 531 ``` 532 533 ## [1526E - Oolimry and Suffix Array](/contest/1526/problem/E "Codeforces Round 723 (Div. 2)") 534 535 Setter: [iLoveIOI](/profile/iLoveIOI "Candidate Master iLoveIOI") 536 Preparer: [iLoveIOI](/profile/iLoveIOI "Candidate Master iLoveIOI") 537 538 **Hint 1** 539 540 Try to solve the problem of the minimal $K$ needed to make a string with such a suffix array. 541 542 **Solution** 543 544 First, let's consider a simpler problem. 545 546 Is it possible to make a string with a certain suffix array given an alphabet size $k$. 547 548 Consider two adjacent suffixes in the suffix array "xy" and "ab" where $b$ and $y$ are some strings and $x$ and $a$ are some characters i.e. $x$ is the first character of that suffix and similarly for $a$. If $b$ and $y$ don't exist we consider them as \$, i.e. smaller than everything. Also, "xy" comes before "ab". 549 550 Observation: If the position of $b$ is less than the position of $y$ in the suffix array, $x$ must be less than $a$. Otherwise, $x$ must be less than or equal to $a$. 551 552 This can be easily shown as "xy" must be lexicographically smaller than "ab". This is sufficient also. 553 554 Thus we can iterate through the suffix array and check if $pos[arr[i]+1] \gt pos[arr[i+1]+1]$ where $arr$ is the suffix array and $pos$ is the position of the $i$th element in the suffix array. If this condition holds then the $arr[i]$ th character must be strictly less than the $arr[i+1]$ th character. Thus we can just count how many such pairs exist. If this count is larger than the alphabet size no such string is possible. Otherwise, such string exists. Note that special care must be taken when considering $arr[i]=n-1$ as $pos[n]$ may not be defined ($0$-indexed). 555 556 After tackling the simpler question we move on to the full question of counting how many such strings are there. If we consider the string as an array and the order of the array as the order of the suffix array meaning that the $i$ th element of this array is the $arr[i]$ th element of the string. We have now transformed the question into **"Given that some elements must be greater than the previous elements while others can be equal. Count how many arrays are there such that the largest element is less than $k$"**. 557 558 Consider the difference array, some elements must be $\geq 1$ while some can be $\geq 0$. We add padding to the front and back of the array so as to account for the first value being non-zero and the last element being less than $k$. These two elements are both $\geq 0$. Let $cnt$ be the number of elements that must be $\geq 1$ in the difference array. Now, this becomes count how many arrays of $(n-1+2)=(n+1)$ non-negative elements sum to $k-cnt$. This can be solved using stars and bars so the final answer comes out to be $n+1+k-cnt \choose n$ which can be found easily. Note that we define $\binom{a}{b}=0$ when $a \lt b$. 559 560 Final Complexity $O(n\log MOD)$ or $O(n)$ depending on how you find the modular inverse. 561 562 Btw $k$ was chosen to also be $\leq 2\times 10^5$ so as to hide the final complexity :) 563 564 **Code (C++)** 565 566 ``` 567 /*input 568 5 4 569 3 4 2 1 0 570 571 */ 572 #include<bits/stdc++.h> 573 #include <ext/pb_ds/assoc_container.hpp> 574 #include <ext/pb_ds/tree_policy.hpp> 575 using namespace std; 576 using namespace __gnu_pbds; 577 typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; 578 //order_of_key #of elements less than x 579 // find_by_order kth element 580 typedef long long int ll; 581 #define ld long double 582 #define pii pair<ll,ll> 583 #define f first 584 #define s second 585 #define pb push_back 586 #define REP(i,n) for(ll i=0;i<n;i++) 587 #define REP1(i,n) for(int i=1;i<=n;i++) 588 #define FILL(n,x) memset(n,x,sizeof(n)) 589 #define ALL(_a) _a.begin(),_a.end() 590 #define sz(x) (int)x.size() 591 const ll maxn=2e5+5; 592 const ll maxlg=__lg(maxn)+2; 593 const ll INF64=4e17; 594 const int INF=0x3f3f3f3f; 595 const ll MOD=998244353; 596 const ld PI=acos(-1); 597 const ld eps=1e-9; 598 #define lowb(x) x&(-x) 599 #define MNTO(x,y) x=min(x,(__typeof__(x))y) 600 #define MXTO(x,y) x=max(x,(__typeof__(x))y) 601 #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) 602 ll mult(ll a,ll b){ 603 return ((a%MOD)*(b%MOD))%MOD; 604 } 605 ll mypow(ll a,ll b){ 606 607 if(b<=0) return 1; 608 if(a<=0) return 0; 609 ll res=1LL; 610 while(b){ 611 if(b&1) res=mult(res,a); 612 a=mult(a,a); 613 b>>=1; 614 } 615 return res; 616 } 617 int arr[maxn],pos[maxn]; 618 ll inv(ll x){ 619 return mypow(x,MOD-2); 620 } 621 int32_t main(){ 622 ios::sync_with_stdio(false),cin.tie(0); 623 int n,k; 624 cin>>n>>k; 625 --k; 626 REP(i,n) cin>>arr[i],pos[arr[i]]=i; 627 pos[n]=-1; 628 int cnt=0; 629 REP(i,n-1){ 630 // character at arr[i] and arr[i+1] cannot be the same 631 if(pos[arr[i]+1]>pos[arr[i+1]+1]){ 632 ++cnt; 633 } 634 } 635 //calculate c(k-cnt+n+1-1,n+1-1) 636 k-=cnt; 637 if(k<0){ 638 cout<<0; 639 return 0; 640 } 641 ll ans=1; 642 REP1(i,n){ 643 ans=mult(ans,inv(i)); 644 ans=mult(ans,(k+i)); 645 } 646 cout<<ans; 647 } 648 ``` 649 650 **Code (Python)** 651 652 ``` 653 MOD=998244353 654 655 n,k=map(int,input().split()) 656 arr=list(map(int,input().split())) 657 658 pos=[0]*(n+1) 659 660 for i in range(n): 661 pos[arr[i]]=i 662 pos[n]=-1 663 664 cnt=0 665 666 for i in range(n-1): 667 if (pos[arr[i]+1]>pos[arr[i+1]+1]): cnt+=1 668 669 #k-cnt+n-1 choose n 670 num,denom=1,1 671 672 for i in range(n): 673 num=num*(k-cnt+n-1-i)%MOD 674 denom=denom*(i+1)%MOD 675 676 print(num*pow(denom,MOD-2,MOD)%MOD) 677 ``` 678 679 ## [1526F - Median Queries](/contest/1526/problem/F "Codeforces Round 723 (Div. 2)") 680 681 Setter: [errorgorn](/profile/errorgorn "International Master errorgorn") and [oolimry](/profile/oolimry "Master oolimry") 682 Preparer: [errorgorn](/profile/errorgorn "International Master errorgorn") 683 684 **Hint 1** 685 686 Find elements $1$ and $2$ in $N+420$ queries. 687 688 **Hint 2** 689 690 Find a pair $(a,b)$ such that $|p[b]-p[a]| \leq \frac{n}{3}-c$, where $c$ is some constant. 691 692 **Solution** 693 694 The problem can be broken into $2$ main parts: 695 696 * Finding a pair $(a,b)$ such that $|p[a]-p[b]|$ is roughly less than a third. 697 * Finding elements $1$ and $2$ (actually we may find $N$ and $N-1$ but it is the same). 698 * Find the rest of the elements 699 700 A convenient way to think about the queries, is that given $p[a] \lt p[b] \lt p[c]$, we will be returned $\max(p[b]-p[a],p[c]-p[b])$. 701 702 We will spend the first queries to find a tuple $(a,b,c)$ such that the return value of this query is at most $\lfloor \frac{n-4}{6} \rfloor$. The easiest way to do this is by randomly choosing distinct $a$,$b$,$c$ and querying it. See proof 1 for the random analysis. But there is also a deterministic solution. Choose any $13$ elements from the array, and it is guaranteed that there exists a tuple in those $13$ elements such that the return value of the query is at most $\lfloor \frac{n-4}{6} \rfloor$, see proof 2. To query all tuples in this sub-array of size $13$, it takes $286$ queries, which fits very comfortably under $420$. [user14767553](/profile/user14767553 "Candidate Master user14767553") conjectured that a sub-array of size $10$ works, however we are unable to prove it. You can try to hack his solution at [117685511](/contest/1526/submission/117685511 "Submission 117685511 by user14767553"). 703 704 Among $a$, $b$, and $c$, we choose $a$ and $b$. The important idea here is that the gap between $a$ and $b$ is small, because we have found a tuple $(a,b,c)$ is less than or equal to $\lfloor \frac{n-4}{6} \rfloor$, so $|p[a]-p[b]| \leq 2 \cdot \lfloor \frac{n-4}{6} \rfloor \leq \lfloor \frac{n-4}{3} \rfloor$. Now, we query all tuples $(a,b,x)$ for all $x \ne a$ and $x \ne b$. Since the gap between $a$ and $b$ is small, we should be able to identify either $(1,2)$ or $(n,n-1)$. This is because either $p[a]-1 \gt p[b]-p[a]$ or $n-p[b] \gt p[b] - p[a]$ (WLOG assuming $p[b] \gt p[a]$), see proof 3. Therefore, the furthest $x$ will return the largest value when querying for $(a,b,x)$. (If there's ties choose anyone). 705 706 Suppose we found element $1$, there are at most two possible candidates for element $2$, $y_1$ and $y_2$ (the other possible candidate will be either $n$ or $n-1$). We can use 2 queries to figure out which of them is element $2$. We can query $(1, y_1, a)$ and $(1, y_2, a)$. Whichever produces the smaller value is element $2$, see proof 4. 707 708 Once we have found elements $1$ and $2$, solving the rest of the problem is simple. Querying $(1,2,x)$ will always return $x-2$. And we can find the rest of the elements in another $n-2$ queries. Do not forgot about the condition that $p[0] \lt p[1]$! 709 710 **Proof 1** 711 712 This is a rough asymptotic analysis for large $n$. 713 714 Observe that if 715 716 * $\frac n6 \lt b \lt \frac{5n}{6}$ (this happens around $\frac 23$ of the time) 717 * $b-\frac{n}{6} \lt a \lt b$ (around $\frac 16$ of the time) 718 * $b \lt c \lt b+\frac{n}{6}$ (around $\frac 1 6$ of the time) 719 720 Around $\frac{1}{54}$, we will get a return value of less than $\frac{1}{6}$. Since there are 6 permutations (i.e. relative orderings of a,b,c), there is a probability of roughly $\frac{1}{9}$ that some permutation of $(a,b,c)$ satisfies the above condition. 721 722 The probability that we do not find such a tuple after $420$ queries is $(\frac{8}{9})^{420} \approx 3.28\cdot10^{-22}$. To put this into perspective, you have a higher chance of: 723 724 * Flipping heads $70$ times in a row 725 * Drawing a royal flush $5$ times in a row 726 * Anton not rejecting a data structure problem 727 728 **Proof 2** 729 730 We will use contradiction. 731 732 let $d1, d2, \ldots ...$ refer to the gaps between the elements. If the maximum any two consecutive gaps is at most $\lfloor \frac{n-4}{6} \rfloor$, one of the queries will work. As such, it is necessary that least $6$ of these gaps are at least $\lfloor \frac{n-4}{6} \rfloor$. 733 734 Then we have $6 \cdot (\lfloor \frac{n-4}{6} \rfloor+1) +13$ as the smallest possible size of the original array. 735 736 However, $6 \cdot (\lfloor \frac{n-4}{6} \rfloor+1) +13 \geq 6 \cdot (\frac{n-9}{6}+1) +13 = n+10$ which is a clear contradiction. 737 738 **Proof 3** 739 740 We proof this statement by contrapositive. 741 742 This statement is equivalent to: if $a-1 \leq b-a$ and $n-b \leq b-a$, then $b-a \gt \lfloor \frac{n-4}{3} \rfloor$. Abbreviating $p[a]$ and $p[b]$ to $a$ and $b$ respectively. 743 744 Using algebra, $a-1 \leq b-a$ implies $2a -1 \leq b$ and $n+a \leq 2b$. 745 746 Therefore, $n+3a-1 \leq 3b$. 747 748 Then, $\frac{n-1}{3} \leq b-a$. 749 750 It is trivial to see that $\lfloor \frac{n-4}{3} \rfloor \lt \frac{n-1}{3}$. 751 752 Therefore, we have shown that $b-a \gt \lfloor \frac{n-4}{3} \rfloor$. 753 754 **Proof 4** 755 756 Suppose that $y_1=2$ and $y_2 = n-1$ or $y_2=n$. We can bound $a$ by $y_1 \lt a \lt y_2$ 757 758 We want to show that the query of $(1,y_1,a)$ is smaller than $(1,a,y_2)$. 759 760 This is equivalent to showing that $\max(|1-2|,|2-a|) \lt \max (|1-a|,|a-y_2|)$. 761 762 Since $2 \lt a$, $\max(|1-2|,|2-a|)=a-2$. 763 764 Case $1$: $|1-a| \geq |a-y_2|$ 765 $\max(|1-a|,|a-y_2|)=a-1$. 766 Therefore, $\max(|1-2|,|2-a|) = a-2 \lt a-1 = \max(|1-a|,|a-y_2|)$. 767 768 Case $2$: $|a-y_2| \gt |1-a|$ 769 $\max(|1-a|,|a-y_2|)=|a-y_2|$. 770 Therefore, $\max(|1-2|,|2-a|) = a-2 \lt a-1 = |1-a| \lt |a-y_2| = \max(|1-a|,|a-y_2|)$. 771 772 **Code (C++)** 773 774 ``` 775 //雪花飄飄北風嘯嘯 776 //天地一片蒼茫 777 778 #include <bits/stdc++.h> 779 #include <ext/pb_ds/assoc_container.hpp> 780 #include <ext/pb_ds/tree_policy.hpp> 781 #include <ext/rope> 782 using namespace std; 783 using namespace __gnu_pbds; 784 using namespace __gnu_cxx; 785 #define ll long long 786 #define ii pair<ll,ll> 787 #define iii pair<ii,ll> 788 #define fi first 789 #define se second 790 #define debug(x) cout << #x << " is " << x << endl 791 792 #define pub push_back 793 #define pob pop_back 794 #define puf push_front 795 #define pof pop_front 796 #define lb lower_bound 797 #define up upper_bound 798 799 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 800 #define all(x) (x).begin(),(x).end() 801 #define sz(x) (int)(x).size() 802 803 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 804 //change less to less_equal for non distinct pbds, but erase will bug 805 806 mt19937 rng(177013); 807 808 int query(int a,int b,int c){ 809 cout<<"? "<<a<<" "<<b<<" "<<c<<endl; 810 int temp; 811 cin>>temp; 812 813 return temp; 814 } 815 816 void sort(int &a,int &b,int &c){ 817 if (a>b) swap(a,b); 818 if (b>c) swap(b,c); 819 if (a>b) swap(a,b); 820 } 821 822 void solve(){ 823 int n; 824 cin>>n; 825 826 vector<int> ans(n+5,0); 827 828 set<tuple<int,int,int> > s; 829 830 int a,b,c; 831 rep(x,1,14) rep(y,x+1,14) rep(z,y+1,14){ 832 if (query(x,y,z)<=(n-4)/6){ 833 a=x,b=y,c=z; 834 break; 835 } 836 } 837 838 map<int,vector<int>,greater<int> > m; 839 rep(x,1,n+1) if (x!=a && x!=b){ 840 m[query(a,b,x)].push_back(x); 841 } 842 843 int hv=(*m.begin()).fi; 844 if (sz(m[hv-1])>=2){ //there must be exactly 2 845 if (query(m[hv][0],m[hv-1][0],a)> 846 query(m[hv][0],m[hv-1][1],a)) 847 swap(m[hv-1][0],m[hv-1][1]); 848 } 849 850 int hi=m[hv][0],hi2=m[hv-1][0]; 851 852 //cout<<hi2<<" "<<hi<<endl; 853 854 ans[hi]=1,ans[hi2]=2; 855 rep(x,1,n+1) if (x!=hi2 && x!=hi){ 856 ans[x]=query(hi,hi2,x)+2; 857 } 858 859 if (ans[1]>ans[2]) rep(x,1,n+1) ans[x]=n-ans[x]+1; 860 861 cout<<"! "; rep(x,1,n+1) cout<<ans[x]<<" "; cout<<endl; 862 863 cin>>n; //read stupid value 864 } 865 866 int main(){ 867 ios::sync_with_stdio(0); 868 cin.tie(0); 869 cout.tie(0); 870 cin.exceptions(ios::badbit | ios::failbit); 871 872 int TC; 873 cin>>TC; 874 while (TC--){ 875 solve(); 876 } 877 } 878 ``` 879 880 **Code (Python)** 881 882 ``` 883 import sys, random 884 885 print = sys.stdout.write 886 input = sys.stdin.readline 887 888 def query(a, b, c): 889 print("? " + str(a+1) + " " + str(b+1) + " " + str(c+1) + "\n") 890 sys.stdout.flush() 891 return int(input()) 892 893 def answer(): 894 print("! " + " ".join([str(i) for i in ans]) + "\n") 895 sys.stdout.flush() 896 return int(input()) 897 898 T = int(input()) 899 testVal = 13 900 901 randomQueryOrder = [] 902 for i in range(testVal): 903 for j in range(i+1, testVal): 904 for k in range(j+1, testVal): 905 randomQueryOrder.append((i, j, k)) 906 907 for caseno in range(T): 908 N = int(input()) 909 910 a = -1 911 b = -1 912 913 ans = [0 for i in range(N)] 914 res = [0 for i in range(N)] 915 order = [i for i in range(N)] 916 917 minVal = N+5 918 919 random.shuffle(order) 920 random.shuffle(randomQueryOrder) 921 for ijk in randomQueryOrder: 922 i, j, k = ijk 923 i = order[i] 924 j = order[j] 925 k = order[k] 926 temp = query(i, j, k) 927 928 if temp <= (N-4)//6: 929 a = i 930 b = j 931 break 932 933 assert(a != -1 and b != -1) 934 935 ''' Now, the key thing to note is that abs(P[a]-P[b]) is less than (roughly speaking) N/3. 936 Observe that the index c such that query(a, b, c) is maximum must be such that P[c] == 1 or P[c] == N (some steps skipped). 937 But given the condition P[1] < P[2], we can assume either, then flip using P[i] = N+1-P[i] if condition not satisfied. 938 ''' 939 940 # Now, we assume P[c] = 1 941 # There always exists another index d such that query(a, b, d) = query(a, b, c)-1 and P[d] = 2 942 # There can be only at most 2 d which satisfy the former, and we can check which is which by comparing query(a, c, d) 943 944 maxVal = -1 945 c = -1 946 for i in range(N): 947 if a == i or b == i: 948 continue 949 950 res[i] = query(a, b, i) 951 if res[i] > maxVal: 952 maxVal = res[i] 953 c = i 954 955 d2 = [] 956 for i in range(N): 957 if a == i or b == i: 958 continue 959 960 if res[i] == maxVal-1: 961 d2.append(i) 962 963 d = -1 964 if len(d2) == 1: 965 d = d2[0] 966 elif len(d2) == 2: 967 temp1 = query(a, c, d2[0]) 968 temp2 = query(a, c, d2[1]) 969 if temp1 < temp2: 970 d = d2[0] 971 else: 972 d = d2[1] 973 else: 974 assert(False) 975 976 # After finding indices c and d such P[c] = 1 and P[d] = 2, we can now find the rest of the values 977 ans[c] = 1 978 ans[d] = 2 979 for i in range(N): 980 if i == c or i == d: 981 continue 982 ans[i] = 2 + query(c, d, i) 983 984 # Flip since P[1] < P[2] not satisfied 985 if ans[0] >= ans[1]: 986 for i in range(N): 987 ans[i] = N+1-ans[i] 988 989 result = answer() 990 991 # I dislike getting WA, hence I make my code MLE 992 if result != 1: 993 MLE = [1 for i in range(1<<27)] 994 sys.stdout.write(MLE[0]) 995 ``` 996 997 ## Code Golf 998 999 You may have realized that python codes in the editorial are quite short. We actually had a code golf challenge among testers. You are invited to try code golf our problems and put them in the comments. Maybe I will put the shortest codes in the editorial ;) 1000 1001 Rules for code golf: 1002 1003 * any language allowed 1004 * codes will be judged by number of characters 1005 * must get AC in the respective problems