codeforces-scrape

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

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