1930.md (52546B)
1 Source: https://codeforces.com/blog/entry/126043 2 3 Thank you for your participation! I hope you liked atleast one problem from the set (: 4 5 [1930A - Maximise The Score](/contest/1930/problem/A "think-cell Round 1") 6 7 Idea: [satyam343](/profile/satyam343 "Master satyam343") 8 Editorial: [Non-origination](/profile/Non-origination "Expert Non-origination") 9 10 **Hint 1** 11 12 Selecting the smallest two elements on the whiteboard is a good choice in the first move. 13 14 **Solution** 15 16 Let $b$ denote the sorted array $a$. Assume that $b$ contains only distinct elements for convenience. We prove by induction on $n$ that the maximum final score is $b_1 + b_3 + \ldots + b_{2n-1}$. 17 18 For the base case $n = 1$, the final and only possible score that can be achieved is $b_1$. 19 20 Now let $n \gt 1$. 21 22 **Claim**: It is optimal to choose $b_{1}$ with $b_{2}$ for some move. 23 24 **Proof** 25 26 Suppose that in some move, $b_{1}$ is choosen with $b_i$ and $b_{2}$ is choosen with $b_j$, for some $2 \lt i,j \lt 2n, i \not = j$. 27 28 The contribution to the score according to these choices is $\min(b_{1}, b_{i}) + \min(b_{2}, b_{j}) = b_{1} + b_{2}$. 29 30 However, if we had chosen $b_{1}$ and $b_{2}$ in one move, and $b_i$ and $b_j$ in the other move, the score according to these choices is $\min(b_{1}, b_{2}) + \min(b_{i}, b_{j}) = b_{1} + \min(b_{i}, b_{j})$. 31 32 As $i, j \gt 2$, $b_i \gt b_{2}$ and $b_j \gt b_{2} \implies \min(b_{i}, b_{j}) \gt b_2$. Thus, we can achieve a strictly larger score by choosing $b_1$ with $b_2$ in some move. 33 34 The choice of selecting $b_1$ and $b_2$ contributes a value of $b_1$ to the score. The maximum score that can achieved for the remaining numbers $[b_3, b_4, \ldots, b_{2n}]$ on the whiteboard in the remaining moves is $b_3 + b_5 + b_7 + \ldots b_{2n-1}$ by the induction hypothesis. 35 36 Note that we can extend the arguments for the case where $a$ has duplicate elements. 37 38 **Code** 39 40 ``` 41 #include <bits/stdc++.h> 42 using namespace std; 43 #define ll long long 44 void solve(){ 45 ll n; cin>>n; 46 vector<ll> a(2*n); 47 ll ans=0; 48 for(auto &it:a){ 49 cin>>it; 50 } 51 sort(a.begin(),a.end()); 52 for(ll i=0;i<2*n;i+=2){ 53 ans+=a[i]; 54 } 55 cout<<ans<<"\n"; 56 return; 57 } 58 int main() 59 { 60 ios_base::sync_with_stdio(false); 61 cin.tie(NULL); 62 #ifndef ONLINE_JUDGE 63 freopen("input.txt", "r", stdin); 64 freopen("output.txt", "w", stdout); 65 freopen("error.txt", "w", stderr); 66 #endif 67 ll test_cases=1; 68 cin>>test_cases; 69 while(test_cases--){ 70 solve(); 71 } 72 cout<<fixed<<setprecision(10); 73 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 74 } 75 ``` 76 77 [video editorial by aryanc403](https://youtu.be/OJdMGnC7SHM) 78 79 [1930B - Permutation Printing](/contest/1930/problem/B "think-cell Round 1") 80 81 Idea: [satyam343](/profile/satyam343 "Master satyam343") 82 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 83 84 **Hint 1** 85 86 For integers $x$ ($\lfloor \frac{n}{2} \rfloor \lt x \leq n$), there does not exist integer $y$ ($y \gt x$) such that $y$ is divisible by $x$. 87 88 **Solution** 89 90 Consider the permutation $p$ such that $p=[1, n, 2, n - 1, \ldots \lceil \frac{n+1}{2} \rceil]$. It is valid. Why? 91 92 **Proof** 93 94 We have $\max(p_a, p_{a+1}) \gt \lfloor \frac{n}{2} \rfloor$ for all $1 \leq a \lt n - 1$. So we cannot ever have a pair of integers ($a,b$) such that: 95 96 * $1 \leq a \lt n - 1$ 97 * $1 \leq b \lt n$ 98 * $a \neq b$ 99 * $p_a$ divides $p_b$ and $p_{a+1}$ divides $p_{b+1}$ 100 101 Now, we just need to check for $a = n - 1$. First of all, notice that $p_a$ does not divide $p_1$. 102 103 There does not exist an integer $b$ ($2 \leq b \lt n - 1$) such that $p_{a+1}$ divides $p_{b+1}$ as $2 \cdot p_{a+1} \ge n$ and $p_{c+1} \lt n$ for all $c$ ($2 \leq c \lt n - 1$). 104 105 Note that we covered all possible pairs of indices and did not find two **distinct** indices $i$ and $j$ ($1 \leq i, j \lt n$; $i \neq j$) such that $p_i$ divides $p_j$ and $p_{i+1}$ divides $p_{j+1}$. 106 107 **Code** 108 109 ``` 110 #include <bits/stdc++.h> 111 using namespace std; 112 #define ll long long 113 void solve(){ 114 ll n; cin>>n; 115 ll l=1,r=n; 116 for(ll i=1;i<=n;i++){ 117 if(i&1){ 118 cout<<l<<" "; 119 l++; 120 } 121 else{ 122 cout<<r<<" "; 123 r--; 124 } 125 } 126 cout<<"\n"; 127 return; 128 } 129 int main() 130 { 131 ios_base::sync_with_stdio(false); 132 cin.tie(NULL); 133 #ifndef ONLINE_JUDGE 134 freopen("input.txt", "r", stdin); 135 freopen("output.txt", "w", stdout); 136 freopen("error.txt", "w", stderr); 137 #endif 138 ll test_cases=1; 139 cin>>test_cases; 140 while(test_cases--){ 141 solve(); 142 } 143 cout<<fixed<<setprecision(10); 144 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 145 } 146 ``` 147 148 [video editorial by aryanc403](https://youtu.be/woPPBKBkCFk) 149 150 [1930C - Lexicographically Largest](/contest/1930/problem/C "think-cell Round 1") 151 152 Idea: [satyam343](/profile/satyam343 "Master satyam343") 153 Editorial: [Non-origination](/profile/Non-origination "Expert Non-origination") and [satyam343](/profile/satyam343 "Master satyam343") 154 155 **Hint 1** 156 157 Consider an array $c$ of length $n$ such that $c_i :=$ *number of indices smaller than $i$ which were chosen before index $i$*. 158 159 So set $S$ will be a collection of $a_i + i - c_i$ over all $1 \leq i \leq n$. 160 161 **Solution** 162 163 Now one might wonder what type of arrays $c$ is it possible to get. 164 165 First, it is easy to see that we should have $0 \leq c_i \lt i$ for all $i$. Call an array $c$ of length $n$ *good*, if $0 \leq c_i \lt i$ for all $1 \leq i \leq n$. The claim is that all *good* arrays of length $n$ can be obtained. 166 167 **Proof** 168 169 We can prove it by induction on $n$. 170 171 $c_1 = 0$ always holds. Now $c_2$ can either be $0$ or $1$. We can obtain $c_2 = 0$ by deleting the element at index $2$ before the element at index $1$. We can also obtain $c_2 = 1$ by deleting it after deleting the element at index $1$. Thus, all *good* arrays of length 2 can be obtained. 172 173 Now assume that it is possible to obtain all *good* arrays of length atmost $k$. Choose an integer $x$ ($0 \leq x \leq k$) arbitrarily. Consider the following sequence for the order of deletion: 174 175 * The elements at indices $1, 2, \ldots, x$ in the same order. 176 * The element at index $k$. 177 * The elements at indices $x + 1, \ldots, k - 1$ in the same order. 178 179 It is easy to see that the array obtained on performing the above sequence of operations is a *good* array of length $k + 1$ with $c_{k+1} = x$. Hence we can establish a bijection between the sequence of order of deletion and the number of *good* arrays. 180 181 So we have the following subproblem. We have a set $S$. We will iterate $i$ from $1$ to $n$, select an integer $c_i$ ($0 \leq c_i \leq i - 1$) and insert $a_i + i - c_i$ into set $S$ and move to $i + 1$. Now using exchange arguments, we can prove that it is never bad if we select the smallest integer $v$ ($0 \leq v \leq i - 1$) such that $a_i + i - v$ is not present in the set $S$, and assign it to $c_i$. Note that as we have $i$ options for $v$, and we would have inserted exactly $i-1$ elements before index $i$, there always exists an integer $v$ ($0 \leq v \leq i - 1$) such that $a_i + i - v$ is not present in the set $S$. You can refer to the attached submission to see how to find $v$ efficiently for each $i$. 182 183 **Code** 184 185 ``` 186 #include <bits/stdc++.h> 187 using namespace std; 188 #define ll long long 189 void solve(){ 190 ll n; cin>>n; 191 set<ll> used,not_used; 192 vector<ll> ans; 193 for(ll i=1;i<=n;i++){ 194 ll x; cin>>x; x+=i; 195 if(!used.count(x)){ 196 not_used.insert(x); 197 } 198 ll cur=*(--not_used.upper_bound(x)); //find the largest element(<= x) which is not in set "used" 199 not_used.erase(cur); 200 ans.push_back(cur); 201 used.insert(cur); 202 if(!used.count(cur-1)){ 203 not_used.insert(cur-1); 204 } 205 } 206 sort(ans.begin(), ans.end()); 207 reverse(ans.begin(), ans.end()); 208 for(auto i:ans){ 209 cout<<i<<" "; 210 } 211 cout<<"\n"; 212 return; 213 } 214 int main() 215 { 216 ios_base::sync_with_stdio(false); 217 cin.tie(NULL); 218 #ifndef ONLINE_JUDGE 219 freopen("input.txt", "r", stdin); 220 freopen("output.txt", "w", stdout); 221 freopen("error.txt", "w", stderr); 222 #endif 223 ll test_cases=1; 224 cin>>test_cases; 225 while(test_cases--){ 226 solve(); 227 } 228 cout<<fixed<<setprecision(10); 229 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 230 } 231 ``` 232 233 [video editorial by aryanc403](https://youtu.be/d8_f4ae0lJ8) 234 235 [1930D1 - Sum over all Substrings (Easy Version)](/contest/1930/problem/D1 "think-cell Round 1") 236 237 Idea: [satyam343](/profile/satyam343 "Master satyam343") 238 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 239 240 **Hint 1** 241 242 To find $f(s)$, we can partition $s$ into multiple independent substrings of length atmost $3$ and find best answer for them separately. 243 244 **Hint 2** 245 246 There always exists a string $g$ such that: 247 248 1. $g$ is $s-good$ 249 2. there are $f(s)$ number of $\mathtt{1} $s in $g$ 250 3. $g$ is of the form $b_1 + b_2 + \ldots b_q$, where $b_i$ is either equal to $\mathtt{0}$ or $\mathtt{010}$. 251 252 **Solution** 253 254 First of all, append $n$ $\mathtt{0} $ s to the back of $s$ for our convenience. Note that this does not change the answer. 255 256 Now let us call a binary string $p$ of size $d$ *nice* if: 257 258 1. there exists a positive integer $k$ such that $d = 3k$ 259 2. $p$ is of form $ f(\mathtt{0} , k) + f(\mathtt{1} , k) + f(\mathtt{0} , k) $, where $f(c, z)$ gives a string containing exactly $z$ characters equal to $c$. 260 261 Suppose binary string $t$ is one of the $s-good$ strings such that there are exactly $f(s)$ $\mathtt{1} $ s in $t$. 262 263 We claim that for any valid $t$, there always exists a binary string $t'$ such that: 264 265 1. $t'$ is permutation of $t$ 266 2. $t'$ is $s-good$ 267 3. $t'$ is of the form $f(\mathtt{0}, d_1) + z_1 + f(\mathtt{0}, d_2) + z_2 + f(\mathtt{0}, d_3) + \ldots + z_g + f(\mathtt{0}, d_{g+1}) $, where $z_1, z_2, \ldots z_g$ are *nice* binary strings and $d_1, d_2, \ldots d_{g+1}$ are non-negative integers. 268 269 **Proof** 270 271 Initially, all the $\mathtt{1} $s in $s$ are unmarked. We will mark all of them and modify the string $t$ in the process. 272 273 We will do the following recursive process unless all the $\mathtt{1} $ s in $s$ are marked. 274 275 Find the index of leftmost unmarked $\mathtt{1} $ in $s$. Suppose its index is $x$. Now suppose $y$ is the largest index such that there are an equal number of $\mathtt{0} $ s and $\mathtt{1} $ s in substring $t[x, y]$. Note that $y$ will always exist as we appended some extra $\mathtt{0} $s in the starting. Now we can rearrange the characters in substring $t[x,y]$, as they will still contain an equal number of $\mathtt{0} $ s and $\mathtt{1} $ s and $\mathtt{1} $ will still be the mode of substring $t[x,y]$. Obviously rearranging the characters in $t[x,y]$ to $\mathtt{0} \ldots \mathtt{0} \mathtt{1} \ldots \mathtt{1}$ is the best we can do. We will mark all the $\mathtt{1} $ s in substring $s[x,y]$. Suppose $y-x+1 = 2v$. Now $t[y+1,y+v]$ might contain some $\mathtt{1} $ s. Say there are $z$ $\mathtt{1} $ s in $t[y+1,y+v]$ initially. We will do the following operation exactly $z$ times. 276 277 * Find the leftmost $\mathtt{1} $ in substring $t[y+1,y+v]$. Find the leftmost $\mathtt{0} $ in substring $t[y+v+1,2n]$. Swap both characters. 278 279 Now note that $t[x,x+3v-1]$ will be of form $f(\mathtt{0}, v) + f(\mathtt{1}, v) + f(\mathtt{0}, v)$. It is easy to verify that in the updated $t$, there won't be any index $i$ for which there does not exist two indices $1 \le l \le i \le r \le 2n$ such that $s_i$ is *mode* of $t[l,r]$. 280 281 Now we can mark all the $\mathtt{1} $ s in substring $s[x+2v,x+3v-1]$ too, as $t[x+v,x+3v-1]$ contain equal number of $\mathtt{0} $ s and $\mathtt{1} $ s. 282 283 It is not hard to conclude that the updated $t$ will be of form $f(\mathtt{0}, d_1) + z_1 + f(\mathtt{0}, d_2) + z_2 + f(\mathtt{0}, d_3) + \ldots + z_g + f(\mathtt{0}, d_{g+1}) $, where $z_1, z_2, \ldots z_g$ are *nice* binary strings and $d_1, d_2, \ldots d_{g+1}$ are non-negative integers. 284 285 Note that the $\mathtt{1}$ s in $t[x, x + 3v - 1]$ won't help the $\mathtt{1}$ s in $s[x + 3v, 2n]$. So, we can solve for $s[x + 3v, 2n]$ independently. 286 287 Let $t'$ be the updated $t$. 288 289 Now, carefully observe the structure of $t'$. We can replace all the substrings of the form $ f(\mathtt{0} , k) + f(\mathtt{1} , k) + f(\mathtt{0} , k) $ in $t'$ with $ \mathtt{0} \mathtt{1} \mathtt{0} \mathtt{0} \mathtt{1} \mathtt{0} \ldots \mathtt{0} \mathtt{1} \mathtt{0} \mathtt{0} \mathtt{1} \mathtt{0}$. 290 291 So the updated $t'$(say $t"$) will be of form $b_1 + b_2 + \ldots b_q$, where $b_i$ is either equal to $\mathtt{0}$ or $\mathtt{010}$. 292 293 So whenever we need to find $f(e)$ for some binary string $e$, we can always try to find a string of form $t"$ using as few $\mathtt{1} $s as possible. Notice that we can construct $t"$ greedily. You can look at the attached code for the implementation details. Also, we don't need to actually append the $\mathtt{0} $s at the back of $s$. It was just for proof purposes. 294 295 **Code** 296 297 ``` 298 #include <bits/stdc++.h> 299 #include <ext/pb_ds/tree_policy.hpp> 300 #include <ext/pb_ds/assoc_container.hpp> 301 using namespace __gnu_pbds; 302 using namespace std; 303 #define ll long long 304 #define pb push_back 305 #define mp make_pair 306 #define nline "\n" 307 #define f first 308 #define s second 309 #define pll pair<ll,ll> 310 #define all(x) x.begin(),x.end() 311 const ll MOD=1e9+7; 312 const ll MAX=500500; 313 ll f(string s){ 314 ll len=s.size(),ans=0,pos=0; 315 while(pos<len){ 316 if(s[pos]=='1'){ 317 ans++; 318 pos+=2; 319 } 320 pos++; 321 } 322 return ans; 323 } 324 void solve(){ 325 ll n,ans=0; cin>>n; 326 string s; cin>>s; 327 for(ll i=0;i<n;i++){ 328 string t; 329 for(ll j=i;j<n;j++){ 330 t.push_back(s[j]); 331 ans+=f(t); 332 } 333 } 334 cout<<ans<<nline; 335 return; 336 } 337 int main() 338 { 339 ios_base::sync_with_stdio(false); 340 cin.tie(NULL); 341 #ifndef ONLINE_JUDGE 342 freopen("input.txt", "r", stdin); 343 freopen("output.txt", "w", stdout); 344 freopen("error.txt", "w", stderr); 345 #endif 346 ll test_cases=1; 347 cin>>test_cases; 348 while(test_cases--){ 349 solve(); 350 } 351 cout<<fixed<<setprecision(10); 352 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 353 } 354 ``` 355 356 [1930D2 - Sum over all Substrings (Hard Version)](/contest/1930/problem/D2 "think-cell Round 1") 357 358 Idea: [satyam343](/profile/satyam343 "Master satyam343") 359 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 360 361 **Hint 1** 362 363 We can use the idea of D1 and dynamic programming to solve in $O(n)$. 364 365 **Solution** 366 367 Suppose $dp[i][j]$ denotes $f(s[i,j])$ for all $1 \le i \le j \le n$. 368 369 Performing the transition is quite easy. 370 371 If $s_i = \mathtt{1}$, $dp[i][j]=1+dp[i+3][j]$, otherwise $dp[i][j]=dp[i+1][j]$. Note that 372 373 Unable to parse markup [type=CF_MATHJAX] 374 375 for if $i \gt j$. 376 377 So if we fix $j$, we can find $dp[i][j]$ for all $1 \le i \le j$ in $O(n)$, and the original problem in $O(n^2)$. 378 379 Now, we need to optimise it. 380 381 Suppose $track[i] = \sum_{j=i}^{n} dp[i][j]$ for all $1 \le i \le n$, with base condition that $track[i] = 0$ if $i \gt n$. 382 383 There are two cases: 384 385 * $s_i = \mathtt{0}$ : 386 387 1. $track[i] = \sum_{j=i}^{n} dp[i][j]$ 388 2. $track[i] = dp[i][i] + \sum_{j=i+1}^{n} dp[i][j]$ 389 3. $track[i] = dp[i][i] + \sum_{j=i+1}^{n} dp[i+1][j]$ 390 4. $track[i] = track[i+1]$ as $dp[i][i]=0$ 391 392 * $s_i = \mathtt{1}$ : 393 394 1. $track[i] = \sum_{j=i}^{n} dp[i][j]$ 395 2. $track[i] = \sum_{j=i}^{n} 1 + dp[i+3][j]$ 396 3. $track[i] = n - i + 1 + \sum_{j=i+3}^{n} dp[i+3][j]$ as $dp[i+3][i]=dp[i+3][i+1]=dp[i+3][i+2]=0$ 397 4. $track[i] = n - i + 1 + \sum_{j=i+3}^{n} dp[i+3][j]$ 398 5. $track[i] = n - i + 1 + track[i+3]$ 399 400 So, the answer to the original problem is $\sum_{i=1}^{n} track[i]$, which we can do in $O(n)$. 401 402 **Code** 403 404 ``` 405 #include <bits/stdc++.h> 406 #include <ext/pb_ds/tree_policy.hpp> 407 #include <ext/pb_ds/assoc_container.hpp> 408 using namespace __gnu_pbds; 409 using namespace std; 410 #define ll long long 411 #define pb push_back 412 #define mp make_pair 413 #define nline "\n" 414 #define f first 415 #define s second 416 #define pll pair<ll,ll> 417 #define all(x) x.begin(),x.end() 418 const ll MOD=1e9+7; 419 const ll MAX=500500; 420 void solve(){ 421 ll n,ans=0; cin>>n; 422 string s; cin>>s; s=" "+s; 423 vector<ll> dp(n+5,0); 424 for(ll i=n;i>=1;i--){ 425 if(s[i]=='1'){ 426 dp[i]=dp[i+3]+n-i+1; 427 } 428 else{ 429 dp[i]=dp[i+1]; 430 } 431 ans+=dp[i]; 432 } 433 cout<<ans<<nline; 434 return; 435 } 436 int main() 437 { 438 ios_base::sync_with_stdio(false); 439 cin.tie(NULL); 440 #ifndef ONLINE_JUDGE 441 freopen("input.txt", "r", stdin); 442 freopen("output.txt", "w", stdout); 443 freopen("error.txt", "w", stderr); 444 #endif 445 ll test_cases=1; 446 cin>>test_cases; 447 while(test_cases--){ 448 solve(); 449 } 450 cout<<fixed<<setprecision(10); 451 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 452 } 453 ``` 454 455 [1930E - 2..3...4.... Wonderful! Wonderful!](/contest/1930/problem/E "think-cell Round 1") 456 457 Idea: [satyam343](/profile/satyam343 "Master satyam343") 458 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 459 460 **Hint 1** 461 462 Suppose you are given some array $b$ of length $m$ and a positive integer $k$. How to check whether we can get the array $b$ if we start with an array $a$ of length $n$ such that $a_i = i$ for all $i$ ($1 \leq i \leq n$)? 463 464 **Hint 2** 465 466 First of all, array $b$ should be a subsequence of $a$. Now consider an increasing array $c$ (possibly empty) such that it contains all the elements of $a$ which are not present in $b$. Now look at some trivial necessary conditions. 467 468 * The length of array $c$ should divisible by $2k$, as exactly $2k$ elements were deleted in one operation. 469 * There should be atleast one element $v$ in $b$ such that there are atleast $k$ elements smaller than $v$ in the array $c$, and alteast $k$ elements greater than $v$ in the array $c$. Why? Think about the last operation. We can consider the case of empty $c$ separately. 470 471 In fact, it turns out that these necessary conditions are sufficient (Why?). 472 473 **Solution** 474 475 Now, we need to find the number of possible $b$. We can instead find the number of binary strings $s$ of length $n$ such that $s_i = 1$ if $i$ is present in $b$, and $s_i=0$ otherwise. 476 477 For given $n$ and $k$, let us call $s$ **good** if there exists some $b$ which can be achieved from $a$. 478 479 Instead of counting strings $s$ which are **good**, let us count the number of strings which are not **good**. 480 481 For convenience, we will only consider strings $s$ having the number of $\mathtt{0}$'s divisible by $2k$. 482 483 Now, based on the conditions in hint $2$, we can conclude that $s$ is **bad** if and only if there does not exist any $1$ between the $k$-th $0$ from the left and the $k$-th $0$ from the right in $s$. 484 485 Let us compress all the $\mathtt{0}$'s between the $k$-th $0$ from the left and the $k$-th $0$ from the right into a single $0$ and call the new string $t$. Note that $t$ will have exactly $2k - 1$ $\mathtt{0}$'s. We can also observe that for each $t$, a unique $s$ exists. This is only because we have already fixed the parameters $n$ and $k$. Thus the number of **bad** $s$ having exactly $x$ $\mathtt{1}$'s is ${{x + 2k - 1} \choose {2k - 1}}$ as there are exactly ${{x + 2k - 1} \choose {2k - 1}}$ binary strings $t$ having $2k - 1$ $\mathtt{0}$'s and $x$ $\mathtt{1}$'s. 486 487 Finally, there are exactly $\binom{n}{x} - \binom{x + 2k - 1}{2k - 1}$ **good** binary strings $s$ having $x$ $\mathtt{1}$'s and $n-x$ $\mathtt{0}$'s. Now, do we need to find this value for each $x$ from $1$ to $n$? No, as the number($n-x$) of $\mathtt{0}$'s in $s$ should be a multiple of $2k$. There are only $O(\frac{n}{2k})$ useful candidates for $x$. 488 489 Thus, our overall complexity is $O(n \log(n))$ (as $\sum_{i=1}^{n} O(\frac{n}{i}) = O(n \log(n))$). 490 491 **Code** 492 493 ``` 494 #pragma GCC optimize("O3,unroll-loops") 495 #include <bits/stdc++.h> 496 #include <ext/pb_ds/tree_policy.hpp> 497 #include <ext/pb_ds/assoc_container.hpp> 498 using namespace __gnu_pbds; 499 using namespace std; 500 #define ll long long 501 const ll INF_ADD=1e18; 502 #define pb push_back 503 #define mp make_pair 504 #define nline "\n" 505 #define f first 506 #define s second 507 #define pll pair<ll,ll> 508 #define all(x) x.begin(),x.end() 509 const ll MOD=998244353; 510 const ll MAX=5000500; 511 vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1); 512 ll binpow(ll a,ll b,ll MOD){ 513 ll ans=1; 514 a%=MOD; 515 while(b){ 516 if(b&1) 517 ans=(ans*a)%MOD; 518 b/=2; 519 a=(a*a)%MOD; 520 } 521 return ans; 522 } 523 ll inverse(ll a,ll MOD){ 524 return binpow(a,MOD-2,MOD); 525 } 526 void precompute(ll MOD){ 527 for(ll i=2;i<MAX;i++){ 528 fact[i]=(fact[i-1]*i)%MOD; 529 } 530 inv_fact[MAX-1]=inverse(fact[MAX-1],MOD); 531 for(ll i=MAX-2;i>=0;i--){ 532 inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD; 533 } 534 } 535 ll nCr(ll a,ll b,ll MOD){ 536 if(a==b){ 537 return 1; 538 } 539 if((a<0)||(a<b)||(b<0)) 540 return 0; 541 ll denom=(inv_fact[b]*inv_fact[a-b])%MOD; 542 return (denom*fact[a])%MOD; 543 } 544 ll n,k; 545 ll ways(ll gaps,ll options){ 546 gaps--; 547 ll now=nCr(gaps+options-1,options-1,MOD); 548 return now; 549 } 550 void solve(){ 551 cin>>n; 552 for(ll k=1;k<=(n-1)/2;k++){ 553 ll ans=1; 554 for(ll deleted=2*k;deleted<=n-1;deleted+=2*k){ 555 ll options=2*k,left_elements=n-deleted; 556 ans=(ans+ways(left_elements+1,deleted+1)-ways(left_elements+1,options)+MOD)%MOD; 557 } 558 cout<<ans<<" "; 559 } 560 cout<<nline; 561 return; 562 } 563 int main() 564 { 565 ios_base::sync_with_stdio(false); 566 cin.tie(NULL); 567 #ifndef ONLINE_JUDGE 568 freopen("input.txt", "r", stdin); 569 freopen("output.txt", "w", stdout); 570 freopen("error.txt", "w", stderr); 571 #endif 572 ll test_cases=1; 573 cin>>test_cases; 574 precompute(MOD); 575 while(test_cases--){ 576 solve(); 577 } 578 cout<<fixed<<setprecision(10); 579 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 580 } 581 ``` 582 583 [1930F - Maximize the Difference](/contest/1930/problem/F "think-cell Round 1") 584 585 Idea: [satyam343](/profile/satyam343 "Master satyam343") 586 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 587 588 **Hint 1** 589 590 Note that $\max - \min$ is just the difference of two elements, so let us first look at two numbers $y$ and $z$, where we want to maximise $(y | x) - (z | x)$. In $y - z$, the bits only present in $y$ add to the result, and the bits only present in $z$ reduce it. Setting a bit in $x$ puts it in both numbers, so that bit just stops mattering. Now, if we take $x = z$, we kill every bit that reduces the result without touching any bit that increases it, which is the best possible case. 591 592 Now take an optimal $x$, and say $b_i | x$ is the maximum and $b_j | x$ is the minimum. Switching to $x = b_j$ can't make the difference of this pair smaller, and the range of the whole array is atleast this difference, so $x = b_j$ is optimal too. Note that other values of $x$ can also be optimal, but we can always get the maximum possible value by choosing $x = b_p$ for some $p$ $(1 \le p \le m)$. 593 594 **Hint 2** 595 596 In Hint 1, we saw that a single pair $(y, z)$ gets its best answer at $x = z$. Let us see why $f(b)$ is just the best answer among all pairs. 597 598 It can't be more. Whatever $x$ we choose, $\max - \min$ is just the difference of the two elements that end up as the maximum and the minimum. That pair can't do better than its own best answer, so no $x$ can beat the best pair. 599 600 And we can actually reach it. Take the best pair $(b_i, b_j)$ and choose $x = b_j$. By Hint 1, just these two elements already give this pair's best answer, and the other elements can only stretch $\max - \min$, never shrink it. 601 602 Now, what is the answer for a pair? With $x = z$, the bits of $z$ cancel out, and we are left with exactly the bits present in $y$ but not in $z$. In other words, the answer is the maximum value $v$ such that $v \land y = v$ and $v \land z = 0$, which is $y \land {\sim} z$. Hence, 603 604 $f(b) = \max_{1 \le i, j \le m} \left(b_i \land {\sim} b_j\right),$ 605 606 where $\land$ is the bitwise AND operator and ${\sim}$ is the bitwise One's complement operator. 607 608 **Solution** 609 610 Let us see how to find $f(b)$ in $O(n \log(n))$ first. We will focus on updates later. Let us have two sets $S_1$ and $S_2$ such that 611 612 * $S_1$ contains all submasks of $b_i$ for all $1 \leq i \leq m$ 613 * $S_2$ contains all submasks of ~$b_i$for all $1 \leq i \leq m$ 614 615 We can observe that $f(b)$ is the largest element present in both sets $S_1$ and $S_2$. 616 617 Now, we can insert all submasks naively. But it would be pretty inefficient. Note that we need to insert any submask atmost once in either of the sets. 618 619 Can you think of some approach in which you efficiently insert all the non-visited submasks of some mask? 620 621 **Pseudo Code** 622 623 ``` 624 insert_submask(cur, S){ 625 return if mask cur is present in S 626 add mask cur to the set S 627 vec = list of all the set bits of the mask cur 628 for i in vec: 629 insert_submask(cur - 2^i) 630 } 631 ``` 632 633 Note that the above pseudo code inserts all the all submasks efficiently. As all the masks will be visited atmost once, the amortised complexity will be $O(n \log(n)^2)$. Note that instead of using a set, we can use a boolean array of size $n$ to reduce the complexity to $O(n \log(n))$. 634 635 Thus, we can use the above idea to find $f(b)$ in $O(n \log(n))$. For each $i$ from $1$ to $m$, we can insert all submasks of $b_i$ into set $S_1$ and insert all the submasks of ~$b_i$ into set $S_2$. 636 637 The above idea hints at how to deal with updates. If we need to append an element $z$ to $b$, we can just insert all submasks of $z$ into set $S_1$ and insert all the submasks of ~$z$ into set $S_2$. 638 639 Hence, the overall complexity is $O(n \log(n))$. 640 641 **Code** 642 643 ``` 644 #pragma GCC optimize("O3,unroll-loops") 645 #include <bits/stdc++.h> 646 #include <ext/pb_ds/tree_policy.hpp> 647 #include <ext/pb_ds/assoc_container.hpp> 648 using namespace __gnu_pbds; 649 using namespace std; 650 #define ll long long 651 #define pb push_back 652 #define mp make_pair 653 #define nline "\n" 654 #define f first 655 #define s second 656 #define pll pair<ll,ll> 657 #define all(x) x.begin(),x.end() 658 const ll MAX=100100; 659 void solve(){ 660 ll n,q; cin>>n>>q; 661 ll till=1,len=1; 662 while(till<n){ 663 till*=2; 664 len++; 665 } 666 ll ans=0; 667 vector<vector<ll>> track(2,vector<ll>(till+5,0)); 668 auto add=[&](ll x,ll p){ 669 queue<ll> trav; 670 if(track[p][x]){ 671 return; 672 } 673 trav.push(x); track[p][x]=1; 674 while(!trav.empty()){ 675 auto it=trav.front(); 676 trav.pop(); 677 if(track[0][it]&track[1][it]){ 678 ans=max(ans,it); 679 } 680 for(ll j=0;j<len;j++){ 681 if(it&(1<<j)){ 682 ll cur=(it^(1<<j)); 683 if(!track[p][cur]){ 684 track[p][cur]=1; 685 trav.push(cur); 686 } 687 } 688 } 689 } 690 }; 691 ll supermask=till-1; 692 vector<ll> a(q+5); 693 for(ll i=1;i<=q;i++){ 694 ll h; cin>>h; 695 a[i]=(h+ans)%n; 696 add(a[i],0); 697 add(supermask^a[i],1); 698 cout<<ans<<" \n"[i==q]; 699 } 700 return; 701 } 702 int main() 703 { 704 ios_base::sync_with_stdio(false); 705 cin.tie(NULL); 706 #ifndef ONLINE_JUDGE 707 freopen("input.txt", "r", stdin); 708 freopen("output.txt", "w", stdout); 709 freopen("error.txt", "w", stderr); 710 #endif 711 ll test_cases=1; 712 cin>>test_cases; 713 while(test_cases--){ 714 solve(); 715 } 716 cout<<fixed<<setprecision(10); 717 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 718 } 719 ``` 720 721 [1930G - Prefix Max Set Counting](/contest/1930/problem/G "think-cell Round 1") 722 723 Idea: [satyam343](/profile/satyam343 "Master satyam343") 724 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 725 726 **Hint 1** 727 728 Consider some subsequence $S$ of $[1,2, \ldots n]$ such that there exists atleast one pre-order $a$ such that $F(a)=S$. Look for some non-trivial properties about $S$. Node $S_i$ will be visited before the node $S_{i+1}$. 729 730 **Hint 2** 731 732 Assume $|S|=k$. First of all, we should $S_1=1$ and $S_k = n$. There cannot exists there distinct indices $a, b$ and $c$ ($1 \leq a \lt b \lt c \leq |k|$) such that $S_c$ lies on the path from $S_a$ to $S_b$. Assume $LCA_i$ is the lowest common ancestor of $S_i$ and $S_{i+1}$. For all $i$($1 \leq i \lt k$), the largest value over all the nodes on the unique path from $S_i$ to $S_{i+1}$ should be $S_{i+1}$. 733 734 **Hint 3** 735 736 Suppose $nax_p$ is the maximum value in the subtree of $p$. There is one more important restriction if $S_i$ does not lie on the path from $S_{i+1}$ to $1$. Suppose $m$ is the child of $LCA_i$, which lies on the path from $S_i$ to $LCA_i$. We should have $S_{i+1} \gt nax_m$. In fact, if you observe carefully you will realise that we should have $S_i = nax_m$. 737 738 **Solution** 739 740 Let us use dynamic programming. Suppose $dp[i]$ gives the number of valid subsequences(say $S$) such that the last element of $S$ is $i$. Note that the answer to our original problem will be $dp[n]$. 741 742 Suppose $nax(u,v)$ denotes the maximum value on the path from $u$ to $v$(including the endpoints). 743 744 Let us have a $O(n^2)$ solution first. 745 746 We have $dp[1]=1$. 747 748 Suppose we are at some node $i$($i \gt 1$), and we need to find $dp[i]$. Let us consider some node $j$($1 \le j \lt i$) and see if we can append $i$ to all the subsequences which end with node $j$. If we can append, we just need to add $dp[j]$ to $dp[i]$. 749 750 But how do we check if we can append $i$ to all the subsequences that end with node $j$? 751 752 Check hints 2 and 3. 753 754 So, we have a $n^2$ solution now. 755 756 We need to optimise it now. 757 758 We will move in the increasing value of the nodes(from $2$ to $n$) and calculate the $dp$ values. 759 760 Suppose $nax(1, par_i) = v$, where $par_i$ denotes the parent of $i$. 761 762 Assume we go from node $j$($j \lt i$) to node $i$. 763 764 There are two cases: 765 766 1. $j$ lies on the path from $1$ to $i$: This case is easy, as we just need to ensure that $nax(j,par_i) = j$. We can add $dp[j]$ to $dp[i]$ if we have $nax(j,par_i) = j$. Note that there exists only one node(node $v$) for which might add $dp[v]$ to $dp[i]$ 767 2. $j$ does not lie on the path from $1$ to $i$ : We will only consider the case in which $dp[j]$ will be added to $dp[i]$. Suppose $lca$ is the lowest common ancestor of $j$ and $i$, and $m$ is the child of $lca$, which lies on the path from $j$ to $lca$. Notice that the largest value in the subtree of $m$ should be $j$. This observation is quite helpful. We can traverse over all the ancestors of $i$. Suppose that we are at ancestor $u$. We will iterate over all the child(say $c$) of $u$ such that $nax_c \lt i$, and add $dp[nax_c]$ to $dp[i]$ if $nax(u,par_i) \lt nax_c$. Suppose $track[u][i]$ stores the sum of $dp[nax_c]$ for all $c$ such that $nax_c \lt i$. So we should add $track[u][i]$ to $dp[i]$. But there is a catch. This way, $dp[nax_c]$ will also get added $dp[i]$ even when $nax_c \lt nax(u, par_i)$. So, we need to subtract some values, which is left as an exercise for the readers. Now, $track[u][d] = track[u][d-1] + dp[nax_c]$ if $nax_c = d$. So, instead of keeping a two-dimensional array $track$, we can just maintain a one-dimensional array $track$. Note that we will only need the sum of $track[u]$ for all the ancestors of $i$, which we can easily calculate using the euler tour. 768 769 You can look at the attached code for the implementation details. 770 771 The intended time complexity is $O(n \cdot \log(n))$. 772 773 **Code** 774 775 ``` 776 #include <bits/stdc++.h> 777 #include <ext/pb_ds/tree_policy.hpp> 778 #include <ext/pb_ds/assoc_container.hpp> 779 using namespace __gnu_pbds; 780 using namespace std; 781 #define ll long long 782 #define pb push_back 783 #define mp make_pair 784 #define nline "\n" 785 #define f first 786 #define s second 787 #define pll pair<ll,ll> 788 #define all(x) x.begin(),x.end() 789 const ll MOD=998244353; 790 const ll MAX=1000100; 791 struct FenwickTree{ 792 vector<ll> bit; 793 ll n; 794 FenwickTree(ll n){ 795 this->n = n; 796 bit.assign(n, 0); 797 } 798 FenwickTree(vector<ll> a):FenwickTree(a.size()){ 799 ll x=a.size(); 800 for(size_t i=0;i<x;i++) 801 add(i,a[i]); 802 } 803 ll sum(ll r) { 804 ll ret=0; 805 for(;r>=0;r=(r&(r+1))-1){ 806 ret+=bit[r]; 807 ret%=MOD; 808 } 809 return ret; 810 } 811 ll sum(ll l,ll r) { 812 if(l>r) 813 return 0; 814 ll val=sum(r)-sum(l-1)+MOD; 815 val%=MOD; 816 return val; 817 } 818 void add(ll idx,ll delta) { 819 for(;idx<n;idx=idx|(idx+1)){ 820 bit[idx]+=delta; 821 bit[idx]%=MOD; 822 } 823 } 824 }; 825 vector<vector<ll>> adj; 826 vector<ll> tin(MAX,0),tout(MAX,0); 827 vector<ll> parent(MAX,0); 828 vector<ll> overall_max(MAX,0); 829 ll now=1; 830 vector<ll> jump_to(MAX,0),sub(MAX,0); 831 void dfs(ll cur,ll par){ 832 parent[cur]=par; 833 tin[cur]=now++; 834 overall_max[cur]=cur; 835 for(auto chld:adj[cur]){ 836 if(chld!=par){ 837 jump_to[chld]=max(jump_to[cur],cur); 838 dfs(chld,cur); 839 overall_max[cur]=max(overall_max[cur],overall_max[chld]); 840 } 841 } 842 tout[cur]=now++; 843 } 844 vector<ll> dp(MAX,0); 845 void solve(){ 846 ll n; cin>>n; 847 adj.clear(); 848 adj.resize(n+5); 849 for(ll i=1;i<=n-1;i++){ 850 ll u,v; cin>>u>>v; 851 adj[u].push_back(v); 852 adj[v].push_back(u); 853 } 854 now=1; 855 dfs(1,0); 856 ll ans=0; 857 FenwickTree enter_time(now+5),exit_time(now+5); 858 overall_max[0]=MOD; 859 dp[0]=1; 860 for(ll i=1;i<=n;i++){ 861 ll p=jump_to[i]; 862 dp[i]=(enter_time.sum(0,tin[i])-exit_time.sum(0,tin[i])-sub[p]+dp[p]+MOD+MOD)%MOD; 863 if(p>i){ 864 dp[i]=0; 865 } 866 ll node=i; 867 while(overall_max[node]==i){ 868 node=parent[node]; 869 } 870 enter_time.add(tin[node],dp[i]); 871 exit_time.add(tout[node],dp[i]); 872 sub[i]=(enter_time.sum(0,tin[i])-exit_time.sum(0,tin[i])+MOD)%MOD; 873 } 874 cout<<dp[n]<<nline; 875 return; 876 } 877 int main() 878 { 879 ios_base::sync_with_stdio(false); 880 cin.tie(NULL); 881 #ifndef ONLINE_JUDGE 882 freopen("input.txt", "r", stdin); 883 freopen("output.txt", "w", stdout); 884 freopen("error.txt", "w", stderr); 885 #endif 886 ll test_cases=1; 887 cin>>test_cases; 888 while(test_cases--){ 889 solve(); 890 } 891 cout<<fixed<<setprecision(10); 892 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 893 } 894 ``` 895 896 [1930H - Interactive Mex Tree](/contest/1930/problem/H "think-cell Round 1") 897 898 Idea: [satyam343](/profile/satyam343 "Master satyam343") 899 Editorial: [satyam343](/profile/satyam343 "Master satyam343") 900 901 **Hint 1** 902 903 $\operatorname{MEX}$ of the path from $u$ to $v$ will be the minimum value over all the nodes of $T$ which do not lie on the path from $u$ to $v$. 904 905 **Hint 2** 906 907 $p_1$ and $p_2$ are associated with the Euler tour 908 909 **Hint 3** 910 911 $p_1$ is the permutation of $[1,2, \ldots n]$ sorted in increasing order on the basis on $tin$ time observed during Euler tour. Similarly, $p_2$ is the permutation of $[1,2, \ldots n]$ sorted in increasing order based on $tout$ time. Note that any Euler tour is fine. 912 913 **Solution** 914 915 Now we have $p_1$ and $p_2$ with us. Suppose we need to find $\operatorname{MEX}$ of the path from $u$ to $v$. Assume that $tin_u \lt tin_v$ for convenience. Assume $T'$ is the forest we get if we remove all the nodes on the path from $u$ to $v$ from $T$. Our goal is to find the minimum value over all the nodes in $T'$. Assume that $T'$ is non-empty, as $\operatorname{MEX}$ will be $n$ if $T'$ is empty. Assume $LCA$ is the lowest common ancestor of $u$ and $v$. Suppose $m$ is the child of $LCA(u,v)$, which lies on the path from $v$ to $LCA(u,v)$. 916 917 Let us consider some groups of nodes $p$ such that. 918 919 1. $tout_p \lt tin_u$ 920 2. $tin_u \lt tin_p \lt tin_m$ 921 3. $tin_m \lt tout_p \lt tin_v$ 922 4. $tin_v \lt tin_p$ 923 5. $tout_{LCA} \lt tout_p$ 924 925 Note that we have precisely $5$ groups, with the $i$-th group consisting of only those nodes which satisfy the $i$-th condition. 926 927 Here comes the interesting claim. All nodes in $T'$ are present in atleast one of the above $5$ groups. There does not exist a node $p$ such that $p$ is on the path from $u$ from $v$ and $p$ is present in any of the groups. 928 929 Now, it is not hard to observe that if we consider the nodes of any group, they will form a continuous segment in either $p_1$ or $p_2$. So we can cover each group in a single query. Hence, we can find the $\operatorname{MEX}$ of the path in any round using atmost $5$ queries. 930 931 **Code** 932 933 ``` 934 #include <bits/stdc++.h> 935 #include <ext/pb_ds/tree_policy.hpp> 936 #include <ext/pb_ds/assoc_container.hpp> 937 using namespace __gnu_pbds; 938 using namespace std; 939 #define ll long long 940 const ll INF_ADD=1e18; 941 #define pb push_back 942 #define mp make_pair 943 #define nline "\n" 944 #define f first 945 #define s second 946 #define pll pair<ll,ll> 947 #define all(x) x.begin(),x.end() 948 const ll MOD=998244353; 949 const ll MAX=200200; 950 vector<ll> adj[MAX]; 951 ll now=0,till=20; 952 vector<ll> tin(MAX,0),tout(MAX,0),depth(MAX,0); 953 vector<vector<ll>> jump(MAX,vector<ll>(till+1,0)); 954 void dfs(ll cur,ll par){ 955 jump[cur][0]=par; 956 for(ll i=1;i<=till;i++) 957 jump[cur][i]=jump[jump[cur][i-1]][i-1]; 958 tin[cur]=++now; 959 for(ll chld:adj[cur]){ 960 if(chld!=par){ 961 depth[chld]=depth[cur]+1; 962 dfs(chld,cur); 963 } 964 } 965 tout[cur]=++now; 966 } 967 bool is_ancestor(ll a,ll b){ 968 if((tin[a]<=tin[b])&&(tout[a]>=tout[b])) 969 return 1; 970 return 0; 971 } 972 ll lca(ll a,ll b){ 973 if(is_ancestor(a,b)) 974 return a; 975 for(ll i=till;i>=0;i--){ 976 if(!is_ancestor(jump[a][i],b)) 977 a=jump[a][i]; 978 } 979 return jump[a][0]; 980 } 981 void solve(){ 982 ll n; cin>>n; 983 ll m; cin>>m; 984 vector<ll> a(n+5); 985 for(ll i=1;i<=n-1;i++){ 986 ll u,v; cin>>u>>v; 987 adj[u].push_back(v); 988 adj[v].push_back(u); 989 } 990 now=1; 991 dfs(1,1); 992 vector<ll> p(n),q(n); 993 for(ll i=0;i<n;i++){ 994 p[i]=q[i]=i+1; 995 } 996 sort(all(p),[&](ll l,ll r){ 997 return tin[l]<tin[r]; 998 }); 999 sort(all(q),[&](ll l,ll r){ 1000 return tout[l]<tout[r]; 1001 }); 1002 for(auto it:p){ 1003 cout<<it<<" "; 1004 } 1005 cout<<endl; 1006 for(auto it:q){ 1007 cout<<it<<" "; 1008 } 1009 cout<<endl; 1010 auto query_p=[&](ll l,ll r){ 1011 ll left_pos=n+1,right_pos=-1; 1012 for(ll i=0;i<n;i++){ 1013 ll node=p[i]; 1014 if((tin[node]>=l) and (tin[node]<=r)){ 1015 left_pos=min(left_pos,i); 1016 right_pos=i; 1017 } 1018 } 1019 ll now=n+5; 1020 if(right_pos!=-1){ 1021 left_pos++,right_pos++; 1022 cout<<"? 1 "<<left_pos<<" "<<right_pos<<endl; 1023 cin>>now; 1024 } 1025 return now; 1026 }; 1027 auto query_q=[&](ll l,ll r){ 1028 ll left_pos=n+1,right_pos=-1; 1029 for(ll i=0;i<n;i++){ 1030 ll node=q[i]; 1031 if((tout[node]>=l) and (tout[node]<=r)){ 1032 left_pos=min(left_pos,i); 1033 right_pos=i; 1034 } 1035 } 1036 ll now=n+5; 1037 if(right_pos!=-1){ 1038 left_pos++,right_pos++; 1039 cout<<"? 2 "<<left_pos<<" "<<right_pos<<endl; 1040 cin>>now; 1041 } 1042 return now; 1043 }; 1044 while(m--){ 1045 ll u,v; cin>>u>>v; 1046 if(tout[u]>tout[v]){ 1047 swap(u,v); 1048 } 1049 ll lca_node=lca(u,v); 1050 ll ans=n; 1051 if(lca_node==v){ 1052 ans=min(ans,query_q(1,tin[u])); 1053 ans=min(ans,query_p(tin[u]+1,tout[v])); 1054 ans=min(ans,query_q(tout[v]+1,now)); 1055 cout<<"! "<<ans<<endl; 1056 ll x; cin>>x; 1057 continue; 1058 } 1059 ans=min(ans,query_q(1,tin[u])); 1060 ll consider=v; 1061 for(auto it:adj[lca_node]){ 1062 if(is_ancestor(lca_node,it) and is_ancestor(it,v)){ 1063 consider=it; 1064 } 1065 } 1066 ans=min(ans,query_p(tin[u]+1,tin[consider]-1)); 1067 ans=min(ans,query_q(tin[consider],tin[v])); 1068 ans=min(ans,query_p(tin[v]+1,tout[lca_node])); 1069 ans=min(ans,query_q(tout[lca_node]+1,now)); 1070 cout<<"! "<<ans<<endl; 1071 ll x; cin>>x; 1072 } 1073 for(ll i=1;i<=n;i++){ 1074 adj[i].clear(); 1075 } 1076 return; 1077 } 1078 int main() 1079 { 1080 ios_base::sync_with_stdio(false); 1081 cin.tie(NULL); 1082 #ifndef ONLINE_JUDGE 1083 freopen("input.txt", "r", stdin); 1084 freopen("output.txt", "w", stdout); 1085 freopen("error.txt", "w", stderr); 1086 #endif 1087 ll test_cases=1; 1088 cin>>test_cases; 1089 while(test_cases--){ 1090 solve(); 1091 } 1092 cout<<fixed<<setprecision(10); 1093 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 1094 } 1095 ``` 1096 1097 [1930I - Counting Is Fun](/contest/1930/problem/I "think-cell Round 1") 1098 1099 Idea: [satyam343](/profile/satyam343 "Master satyam343") 1100 Full Solution: [Elegia](/profile/Elegia "Legendary Grandmaster Elegia") 1101 Editorial: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 1102 1103 **Hint 1** 1104 1105 [A167510](https://oeis.org/A167510) 1106 1107 **Solution** 1108 1109 It is convinient here to assign weights to $\mathtt{0} \to -1$ and $\mathtt{1} \to 1$. 1110 1111 Given a string $t$, we can define the prefix sum $p$ of it's weights. For example, if $t=\mathtt{0010111}$, then $p=[0,-1,-2,-1,-2,-1,0,1]$. So that if $t$ is bad and $i$ is a index that violates the definition, then $\max(p_0,p_1,\ldots,p_{i-1}) \lt \min(p_i,p_{i+1},\ldots,p_n)$ if $s_i = \mathtt{0}$ or $\min(p_0,p_1,\ldots,p_{i-1}) \gt \max(p_i,p_{i+1},\ldots,p_n)$ if $s_i = \mathtt{1}$. 1112 1113 Naturally, it is convinient to assume that $p_0 \lt p_n$. All string with $p_0 = p_n$ are clearly good and $p_0 \gt p_n$ is handled similarly. For strings with $p_0 \lt p_n$, the condition can only be violated on an index with $s_i = \mathtt{0}$. 1114 1115 The solution works using PIE. Let us fix a set of positions $I$ that are bad, so that if $i \in I$, then $s_i =\mathtt{0}$ and $\max(p_0,p_1,\ldots,p_{i-1}) \lt \min(p_i,p_{i+1},\ldots,p_n)$. Then we need to count the number of ways to construct $p$ satisfying these conditions and then add it to the answer multiplied by $(-1)^{|I|}$. 1116 1117 Suppose that $I = i_1,i_2,\ldots,i_k$. $t[1,i_1]$ and $t[i_k,n]$ need to be a ballot sequence of length $i_1-1$ and $n-i_k$ respectively (A001405, denote it as $f(n)$) while $t[i_j,i_{j+1}]$ needs to be bidirectional ballot sequence of length $i_{j+1}-i_j-1$ (A167510, denote it as $g(n)$). Note that in our definition of ballot sequence, we are do not require that prefixes and suffixes have strictly more $\mathtt{1}$ s thatn $\mathtt{0}$ s. It is the same sequence, but note that we need to shift it by a few places when refering to OEIS. 1118 1119 The first $n$ terms of $f$ is easily computed in linear time. We will focus on how to compute the first $n$ terms of $g$ in $O(n \log^2 n)$. 1120 1121 **Computing $g(n)$** Firstly, let us consider the number of bidirectional sequences with $\frac{n+k}{2}$ $\mathtt{1}$ s and $\frac{n-k}{2}$ $\mathtt{0}$ s. We will imagine this as lattice walks from $(0,0)$ to $(n,k)$ where $\mathtt{1} \to (1,1)$ and $\mathtt{0} \to (1,-1)$. If we touch the lines $y=-1$ or $y=k+1$, the walk is invalid. 1122 1123 We can use the reflection method here, similar to a proof of Catalan. The number of valid walks is $#(*) - #(T) + #(TB) - #(TBT) ..... - #(B) + #(BT) - #(BTB) + .....$ where $#(BTB)$ denotes the number of walks that touch the bottom line, then the top line, then the bottom line, and then may continue to touch the top and bottom line after that. 1124 1125 We have $#(*) =$ $\binom{n}{\frac{n+k}{2}}$, $#(T) =$ $ \binom{n}{\frac{n+k+2}{2}}$, $#(TB) =$ $ \binom{n}{\frac{n+3k+4}{2}}$, $#(TBT) =$ $ \binom{n}{\frac{n+3k+6}{2}}$, $\ldots$, $#(B) = $ $\binom{n}{\frac{n+k+2}{2}}$, $#(BT) =$ $ \binom{n}{\frac{n+k+4}{2}}$, $#(BTB) =$ $ \binom{n}{\frac{n+3k+6}{2}}$, $\ldots$ 1126 1127 This already gives us a method to compute $g(n)$ in $O(n \log n)$ since for a fixed $k$, we can compute the above sum in $O(\frac{n}{k})$, since only the first $O(\frac{n}{k})$ terms are not $0$. 1128 1129 First, notice that we can aggregate them sums without iterating on $k$, for some fixed $j$, we can find the coefficient $c_j$ of $\binom{n}{\frac{n+j}{2}}$ across all $k$. Notice that this coefficient is independent across all $n$, so we only need to compute $c$ once. 1130 1131 Now, note that $\binom{n}{\frac{n+z}{2}} = [x^z] (x^{-1} + x) ^ n$. So that $g(n) = [x^0] C \cdot (x^{-1} + x)^n$, where $C$ is the ogf of $c$. 1132 1133 From this formulation, we can describe how to compute the first $n$ terms of $g$ in $O(n \log^2 n)$ using Divide and Conquer. 1134 1135 $DnC(l,r,V)$ computes the $g(l) \ldots g(r)$ where $V$ is the coefficents between $[l-r,r-l]$ of $C \cdot (x^{-1} + x)^l$. $DnC(l,r,V)$ will call $DnC(l,m,V)$ and $DnC(m+1,r,V \cdot (x^{-1}+x)^{m-l+1})$. We have the reccurence $T(n) = 2 T(\frac{n}{2}) + O(n \log n)$ so $T(n) = O(n \log^2 n)$. 1136 1137 Of course, for constant time speedup, you can choose to split the odd and even coefficients, but that is not needed. 1138 1139 It is possible to compute the first $n$ of $g$ in $O(n \log n)$ but it does not improve the overall complexity of the solution. 1140 1141 **Final Steps** 1142 1143 Now that we obtained the $n$ terms of $f$ and $g$, let us return to the origial problem. 1144 1145 If $s_i =\mathtt{0}$, define $dp_i = f(i-1) - \sum\limits_{s_j = \mathtt{0}} dp_j \cdot g(j-i-1)$. Then this contributes $f(n-i) \cdot dp_i$ to the number of bad strings. 1146 1147 Again, we will use Divide and Conquer to perform this quickly. 1148 1149 Briefly, $DnC(l,r)$ will compute the values of $dp[l,r]$ given that contributions from $dp[1,l-1]$ has been transferred to $dp[l,r]$ already. 1150 1151 We will call $DnC(l,m)$, compute the contribution from $dp[l,m]$ to $dp[m+1,r]$ using FFT and then call $DnC(m+1,r)$. The complexity of this is $O(n \log^2 n)$. 1152 1153 **Code(errorgorn)** 1154 1155 ``` 1156 #include <bits/stdc++.h> 1157 using namespace std; 1158 1159 #define int long long 1160 #define ll long long 1161 #define ii pair<int,int> 1162 #define iii tuple<int,int,int> 1163 #define fi first 1164 #define se second 1165 #define endl '\n' 1166 #define debug(x) cout << #x << ": " << x << endl 1167 1168 #define pub push_back 1169 #define pob pop_back 1170 #define puf push_front 1171 #define pof pop_front 1172 #define lb lower_bound 1173 #define ub upper_bound 1174 1175 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 1176 #define all(x) (x).begin(),(x).end() 1177 #define sz(x) (int)(x).size() 1178 1179 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 1180 1181 const int MOD=998244353; 1182 1183 ll qexp(ll b,ll p,int m){ 1184 ll res=1; 1185 while (p){ 1186 if (p&1) res=(res*b)%m; 1187 b=(b*b)%m; 1188 p>>=1; 1189 } 1190 return res; 1191 } 1192 1193 ll inv(ll i){ 1194 return qexp(i,MOD-2,MOD); 1195 } 1196 1197 ll fix(ll i){ 1198 i%=MOD; 1199 if (i<0) i+=MOD; 1200 return i; 1201 } 1202 1203 ll fac[1000005]; 1204 ll ifac[1000005]; 1205 1206 ll nCk(int i,int j){ 1207 if (i<j) return 0; 1208 return fac[i]*ifac[j]%MOD*ifac[i-j]%MOD; 1209 } 1210 1211 const ll mod = (119 << 23) + 1, root = 62; // = 998244353 1212 // For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21 1213 // and 483 << 21 (same root). The last two are > 10^9. 1214 typedef vector<ll> vl; 1215 void ntt(vl &a) { 1216 int n = sz(a), L = 31 - __builtin_clz(n); 1217 static vl rt(2, 1); 1218 for (static int k = 2, s = 2; k < n; k *= 2, s++) { 1219 rt.resize(n); 1220 ll z[] = {1, qexp(root, mod >> s, mod)}; 1221 rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod; 1222 } 1223 vector<int> rev(n); 1224 rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2; 1225 rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]); 1226 for (int k = 1; k < n; k *= 2) 1227 for (int i = 0; i < n; i += 2 * k) rep(j,0,k) { 1228 ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j]; 1229 a[i + j + k] = ai - z + (z > ai ? mod : 0); 1230 ai += (ai + z >= mod ? z - mod : z); 1231 } 1232 } 1233 vl conv(const vl &a, const vl &b) { 1234 if (a.empty() || b.empty()) return {}; 1235 int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B; 1236 int inv = qexp(n, mod - 2, mod); 1237 vl L(a), R(b), out(n); 1238 L.resize(n), R.resize(n); 1239 ntt(L), ntt(R); 1240 rep(i,0,n) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod; 1241 ntt(out); 1242 return {out.begin(), out.begin() + s}; 1243 } 1244 1245 int n; 1246 string s; 1247 1248 int c[100005]; 1249 int f[100005]; 1250 1251 void calc(int l,int r,vector<int> v){ 1252 while (sz(v)>(r-l)*2+1) v.pob(); 1253 1254 if (l==r){ 1255 f[l]=v[0]; 1256 return; 1257 } 1258 1259 int m=l+r>>1; 1260 1261 calc(l,m,vector<int>(v.begin()+(r-m),v.end())); 1262 vector<int> a; 1263 int t=m-l+1; 1264 rep(x,0,t+1) a.pub(nCk(t,x)),a.pub(0); 1265 1266 v=conv(v,a); 1267 calc(m+1,r,vector<int>(v.begin()+(2*t),v.end())); 1268 } 1269 1270 int ans[100005]; 1271 1272 void solve(int l,int r){ 1273 if (l==r) return; 1274 int m=l+r>>1; 1275 solve(l,m); 1276 auto a=conv(vector<int>(ans+l,ans+m+1),vector<int>(f,f+(r-l))); 1277 rep(x,m+1,r+1) if (s[x]=='0') ans[x]=fix(ans[x]-a[x-1-l]); 1278 solve(m+1,r); 1279 } 1280 1281 signed main(){ 1282 ios::sync_with_stdio(0); 1283 cin.tie(0); 1284 cout.tie(0); 1285 cin.exceptions(ios::badbit | ios::failbit); 1286 1287 fac[0]=1; 1288 rep(x,1,1000005) fac[x]=fac[x-1]*x%MOD; 1289 ifac[1000004]=inv(fac[1000004]); 1290 rep(x,1000005,1) ifac[x-1]=ifac[x]*x%MOD; 1291 1292 rep(x,1,100005){ 1293 c[x]++; 1294 1295 int curr=x; 1296 while (curr<100005){ 1297 if (curr+2<100005) c[curr+2]-=2; 1298 if (curr+4<100005) c[curr+4]++; 1299 if (curr+2*x+4<100005) c[curr+2*x+4]++; 1300 curr+=2*x+4; 1301 } 1302 } 1303 1304 cin>>n; 1305 cin>>s; 1306 1307 vector<int> v; 1308 rep(x,n+1,1) v.pub(fix(c[x]+(x>=2?c[x-2]:0LL))); 1309 calc(1,n,v); 1310 f[0]=1; 1311 1312 int fin=qexp(2,n,MOD); 1313 rep(_,0,2){ 1314 rep(x,0,n) ans[x]=(s[x]=='0')?nCk(x,x/2):0LL; 1315 solve(0,n-1); 1316 rep(x,0,n) if (s[x]=='0') fin=fix(fin-ans[x]*nCk((n-x-1),(n-x-1)/2)); 1317 1318 for (auto &it:s) it^=1; 1319 } 1320 1321 cout<<fin<<endl; 1322 } 1323 ```