1975.md (43659B)
1 Source: https://codeforces.com/blog/entry/129801 2 3 [1975A - Bazoka and Mocha's Array](/contest/1975/problem/A) 4 5 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") 6 7 **Hint 1** 8 9 We can't do any insertions by the operation. 10 11 **Hint 2** 12 13 If the answer is yes, we can make $a$ become non-decreasing in no more than one operation. 14 15 **Solution** 16 17 Read the hints. 18 19 If $a$ is non-decreasing initially, the answer is yes. 20 21 If $a$ isn't non-decreasing initially, we can find the smallest $i$ such that $a_i \gt a_{i+1}$. Then we choose $x=[a_1,a_2,...,a_i]$ and $y=[a_{i+1},a_{i+2},...,a_n]$. If the array $y+x$ is non-decreasing, the answer is yes. Otherwise, the answer is no. 22 23 **Code** 24 25 ``` 26 #include<bits/stdc++.h> 27 using namespace std; 28 const int N = 1e5+10; 29 int a[N]; 30 int main(){ 31 int t; 32 cin>>t; 33 while(t--){ 34 int n; 35 cin>>n; 36 for(int i=1;i<=n;i++){ 37 cin>>a[i]; 38 } 39 int pos=0; 40 for(int i=1;i<n;i++){ 41 if(a[i]>a[i+1]){ 42 pos=i; 43 break; 44 } 45 } 46 if(!pos)cout<<"Yes\n"; 47 else{ 48 int fl=0; 49 for(int i=pos+1;i<=n;i++){ 50 int j=(i%n)+1; 51 if(a[i]>a[j])fl=1; 52 } 53 if(!fl)cout<<"Yes\n"; 54 else cout<<"No\n"; 55 } 56 } 57 } 58 ``` 59 60 [1975B - 378QAQ and Mocha's Array](/contest/1975/problem/B) 61 62 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") 63 64 **Hint 1** 65 66 How to solve the problem if we only need to find a number $i$($1\leq i\leq n$) such that $a_k$ is divisible by $a_i$ for all $k$($1\leq k\leq n$)? 67 68 **Hint 2** 69 70 We only need to check whether all elements are divisible by the minimum element of the array. 71 72 **Solution** 73 74 Read the hints. 75 76 Suppose the minimum element of $a$ is $x$. Then we iterate over $a$, if an element is not divisible by $x$, then we add it to $b$ ($b$ is initially empty). 77 78 If $b$ is still empty after iterating $a$, the answer is yes. 79 80 If $b$ isn't empty, we check whether all elements of $b$ are divisible by the minimum element of $b$. If so, the answer is yes. Otherwise, the answer is no. 81 82 **Code** 83 84 ``` 85 #include<bits/stdc++.h> 86 using namespace std; 87 #define ll long long 88 const int N = 1e5+10; 89 int a[N]; 90 int main(){ 91 int t; 92 cin>>t; 93 while(t--){ 94 int n; 95 cin>>n; 96 int fl=0; 97 for(int i=1;i<=n;i++){ 98 cin>>a[i]; 99 if(a[i]==1)fl=1; 100 } 101 if(fl)cout<<"Yes\n"; 102 else{ 103 sort(a+1,a+1+n); 104 vector<int> b; 105 for(int i=2;i<=n;i++){ 106 if(a[i]%a[1])b.push_back(a[i]); 107 } 108 sort(b.begin(),b.end()); 109 n = b.size(); 110 for(int j=1;j<n;j++){ 111 if(b[j]%b[0]){ 112 fl=1; 113 break; 114 } 115 } 116 if(!fl)cout<<"Yes\n"; 117 else cout<<"No\n"; 118 } 119 120 } 121 } 122 ``` 123 124 [1975C - Chamo and Mocha's Array](/contest/1975/problem/C) 125 126 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") 127 128 **Hint 1** 129 130 If a subarray of length at least $2$ contains only the same elements, we can change all elements of the array to that element by operations. 131 132 **Hint 2** 133 134 Suppose the answer is $x$, we can perform no more than one operation on the original array $a$ so that there is a subarray of length at least $2$ that contains only $x$. 135 136 **Hint 3** 137 138 If we can make all elements of a subarray become $x$ in one operation, then there must be a subarray of length $3$ with a median of $y$ ($y\geq x$). 139 140 **Solution** 141 142 Read the hints. 143 144 If $n=2$, the answer is the minimum element. 145 146 If $n\geq 3$, we iterate over all subarrays of length $3$, and the answer is the maximum value of the median of all subarrays of length $3$. 147 148 **Code** 149 150 ``` 151 #include<bits/stdc++.h> 152 using namespace std; 153 const int N = 1e5+10; 154 int a[N]; 155 int main(){ 156 int n,t; 157 cin>>t; 158 while(t--){ 159 cin>>n; 160 for(int i=1;i<=n;i++) 161 cin>>a[i]; 162 if(n==2)cout<<min(a[1],a[2])<<"\n"; 163 else{ 164 int ans = min(a[1],a[2]); 165 for(int i=1;i<=n-2;i++){ 166 vector<int> tmp; 167 for(int k=0;k<=2;k++) 168 tmp.push_back(a[i+k]); 169 sort(tmp.begin(),tmp.end()); 170 ans = max(ans,tmp[1]); 171 } 172 cout<<ans<<"\n"; 173 } 174 } 175 } 176 ``` 177 178 [1975D - Paint the Tree](/contest/1975/problem/D) 179 180 Idea: [SanweiTreap](/profile/SanweiTreap "Grandmaster SanweiTreap") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") 181 182 **Hint 1** 183 184 If two pieces overlap at the beginning, can you solve the problem? 185 186 **Hint 2** 187 188 Consider the first time a vertex is painted blue. After this event occurs, what happens next? 189 190 **Solution** 191 192 Read the hints. 193 194 In subsequent movements after the first time a vertex is painted blue, we can ignore the process of painting vertices red and then painting them blue. 195 196 We call the first vertex painted blue $r$. Then it is not difficult to find that $P_A$ arrived at this vertex earlier than $P_B$. Considering all subsequent movements of $P_B$, $P_A$ can restore these movements one by one after reaching $r$, then $P_B$ will pass through all vertices have been painted red. 197 198 If we know which vertex is $r$, this will be a classic problem, assuming the distance between the farthest vertex on the tree from $r$ and $r$ is $d$, then the answer is $2(n-1)-d$. Then we consider the strategies of $P_A$ and $P_B$ at this time. The two must be close to each other, and then until the first vertex is painted blue. If another vertex is $r$, although the value of $d$ may increase, every time the value of $d$ increases by $1$, the time when $P_A$ and $P_B$ meet will also increase by at least $1$, so the answer will not decrease. 199 200 **Code** 201 202 ``` 203 #include<bits/stdc++.h> 204 using namespace std; 205 #define ll long long 206 const int N = 2e5+10; 207 vector<int> g[N]; 208 int dep[N],f[N],mx,n,a,b; 209 void dfs(int x,int fa){ 210 dep[x]=dep[fa]+1; 211 mx = max(mx,dep[x]); 212 f[x]=fa; 213 for(auto i:g[x]){ 214 if(i==fa)continue; 215 dfs(i,x); 216 } 217 } 218 vector<int> move(int x,int y){ 219 if (dep[x] > dep[y]) swap(x, y); 220 vector<int> track,ano; 221 int tmp = dep[y] - dep[x], ans = 0; 222 track.push_back(y); 223 while(tmp--){ 224 y = f[y]; 225 track.push_back(y); 226 } 227 if (y == x) return track; 228 ano.push_back(x); 229 while (f[x] != f[y]) { 230 x = f[x]; 231 y = f[y]; 232 ano.push_back(x); 233 track.push_back(y); 234 } 235 track.push_back(f[y]); 236 reverse(ano.begin(),ano.end()); 237 for(auto i:ano)track.push_back(i); 238 return track; 239 } 240 int main(){ 241 int t; 242 cin>>t; 243 dep[0]=-1; 244 while(t--){ 245 mx = -1; 246 cin>>n; 247 for(int i=1;i<=n;i++)g[i].clear(); 248 cin>>a>>b; 249 for(int i=1;i<n;i++){ 250 int u,v; 251 cin>>u>>v; 252 g[u].push_back(v); 253 g[v].push_back(u); 254 } 255 if(a==b){ 256 dfs(a,0); 257 cout<<2*(n-1)-mx<<"\n"; 258 continue; 259 } 260 dfs(1,0); 261 auto tr = move(a,b); 262 int m = tr.size(); 263 if(tr[0]!=a)reverse(tr.begin(),tr.end()); 264 int x = tr[(m-1)/2]; 265 mx = -1; 266 dfs(x,0); 267 cout<<2*(n-1)-mx+(m-1-(m-1)/2)<<"\n"; 268 } 269 } 270 ``` 271 272 [1975E - Chain Queries](/contest/1975/problem/E) 273 274 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Serval](/profile/Serval "Grandmaster Serval") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") 275 276 **Hint 1** 277 278 Suppose the tree is a rooted tree, we only need to care about the number of black child vertices of each vertex. 279 280 **Hint 2** 281 282 If the black vertices form a chain, there is no black vertex that has three or more black child vertices. And there is at most one black vertex that has two black child vertices. 283 284 **Hint 3** 285 286 If the black vertices form a chain, there is at most one black vertex whose parent vertex is white. 287 288 **Solution** 289 290 Read the hints. 291 292 We can maintain the number of black vertices with $0/1/2/3+$ black child vertices in $O(1)$. When we flip the color of one vertex, only it and its parent node are affected. 293 294 If the black vertices form a chain: - no black vertex that has three or more black child vertices and there is at most one black vertex that has two black child vertices. - there is at most one black vertex whose parent vertex is white. - if there is one black vertex that has two black child vertices, its parent vertex must be white. 295 296 **Code** 297 298 ``` 299 #include<bits/stdc++.h> 300 using namespace std; 301 const int N = 1e6+10; 302 303 int f[N]; 304 vector<int> g[N]; 305 int col[N],num[N]; 306 int faw,sum_two,sum_more,tot_black,xor_two; 307 int n; 308 void init(){ 309 sum_two=0; 310 tot_black=0; 311 sum_more=0; 312 faw=0; 313 xor_two=0; 314 for(int i=1;i<=n;i++){ 315 g[i].clear(); 316 num[i]=0; 317 } 318 } 319 320 void dfs(int x,int fa){ 321 f[x]=fa; 322 if(col[x]==1)tot_black++; 323 int sum=0; 324 for(auto i:g[x]){ 325 if(i==fa)continue; 326 dfs(i,x); 327 if(col[i]==1)sum++; 328 } 329 if(col[fa]==0&&col[x]==1)faw++; 330 if(col[x]==1){ 331 if(sum==2)sum_two++,xor_two^=x; 332 if(sum>2)sum_more++; 333 } 334 num[x]=sum; 335 } 336 337 void flip(int x){ 338 col[x]^=1; 339 int d = col[x]==1?1:-1; 340 tot_black+=d; 341 if(col[f[x]]==0)faw+=d; 342 if(num[x]==2)sum_two+=d,xor_two^=x; 343 if(num[x]>2)sum_more+=d; 344 faw-=d*num[x]; 345 if(col[x]==1){ 346 if(col[f[x]]==1&&num[f[x]]==2)sum_two--,sum_more++,xor_two^=f[x]; 347 num[f[x]]++; 348 if(col[f[x]]==1&&num[f[x]]==2)sum_two++,xor_two^=f[x]; 349 }else{ 350 if(col[f[x]]==1&&num[f[x]]==2)sum_two--,xor_two^=f[x]; 351 num[f[x]]--; 352 if(col[f[x]]==1&&num[f[x]]==2){ 353 sum_two++; 354 sum_more--; 355 xor_two^=f[x]; 356 } 357 } 358 } 359 360 bool check(){ 361 if(!tot_black)return false; 362 if(sum_more||sum_two>1)return false; 363 if(faw>1)return false; 364 if(sum_two&&col[f[xor_two]]==1)return false; 365 return true; 366 } 367 368 int main(){ 369 int t; 370 scanf("%d",&t); 371 while(t--){ 372 init(); 373 int q; 374 scanf("%d %d",&n,&q); 375 for(int i=1;i<=n;i++) cin>>col[i]; 376 for(int i=1;i<n;i++){ 377 int u,v; 378 scanf("%d %d",&u,&v); 379 g[u].push_back(v); 380 g[v].push_back(u); 381 } 382 dfs(1,0); 383 while(q--){ 384 int x; 385 scanf("%d",&x); 386 flip(x); 387 if(check()) printf("Yes\n"); 388 else printf("No\n"); 389 } 390 } 391 } 392 ``` 393 394 [1975F - Set](/contest/1975/problem/F) 395 396 Idea: [Toxel](/profile/Toxel "International Grandmaster Toxel") Solution: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn"), [Toxel](/profile/Toxel "International Grandmaster Toxel") Prepared by: [Nerovix](/profile/Nerovix "International Master Nerovix") 397 398 **Hint 1** 399 400 Consider enumerating each number from $0$ to $n-1$ whether it is contained by $S$, when we have enumerated the first $x$ numbers, there are only $2^{n-x}$ constraints. 401 402 **Solution** 403 404 Read the hints. 405 406 Consider enumerating each number from $0$ to $n-1$ whether it is contained by $S$. Suppose that the current enumeration reaches $i$, and in the remaining constraints, $T_1$ and $T_2$ are two sets, the only difference between them is whether they contain $i$ ($T_1$ contains $i$): 407 408 * $S$ contains $i$. We can merge $T_1$ and $T_2$ into a new constraint $T'$ and $v_{T'}=(v_{T_1}»1)$&$v_{T_2}$. 409 * $S$ doesn't contain $i$. We can merge $T_1$ and $T_2$ into a new constraint $T'$ and $v_{T'}=v_{T_1}$&$v_{T_2}$. 410 411 We can merge constraints quickly when the enumeration reaches a new number. And the time complexity is $O(n\cdot 2^n)$ 412 413 **Code** 414 415 ``` 416 #include<bits/stdc++.h> 417 418 using namespace std; 419 420 const int N = 24, S = (1 << 20) + 5; 421 int n = 0, f[N][S] = {}; 422 vector<int> ans; 423 424 inline void dfs(int s = 0, int i = 0){ 425 if(i < n){ 426 int m = 1 << (n - i - 1); 427 for(int t = 0 ; t < m ; t ++) f[i + 1][t] = f[i][t] & f[i][m | t]; 428 dfs(s << 1, i + 1); 429 for(int t = 0 ; t < m ; t ++) f[i + 1][t] = f[i][t] & (f[i][m | t] >> 1); 430 dfs(s << 1 | 1, i + 1); 431 } 432 else if(f[n][0] & 1) ans.push_back(s); 433 } 434 435 int main(){ 436 scanf("%d", &n); 437 f[0][0] = 1; 438 for(int s = 1 ; s < 1 << n ; s ++) scanf("%d", &f[0][s]); 439 dfs(); 440 printf("%d\n", int(ans.size())); 441 for(int s : ans) printf("%d\n", s); 442 return 0; 443 } 444 ``` 445 446 [1975G - Zimpha Fan Club](/contest/1975/problem/G) 447 448 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish"), [zimpha](/profile/zimpha "Grandmaster zimpha") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish"), [errorgorn](/profile/errorgorn "International Grandmaster errorgorn"), [MagicalFlower](/profile/MagicalFlower "International Grandmaster MagicalFlower") 449 450 **Hint 1** 451 452 If $s, t$ both have $*$, or both don't have $*$, then it will be a simple problem. Can you try to solve this problem? 453 454 **Hint 2** 455 456 According to the first hint, we have discussed two cases. In the remaining cases, without loss of generality, we think that only $t$ has $*$. Suppose we write $t$ as $t'_0*t'_1*t'_2* \dots*t'_k$. Where $t'_i$ does not take $*$, assuming that $|t'_i| \leq 50$ is satisfied for all $i$, can you solve this problem? 457 458 **Hint 3** 459 460 There is a strictly subproblem of this problem, namely, given two strings $s$ and $t$ consisting only of characters from $a$ to $z$ and $-$, you need to find all positions in $s$ where $t$ can be matched. 461 462 This problem has a classic solution, where $-$ is set to $0$, and $a$ to $z$ are sequentially assigned values from $1$ to $26$, and then let $f_i = \sum_{j=1}^m [s_{i +j-1} \gt 0] \times [t_j \gt 0] (s_{i+j-1}-t_j)^2$, then all positions of $f_i = 0$ satisfy $s[i, i + m -1]$ can match $t$. 463 464 Decompose the calculation formula, $f_i = \sum_{j=1}^m s_{i+j-1}^2+s_j^2 - 2\sum_{j=1}^m s_{i+j -1}{t_j} - \sum_{j=1}^m [s_{i+j-1} = 0] t_j^2 - \sum_{j=1}^m s_{i+j-1}^ 2[t_j=0]$. For $\sum_{j=1}^m s_{i+j-1}^2+s_j^2$, you can prefix and process it, and for the remaining part, you can use FFT in $O(n \log n )$ to be resolved. 465 466 What is the use of this solution in the original problem? 467 468 **Solution** 469 470 Read the hints. 471 472 In the following, we consider $n, m$ to be of the same order. 473 474 Consider the case where $s$ and $t$ do not contain $*$. We only need to be compared bit by bit. 475 476 Consider the case where $s, t$ both contain $*$, if the beginning of $s$ is not $*$ or the beginning of $t$ is not $*$: 477 478 * If one of the first characters of $s$ and $t$ is $*$ or the first characters can match, delete the first characters of the two strings that are not $*$. 479 * Oherwise the answer is obviously `No`. 480 481 Performing the same operation on the last characters, it is not difficult to find that it will be reduced to two strings $*s’$ and $t'*$, where $s'$ and $t'$ are arbitrary strings. Then it is not difficult to find that $t's'$ matches two strings at the same time. Therefore, as long as the head and tail can be successfully deleted, the answer must be `Yes`. 482 483 Consider the hardest case. Without loss of generality, we assume that only $t$ contains $*$, otherwise $s, t$ can be exchanged. We still delete the beginning and the end first. It is not difficult to find that thereafter $t$ can be written as $*t'_1*t'_2*\dots*t'_k *$. 484 485 Then we will have a greedy solution. We iterate $i$ from $1$ to $n$, find the first matching position of $t'_i$ in $s$ each time, and delete tthese matching characters and all preceding characters in $s$, that is, remove a prefix of $s$, and then until all matching is completed or no matching position is found in $s$. 486 487 Assume that we use FFT to brute force solve this problem every time. See Hint.3 for the specific solution, then the complexity is $O(nk \log n)$. 488 489 But it is not difficult to find that this is very wasteful. In fact, we can do this: 490 491 * When matching $t'_i$, only take out the first $|2t'_i|$ characters of $s$ each time and try to match $t'_i$. Because if the match is successful, then since all positions matching $t'_i$ are deleted, it is not difficult to find that at least $|t'_i|$ characters are deleted. And if the match fails, it is not difficult to find that the first $|t'_i|$ characters of $s$ will no longer be useful and can also be deleted. Therefore we remove at least the first $|t'_i|$ characters in $s$ in complexity $O(|t'_i| \log |t'_i|)$. 492 493 Since the total length of $s$ is $n$, the total time complexity does not exceed $O(n \log n)$. 494 495 **Code** 496 497 ``` 498 #include<bits/stdc++.h> 499 500 using namespace std; 501 typedef long long ll; 502 503 const ll N = (1 << 22) + 5, Mod = 2013265921, G = 31; 504 505 inline ll power(ll x, ll y){ 506 ll ret = 1; 507 while(y){ 508 if(y & 1) ret = ret * x % Mod; 509 x = x * x % Mod, y >>= 1; 510 } 511 return ret; 512 } 513 514 ll p[N] = {}, w[N] = {}, g[N] = {}, iv[N] = {}; 515 516 inline void dft(ll n, ll a[], bool idft){ 517 for(ll i = 0 ; i < n ; i ++) if(i < p[i]) swap(a[i], a[p[i]]); 518 for(ll m = 1 ; m < n ; m <<= 1) for(ll j = 0, k = 0 ; j < n ; j += m << 1, k ++) for(ll i = j ; i < j + m ; i ++){ 519 ll x = a[i], y = a[i + m]; 520 a[i] = x + y, a[i] >= Mod && (a[i] -= Mod); 521 a[i + m] = (x - y + Mod) * w[k] % Mod; 522 } 523 if(!idft) return; 524 reverse(a + 1, a + n); 525 for(int i = 0 ; i < n ; i ++) a[i] = a[i] * iv[n] % Mod; 526 } 527 528 inline ll sqr(ll x){ 529 return x * x; 530 } 531 532 ll n = 0, m = 0, a[3][N] = {}, b[3][N] = {}, c[N] = {}, d[N] = {}; 533 char s[N] = {}, t[N] = {}; 534 535 inline ll work(ll L, ll R, ll l, ll r){ 536 ll M = 1; while(M < R - L + r - l) M <<= 1; 537 w[0] = 1; 538 for(ll k = 1 ; k < M ; k <<= 1){ 539 ll bit = M / 2 / k; 540 if(k == M / 2) for(ll i = 0; i < k ; i ++) p[i + k] = p[i] | bit; 541 else for(ll i = 0 ; i < k ; i ++){ 542 w[i + k] = w[i] * g[k] % Mod; 543 p[i + k] = p[i] | bit; 544 } 545 } 546 for(ll i = 0 ; i < M ; i ++){ 547 p[i] = p[i >> 1] >> 1; 548 if(i & 1) p[i] |= M >> 1; 549 } 550 ll z = 0; 551 for(ll i = 0 ; i < M ; i ++){ 552 c[i] = 0; 553 for(ll f = 0 ; f < 3 ; f ++) a[f][i] = b[f][i] = 0; 554 } 555 for(ll i = L ; i < R ; i ++){ 556 ll x = (s[i] == '-') ? 0 : (s[i] - 'a' + 1); 557 a[0][i - L] = x ? 0 : 1, a[1][i - L] = 2 * x, a[2][i - L] = sqr(x), d[i] = sqr(x); 558 } 559 d[R] = 0; 560 for(ll i = l ; i < r ; i ++){ 561 ll x = (t[i] == '-') ? 0 : (t[i] - 'a' + 1); 562 b[0][r - i] = sqr(x), b[1][r - i] = x, b[2][r - i] = x ? 0 : 1, z += sqr(x); 563 } 564 for(ll f = 0 ; f < 3 ; f ++){ 565 dft(M, a[f], 0), dft(M, b[f], 0); 566 for(ll i = 0 ; i < M ; i ++) c[i] = (c[i] + a[f][i] * b[f][i]) % Mod; 567 } 568 dft(M, c, 1); 569 for(ll i = 0 ; i < r - l ; i ++) z += d[i + L]; 570 for(ll i = L ; i <= R - (r - l) ; z -= d[i], z += d[i + (r - l)], i ++) if(z % Mod == c[i - L + r - l]) return i; 571 return -1; 572 } 573 574 int main(){ 575 for(ll i = 1 ; i < N ; i <<= 1) g[i] = power(G, Mod / 4 / i), iv[i] = power(i, Mod - 2); 576 scanf("%lld %lld", &n, &m); 577 scanf("%s %s", s, t); 578 while(n && m && s[n - 1] != '*' && t[m - 1] != '*'){ 579 if(s[n - 1] != t[m - 1] && s[n - 1] != '-' && t[m - 1] != '-'){ 580 printf("No"); 581 return 0; 582 } 583 else n --, m --; 584 } 585 reverse(s, s + n), reverse(t, t + m); 586 while(n && m && s[n - 1] != '*' && t[m - 1] != '*'){ 587 if(s[n - 1] != t[m - 1] && s[n - 1] != '-' && t[m - 1] != '-'){ 588 printf("No"); 589 return 0; 590 } 591 else n --, m --; 592 } 593 reverse(s, s + n), reverse(t, t + m); 594 if(min(n, m) == 0){ 595 while(n && s[n - 1] == '*') n --; 596 while(m && t[m - 1] == '*') m --; 597 if(max(n, m) == 0) printf("Yes"); 598 else printf("No"); 599 return 0; 600 } 601 bool u = 0, v = 0; 602 for(ll i = 0 ; i < n ; i ++) if(s[i] == '*') u = 1; 603 for(ll i = 0 ; i < m ; i ++) if(t[i] == '*') v = 1; 604 if(u){ 605 if(v){ 606 printf("Yes"); 607 return 0; 608 } 609 else swap(n, m), swap(s, t); 610 } 611 ll L = 0, R = 0; 612 for(ll l = 1, r = l ; l < m ; l = r + 1, r = l){ 613 while(t[r] != '*') r ++; 614 if(r - l) while(1){ 615 R = min(n, L + 2 * (r - l)); 616 if(R - L < r - l){ 617 printf("No"); 618 return 0; 619 } 620 ll h = work(L, R, l, r); 621 if(h == -1) L = R - (r - l) + 1; 622 else{ 623 L = h + r - l; 624 break; 625 } 626 } 627 } 628 printf("Yes"); 629 return 0; 630 } 631 ``` 632 633 [1975H - 378QAQ and Core](/contest/1975/problem/H) 634 635 Idea: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") Solution: [Toxel](/profile/Toxel "International Grandmaster Toxel") Prepared by: [Bazoka13](/profile/Bazoka13 "Master Bazoka13") 636 637 **Solution** 638 639 Consider the maximum character $m$ of the string $s$. 640 641 If $m$ only appears once, then obviously the string starting with it is the largest in lexicographical order. To make it the smallest, $m$ should be arranged at the end. Other characters can be arranged arbitrarily. 642 643 If $m$ appears more than twice, it can be proven that the beginning and end of the answer string must be $m$. If the beginning of the string is not $m$, moving the character at the beginning to somewhere before a non-first $m$ can make the suffix lexicographical order starting with this $m$ smaller, while the suffix lexicographical order starting with $m$ after this remains unchanged. For suffixes that do not start with $m$, they are definitely not the largest, so they do not need to be considered. If the end of the string is not $m$, first remove it, and all suffix lexicographical orders become smaller. Similarly, it can also be placed in front of a certain $m$ to reduce the lexicographical order. 644 645 In this case, the answer is always in the form of $ms_{1}ms_{2}m\dots ms_{t}m$. Where $s_{1},s_{2},\dots,s_{t}$ contain characters that are less than $m$, it could also be an empty string. Now suppose that the set ${s_{1},s_{2},\dots,s_{t}}$ is determined, and consider how to arrange their order. Suppose we are currently comparing two suffixes $S_{i}=ms_{i}m\dots ms_{t}m$ and $S_{j}=ms_{j}m\dots ms_{t}m$, and suppose $s_{i+k}$ and $s_{j+k}$ are the first two substrings that appear differently. Then $ms_{i}m\dots ms_{i+k-1}$ and $ms_{j}m\dots ms_{j+k-1}$ must be equal, and the size relationship between $S_{i}$ and $S_{j}$ is the same as the size relationship between $ms_{i+k}$ and $ms_{j+k}$. In this way, all $ms_{i}$ can be sorted according to lexicographical order, and regarded as a new character, and Solving the original problem for $(ms1)(ms_2)…(ms_t)$ is sufficient. 646 647 Now consider how to determine the set ${s_{1},s_{2},\dots,s_{t}}$. For a certain $s_{i}$, it should obviously be ordered, because this can make $ms_{i}$ smaller. There is also another property. Suppose there are $s_{i}=p_{i}c$ and $s_{j}$ such that $ms_{j}$ is the current lexicographically largest string, and $mp_{i} \lt ms_{j}$, where $c$ is a character less than $m$. Putting $c$ after $s_{j}$ can make the answer smaller. 648 649 The proof of the property is as follows. Without loss of generality, let $f_{1}=p_{i}c$, $f_{2}=p_{i}$, $f_{3}=s_{j}c$, $f_{4}=s_{j}$, then we have $mf_{2} \lt mf_{1} \lt mf_{4}$ and $f_{3}m \lt f_{4}m$. Consider the subproblem after iteration, by definition, $f_{4}$ is the largest character in the problem. If $f_{1}$ and $f_{4}$ are used, and there is an $f_{4}$ to the left of some $f_{1}$ in the optimal solution string, then replacing this $f_{1}$ and its nearest $f_{4}$ on the left with $f_{2}$ and $f_{3}$ respectively, it is easy to prove that the largest suffix will definitely become smaller or unchanged. Otherwise, all $f_{1}$ are to the left of all $f_{4}$, at this time you can arbitrarily replace some $f_{1}$ and $f_{4}$ with $f_{2}$ and $f_{3}$ respectively, it is easy to prove that the largest suffix still becomes smaller or unchanged. 650 651 Based on the above discussion, we can now give the final greedy algorithm for the problem. Suppose the largest character $m$ has $t+1$ occurrences. If $t=0$, then put the only $m$ at the end, and the other characters can be arranged arbitrarily. Otherwise, suppose there are $p$ characters less than $m$, if $p\le t$, it can be proved that there is at most one character between any two $m$. Consider $|s_{i}|\ge2$, $s_{j}=\varepsilon$ (empty string), then they meet the above properties, and it is more optimal to exchange the last character of $s_{i}$ to $s_{j}$. Therefore, $s_{1},\dots,s_{p}$ is a single character, $s_{p+1}=\dots=s_{t}=\varepsilon$, and recursively solve the subproblem. Note that to ensure time complexity, when $t\gg p$, multiple rounds of recursion need to be combined. 652 653 If $p \gt t$, it can be similarly proved that there will not be an $s_{i}$ that is an empty string. In addition, consider the first character of all $s_{i}$, for those among these $t$ characters that are not the largest, using the same property, it can be proved that the length of the string they are in must be $1$, and no other characters will follow. Also, since $s_{i}$ is ordered, it can be proved that the first character of all $s_{i}$ must be the smallest $t$ characters less than $m$. Next, the remaining characters will only be filled after those largest characters among these $t$ characters, and it can be similarly proved that those filled in the second position of these strings are also the smallest among the remaining characters, and so on, until all characters are used up. 654 655 Notice that the complexity of each recursion is linear, and each recursion at least halves the number of characters, so the total complexity is $O(n\log n)$. 656 657 **Bonus** 658 659 How to solve this problem in $O(n)$? 660 661 **Code** 662 663 ``` 664 #include<bits/stdc++.h> 665 using namespace std; 666 struct ch{ 667 string c; 668 ch(){c = "";} 669 ch(string cc){c=cc;} 670 bool operator == (const ch& p)const{ 671 return c==p.c; 672 } 673 bool operator != (const ch& p)const{ 674 return c!=p.c; 675 } 676 void add(ch& p){ 677 c.append(p.c); 678 } 679 }; 680 vector<ch> solve(vector<ch> cs){ 681 int n = cs.size(); 682 int t = 0; 683 if(cs.empty())return cs; 684 for(int i=n-2;i>=0;i--){ 685 if(cs[i]!=cs[n-1])break; 686 t++; 687 } 688 if(t==0){ 689 vector<ch> res; 690 res.push_back(cs[n-1]); 691 return res; 692 } 693 int p = n-(t+1); 694 if(p<=t){ 695 vector<ch> res; 696 vector<ch> nxt; 697 int k = (t+1)/(p+1); 698 int le = (t+1)%(p+1); 699 ch m = cs[n-1]; 700 for(int j=1;j<k;j++){ 701 m.add(cs[n-1]); 702 } 703 for(int i=0;i<p;i++){ 704 ch tmp = m; 705 tmp.add(cs[i]); 706 nxt.push_back(tmp); 707 } 708 for(int i=0;i<le;i++){ 709 nxt.push_back(cs[n-1]); 710 } 711 auto nxt_solved = solve(nxt); 712 for(auto i:nxt_solved)res.push_back(i); 713 res.push_back(m); 714 return res; 715 }else{ 716 vector<ch> res; 717 vector<ch> nxt; 718 ch m = cs[n-1]; 719 for(int i=0;i<t;i++){ 720 nxt.push_back(m); 721 } 722 int now = 0,beg=0; 723 for(int i=0;i<p;i++){ 724 nxt[now].add(cs[i]); 725 if(now>=1){ 726 if(cs[i]!=cs[i-1]){ 727 beg=now; 728 } 729 } 730 now++; 731 if(now>=t)now=beg; 732 } 733 auto nxt_solved = solve(nxt); 734 for(auto i:nxt_solved)res.push_back(i); 735 res.push_back(m); 736 return res; 737 } 738 } 739 vector<ch> trans(string s){ 740 vector<ch> tmp; 741 for(auto i:s){ 742 string tmpp = ""; 743 tmpp+=i; 744 tmp.push_back(tmpp); 745 } 746 return tmp; 747 } 748 int main(){ 749 int t; 750 cin>>t; 751 while(t--){ 752 int n; 753 cin>>n; 754 string s; 755 cin>>s; 756 sort(s.begin(),s.end()); 757 auto tmp = trans(s); 758 auto ans= solve(tmp); 759 for(auto c:ans)cout<<c.c; 760 cout<<"\n"; 761 } 762 } 763 ``` 764 765 [1975I - Mind Bloom](/contest/1975/problem/I) 766 767 Idea: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Solution: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish") Prepared by: [Gellyfish](/profile/Gellyfish "Grandmaster Gellyfish"), [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 768 769 **Hint 0** 770 771 Play "Slay the Spire". Unfortunately, it doesn't help much. 772 773 **Hint 1** 774 775 It may be helpful to calculate the probability that your hand becomes empty instead of the probability that the draw pile becomes empty. 776 777 **Hint 2** 778 779 The intended solution is a $O(n^5)$ DP. The constant factor is small enough to run. 780 781 **Solution** 782 783 If all the cards in your hand is $0$, you immediately lose. Therefore, we only need to consider whether we can empty our hand by playing cards with non-$0$ value. 784 785 Consider a sequence of playing cards that will lead to use losing. The sum over the probabilities of all these losing sequences is the probability of us losing. 786 787 To simplify the process, we will consider drawing $x$ random cards from the deck as drawing a random card from the deck $x$ times. 788 789 Consider a sequence of played cards as $z_1, z_2, \ldots, z_k$ where $z_i$ is the index of the card played. Consider how $z_i$ was drawn into our hand. It is not hard to see that either: 790 791 * $z_i$ was in our hand at the start 792 * $z_i$ from drawn from card $a_j$ where $j$ is the maximum index such that $z_j \leq z_i$ and $j \lt i$. 793 794 From our previous observation, we can motivate the following range DP. Let $f(i,0/1,u,p,x)$ denote the a sequence of played cards with the following: 795 796 * the minimum index of a card we played is $i$ 797 * whether there are any cards with value greater than $i$ that is one of the cards that were in our hand in the start 798 * before we played this sequence, we played a card of value $u$ 799 * before we played this sequence, the deck has $p$ cards 800 * The **net** number of cards that we draw is $x$ 801 802 We will use $g(i,0/1,u,p,x)$ to help us transition quickly. It is defined as the suffix sum (on dimension $i$) of $f$. 803 804 Consider transitioning based on the card of index $i$. 805 806 We have the following transition for $f(*,0,*,*,*)$: 807 808 * $f(i, 0, u, p, x) = \sum_{y=0}^{x-(c_i-1)} g(i+1, 0, u, p, y) \times g(i, 0, c_i, p - (c_i - 1) - y, x - (c_i - 1) - y) \times \frac {u+y} {(p-y+1)^{\underline c_i}}$ 809 * $g(i, 0, u, p, x) = g(i+1, 0, u, p, x) + f(i, 0, u, p, x)$ 810 811 For $f(*,1,*,*,*)$, To handle the fact that there are some cards that are initially in our hands, let $h$ denote the the number of $j \gt i$ such that $s_j=1$. 812 813 If $s_i = 1$, we have the following transitions: 814 815 * $f(i, 1, u, p, x) = \sum_{y=h}^{x-c_i} g(i+1, 1, u, p, y) \times g(i, 0, c_i, p - (c_i - 1) - y+h, x - c_i - y) \times \frac {1} {(p-y+1+h)^{\underline c_i}}$ 816 * $g(i, 1, u, p, x) = f(i, 1, u, p, x)$ 817 818 If $s_i = 0$, we have the following transitions: 819 820 * $f(i, 1, u, p, x) = \sum_{y=h}^{x-(c_i-1)} g(i+1, 1, u, p, y) \times g(i, 0, c_i, p - (c_i - 1) - y+h, x - (c_i - 1) - y) \times \frac {u+y} {(p-y+1+h)^{\underline c_i}}$ 821 * $g(i, 1, u, p, x) = g(i+1, 1, u, p, x) + f(i, 1, u, p, x)$ 822 823 The time complexity is $O(n^5)$. 824 825 Now consider adding the cards with value $1$. It is possible that our game never terminates when we keep on drawing cards with value $1$. We will instead force that when we play a card of value $1$, we are not allowed to draw a card of value $1$. It is not hard to observe that the answer will not change. 826 827 Consider $dp(i,x)$ to be the probability that we have in our hand: 828 829 * $i$ card of value $0$ 830 * $x$ card of value $1$ 831 832 It is not hard to observe that for the initial state, $dp(i, o+x)$ is $g(1, 1, i+x, 0, m) \times \binom {i+x} i \times (m-o)^{\underline x}$. 833 834 Next, consider the transitions. There are only two cases, we draw a card with value $0$, or a card with value greater than $0$: 835 836 * $dp(i, x) \times \frac 1 {w+k-i}\rightarrow dp(i + 1, x - 1)$ 837 * $\forall j+y \gt 1, dp(i, x) \times g(1, 0, 1, n-d-i-x,j+y-1) \times \frac 1 {w+k-i} \times \binom {j+y} j \times (m-x+1)^{\underline y}\rightarrow dp(i+j, x+y-1)$ 838 839 Finally, the answer is $\sum_{i=0}^k dp(i, 0) \times k^{\underline i}$. 840 841 The time complexity is $O(n^4)$. 842 843 Therefore, the total complexity is $O(n^5)$. If we use FFT, it can be $O(n^4 \log n)$, but it was not required in our solution and would probably make the code slower. 844 845 Furthermore, we can record $v$ instead of $u$, which means there are $v$ cards with $i$ or greater index drawn from $u$ draws. So it's not difficult to find $v \leq u $. And when $c_i \leq \sqrt n $, we have $v \leq u \leq c_i \leq \sqrt n $. And when $c_i \gt \sqrt n $, we have $v \leq \frac n {c_i - 1} \leq \sqrt n $, the complexity can become $O (n ^ {4.5}) $. If we use FFT, it can be $O (n ^ {3.5} \log n) $. 846 847 Let $k$ be the number of cards with value $0$. It is not hard to see that: 848 849 * the size of $i$ is $n-k$ 850 * the size of $x$ is $k$ 851 * the size of $u$ is $n-k$ 852 * the size of $p$ is $n$ 853 854 The number of states is $(n-k)^2k^2n$, which has a constant of $\frac{1}{16}$. We also have that $y \leq x$ and $u \leq c_i$, which both gives us another constant of $\frac{1}{2}$. Since we have a flag in our dp state, it has a factor of $2$. This gives us a constant factor of rougly $\frac{1}{32}$, which is extremely small. So it is reasonable to expect $O(n^5)$ to run about $1$ second. 855 856 **Code** 857 858 ``` 859 #include<bits/stdc++.h> 860 861 using namespace std; 862 typedef long long ll; 863 864 const ll N = 120 + 5, Mod = 1e9 + 7; 865 866 inline ll power(ll x, ll y){ 867 ll ret = 1; 868 while(y){ 869 if(y & 1) ret = ret * x % Mod; 870 x = x * x % Mod, y >>= 1; 871 } 872 return ret; 873 } 874 875 inline ll inv(ll x){ 876 return power(x, Mod - 2); 877 } 878 879 ll n = 0, m = 0, w = 0, o = 0, d = 0, r = 0, k = 0, c[N] = {}, v[N] = {}; 880 ll iv[N] = {}, a[N][N] = {}, b[N][N] = {}, binom[N][N] = {}; 881 ll f[2][2][N][N][N] = {}, g[2][2][N][N][N] = {}, dp[N][N] = {}; 882 char s[N] = {}; 883 884 inline void init(){ 885 n = m = w = o = d = r = k = 0; 886 memset(c, 0, sizeof(c)), memset(v, 0, sizeof(v)), memset(s, 0, sizeof(s)); 887 memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g)), memset(dp, 0, sizeof(dp)); 888 } 889 890 inline void solve(){ 891 scanf("%lld", &n); 892 v[0] = v[1] = 1; 893 for(ll i = 1 ; i <= n ; i ++){ 894 scanf("%lld", &c[i]); 895 v[c[i]] = 1; 896 } 897 scanf("%s", s + 1); 898 for(ll i = 1 ; i <= n ; i ++){ 899 if(s[i] == '0') r ++; 900 if(c[i] > 1) w ++; 901 else if(c[i] == 1){ 902 if(s[i] == '1') o ++; 903 m ++; 904 } 905 else{ 906 if(s[i] == '1') d ++; 907 else k ++; 908 } 909 } 910 if(c[n] <= 1){ 911 for(ll i = 1 ; i <= n ; i ++) if(s[i] == '0'){ 912 printf("0\n"); 913 return; 914 } 915 printf("1\n"); 916 return; 917 } 918 for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[n] ; u ++) if(v[u]){ 919 f[1][0][u][p][0] = f[1][1][u][p][0] = 1; 920 g[1][0][u][p][0] = g[1][1][u][p][0] = 1; 921 } 922 for(ll i = n, h = 0 ; c[i] > 1 ; i --){ 923 for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]){ 924 g[0][0][u][p][0] = 1; 925 if(s[i] == '0') g[0][1][u][p][0] = g[1][1][u][p][0]; 926 } 927 for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]) for(ll x = 1 ; x <= k ; x ++){ 928 for(ll y = 0 ; y <= x - (c[i] - 1) ; y ++) f[0][0][u][p][x] = (f[0][0][u][p][x] + (g[1][0][u][p][y] * g[0][0][c[i]][p - (c[i] - 1) - y][x - (c[i] - 1) - y] % Mod) * ((u + y) * b[p - y + 1][c[i]] % Mod)) % Mod; 929 g[0][0][u][p][x] = (g[1][0][u][p][x] + f[0][0][u][p][x]) % Mod; 930 } 931 for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]) for(ll x = 1 ; x <= k ; x ++){ 932 if(s[i] == '1'){ 933 for(ll y = h ; y <= x - c[i] ; y ++) f[0][1][u][p][x] = (f[0][1][u][p][x] + (g[1][1][u][p][y] * g[0][0][c[i]][p - (c[i] - 1) - y + h][x - c[i] - y] % Mod) * b[p - y + 1 + h][c[i]]) % Mod; 934 g[0][1][u][p][x] = f[0][1][u][p][x]; 935 } 936 else{ 937 for(ll y = h ; y <= x - (c[i] - 1) ; y ++) f[0][1][u][p][x] = (f[0][1][u][p][x] + (g[1][1][u][p][y] * g[0][0][c[i]][p - (c[i] - 1) - y + h][x - (c[i] - 1) - y] % Mod) * ((u + y) * b[p - y + 1 + h][c[i]] % Mod)) % Mod; 938 g[0][1][u][p][x] = (g[1][1][u][p][x] + f[0][1][u][p][x]) % Mod; 939 } 940 } 941 for(ll p = 0 ; p <= n ; p ++) for(ll u = 0 ; u <= c[i] ; u ++) if(v[u]) for(ll x = 0 ; x <= k ; x ++){ 942 f[1][0][u][p][x] = f[0][0][u][p][x], f[1][1][u][p][x] = f[0][1][u][p][x]; 943 g[1][0][u][p][x] = g[0][0][u][p][x], g[1][1][u][p][x] = g[0][1][u][p][x]; 944 f[0][0][u][p][x] = f[0][1][u][p][x] = g[0][0][u][p][x] = g[0][1][u][p][x] = 0; 945 } 946 if(s[i] == '1') h ++; 947 } 948 for(ll i = 0 ; i <= k ; i ++) for(ll x = 0 ; x <= m - o ; x ++) dp[i][o + x] = g[1][1][0][r][i + x] * (binom[i + x][i] * a[m - o][x] % Mod) % Mod; 949 for(ll i = 0 ; i <= k ; i ++) for(ll x = 1 ; x <= m ; x ++) if(dp[i][x]){ 950 if(i < k) dp[i + 1][x - 1] = (dp[i + 1][x - 1] + dp[i][x] * iv[w + k - i]) % Mod; 951 for(ll j = 0 ; i + j <= k ; j ++) for(ll y = 0 ; x + y - 1 <= m ; y ++) if(j + y > 1) dp[i + j][x + y - 1] = (dp[i + j][x + y - 1] + (dp[i][x] * g[1][0][1][n - d - i - x][j + y - 1] % Mod) * (iv[w + k - i] * (binom[j + y][j] * a[m - x + 1][y] % Mod) % Mod)) % Mod; 952 } 953 ll ans = 1; 954 for(ll i = 0 ; i <= k ; i ++) ans = (ans + (Mod - dp[i][0]) * a[k][i]) % Mod; 955 printf("%lld\n", ans); 956 } 957 958 ll T = 0; 959 960 int main(){ 961 for(ll x = 0 ; x < N ; x ++){ 962 a[x][0] = b[x][0] = 1, iv[x] = inv(x), binom[x][0] = 1; 963 for(ll y = 1 ; y <= x ; y ++){ 964 a[x][y] = a[x][y - 1] * (x - y + 1) % Mod, b[x][y] = inv(a[x][y]); 965 binom[x][y] = (binom[x - 1][y - 1] + binom[x - 1][y]) % Mod; 966 } 967 } 968 scanf("%lld", &T); 969 for(ll i = 1 ; i <= T ; i ++) init(), solve(); 970 return 0; 971 } 972 ``` 973 974 Solution by [Melania](/profile/Melania "Grandmaster Melania") 975 976 **Solution** 977 978 Let $ S $ denote the set of cards currently in Jellyfish's hand. 979 980 We assume that $ a_1 = 0 $ and $ a_n \geq 2 $. Initially, $ |S| \in [1, n-1] $. Cases where these conditions do not hold are trivial. 981 982 We observe that Jellyfish cannot empty the draw pile if and only if she runs out of non-zero cards to play. In the following section, we compute the probability that she eventually runs out of non-zero cards. 983 984 It is clear that in any scenario where she runs out of non-zero cards, $ \max(S) $ must gradually decrease to zero. We can break down the entire process into sub-procedures, where in each sub-procedure, $ \max(S) $ decreases from $ i $ to $ \leq i-1 $, ultimately reaching zero. 985 986 Assume she is currently in a state where $ \max(S) = i $ and $ |S \setminus {i}| = x $. We denote $ F_{i,x,y} $ as the probability that she will eventually transition to a state where $ \max(S) \leq i-1 $, and in the very first state where $ \max(S) \leq i-1 $, the size of $ S $ is $ y $. 987 988 --- 989 990 For a fixed and given pair $(i,x)$, we aim to compute all values of $F_{i,x,y}$ simultaneously. 991 992 To determine the values of $F_{i,x,y}$, consider the situation after Jellyfish plays card $a_i$. For the remaining $n-x$ cards, each card is equally likely to be one of the $a_i$ cards drawn. Therefore, for any individual card outside of the initial $x$ cards, the probability of possessing that card is $p = \dfrac{a_i}{n-x}$. 993 994 We define the initial event where Jellyfish plays card $a_i$ as the starting point of our timeline. Following this event, we consider $n-i+2$ key moments when $\max(S)$ becomes $\leq n$ for the first time, $\leq n-1$ for the first time, and so on, down to $\leq i+1$, $\leq i$, and finally $\leq i-1$ for the first time. 995 996 We denote $G_{j,y}$ as the probability that Jellyfish will eventually reach a state where $\max(S) \leq j$, and in the very first state where $\max(S) \leq j$, the size of $S$ is $y$. Initially, $G_{n,x + a_i} = 1$. 997 998 To understand the transitions of $G_{j,y}$, note that since all cards $\leq j$ (excluding the initial $x$ cards) are symmetrical, the probability of owning card $j$ is exactly $p=\dfrac{y-x}{j-x}$. 999 1000 * If Jellyfish does not own card $j$, then the first state where $\max(S) \leq j-1$ is simply the first state where $\max(S) \leq j$. This describes a transition of $G_{j-1,y} \leftarrow (1-p)G_{j,y}$. 1001 * If Jellyfish owns card $j$, we enumerate the number of cards $|S| = z$ in her hand when she first reaches $\max(S) \leq j-1$. The probability of this happening is $F_{j,y-1,z}$. Thus, we have $G_{j-1,z} \leftarrow pG_{j,y}F_{j,y-1,z}$. 1002 1003 Here’s a further explanation of why "all cards $\leq j$ (excluding the initial $x$ cards) are symmetrical": Because this state is the very first time $\max(S) \leq j$, it means that all cards played before this state and after Jellyfish initially plays $a_i$ are $\geq j+1$. From the perspective of those cards $\geq j+1$, all cards $\leq j$ (excluding the initial $x$ cards) are symmetrical. 1004 1005 --- 1006 1007 In the end, the actual algorithm we derived for computing $F_{i,x,y}$ is quite straightforward: 1008 1009 * Iterate through $j$ backwards from $n$ to $i$. 1010 * For each $G_{j,y}$, make two types of transitions: 1011 1012 1. $G_{j-1,z} \leftarrow pG_{j,y}F_{j,y-1,z}$, where $p = \dfrac{y-x}{j-x}$; 1013 2. $G_{j-1,y} \leftarrow (1-p)G_{j,y}$. 1014 1015 Finally, $F_{i,x,y} = G_{i-1,y}$. 1016 1017 A small catch is that we could have self-loops. If $a_i = 1$, then in the final step where $j = i$, there will be some transitions where $F_{i,x,y} \leftarrow cF_{i,x,y}$. For a given $F_{i,x,y}$, if all the other known values that contribute to it sum to $A$ and all the $c$ coefficients sum to $C$, then we have $F_{i,x,y} = A + CF_{i,x,y}$. This results in $F_{i,x,y} = \dfrac{A}{1-C}$. We can address this by calculating the inverse. 1018 1019 It can be shown that if we also iterate through $x$ from larger to smaller values, no $F_{i,x,y}$ will use other values of $F_{i',x',y'}$ that are neither known nor equal to $F_{i,x,y}$ itself. In other words, the value of $F_{i,x,y}$ does not invoke other unknown values of $F_{i',x',y'}$. 1020 1021 --- 1022 1023 After computing all values of $F_{i,x,y}$, we proceed to determine the final answer. 1024 1025 We define $\text{ans}_{i,x}$ as the average probability that Jellyfish will eventually run out of non-zero cards (thus losing the game) if she starts with all $s_i$ cards in $[1, i]$ (which she owns initially) plus an additional $x$ cards drawn randomly from the remaining $i - s_i$ cards in $[1, i]$ (which she does not own initially). 1026 1027 * If $c_i = 1$, the transition is given by: $\text{ans}_{i,x}=\displaystyle\sum F_{i,x-1,y}\text{ans}_{i-1,y}$; 1028 * If $c_i = 0$, the transition is given by: $\text{ans}_{i,x}=(1-p)\text{ans}_{i-1,x}+p\displaystyle\sum F_{i,x-1,y}\text{ans}_{i-1,y}$, where $p=\dfrac{x-s_i}{i-s_i}$. 1029 1030 Finally, we compute $1 - \text{ans}_{n,s_n}$ to obtain the probability that Jellyfish will eventually win the game. 1031 1032 The time complexity of this approach is $\mathcal{O}(n^5 + n^3 \log p)$, and the space complexity is $\mathcal{O}(n^3)$. 1033 1034 --- 1035 1036 It is also possible to optimize the $\mathcal{O}(n^5)$ time complexity to $\mathcal{O}(n^4 \sqrt{n})$ by using Lagrange interpolation. 1037 1038 To achieve this speedup, we notice that the values of $i$ and $x$ do not play a crucial role in the transition of $G_{j,y}$. Specifically, the influence of the values $i$ and $x$ on the transition of $G_{j,y}$ can be described as follows: 1039 1040 * The initial value is $G_{n,x+a_i} = 1$. 1041 * During the transition, $p = \dfrac{y-x}{j-x}$ and $1-p = \dfrac{j-y}{j-x}$. 1042 1043 We can fix the value of $k = x + a_i$ and treat $x$ as a variable, maintaining a polynomial in $x$ as the value of $G_{j,y}$. 1044 1045 We observe that it is only necessary to keep the point values between $[k-1, k-\sqrt{n}]$ to track the polynomial accurately. 1046 1047 * For $a_i \gt \sqrt{n}$, since each transition involving multiplication by $p$ will increase the value of $y$ by at least $a_i$, it is clear that the degree of the polynomial $G_{j,y}$ is at most $\sqrt{n}$. Thus, keeping track of $\sqrt{n}$ values is sufficient to restore the polynomial, and we can use linear Lagrange interpolation to obtain the point values outside these $\sqrt{n}$ points. 1048 * For $a_i \leq \sqrt{n}$, since $x = k - a_i$, we only care about the point values in the range $[k-1, k-\sqrt{n}]$. Although the polynomial restored may be inaccurate beyond this range, these point values are the ones that matter for our calculations anyway. 1049 1050 By applying this optimization, we effectively reduce the time complexity to $\mathcal{O}(n^4 \sqrt{n} + n^3 \log p)$.