1925.md (38089B)
1 Source: https://codeforces.com/blog/entry/125137 2 3 I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that we can improve upon them the next time. 4 5 #### [2A. We Got Everything Covered!](https://codeforces.com/contest/1925/problem/A) 6 7 Author: [JaySharma1048576](/profile/JaySharma1048576 "Master JaySharma1048576") 8 9 **Hint 1** 10 11 The smallest length for such a string is $n\cdot k$. 12 13 **Tutorial** 14 15 The smallest length possible for such a string is $n\cdot k$. 16 17 **Why?** 18 19 To have the string $\texttt{aaa}\ldots\texttt{a}$ as a subsequence, you need to have at least $n$ characters in the string as $\texttt{a}$. Similarly for all $k$ different characters. So, that gives a total length of at least $n\cdot k$. 20 21 In fact, it is always possible to construct a string of length $n\cdot k$ that satisfies this property. One such string is $(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)\ldots n$ times where $a_i$ is the $i^{th}$ letter of English alphabet. For example, the answer for $n=3,k=4$ can be $\texttt{abcdabcdabcd}$. It is not hard to see that the first letter of the subsequence can be from the first group of $k$ letters, second letter from the second group and so on. 22 23 **Solution** 24 25 ``` 26 #include <bits/stdc++.h> 27 using namespace std; 28 29 int main() 30 { 31 int tc; 32 cin >> tc; 33 while(tc--) 34 { 35 int n,k; 36 cin >> n >> k; 37 for(int i=0;i<n;i++) 38 for(char c='a';c<'a'+k;c++) 39 cout << c; 40 cout << '\n'; 41 } 42 } 43 ``` 44 45 **Feedback** 46 47 * Good problem: 48 * Ok problem: 49 * Bad problem: 50 * Did not attempt: 51 52 #### [2B. A Balanced Problemset?](https://codeforces.com/contest/1925/problem/B) 53 54 Author: [JaySharma1048576](/profile/JaySharma1048576 "Master JaySharma1048576") 55 56 **Hint 1** 57 58 $GCD(a_1,a_2,a_3,\ldots,a_n) = GCD(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,a_1+a_2+a_3+\ldots+a_n)$ 59 60 **Hint 2** 61 62 The maximum GCD that can be achieved is always a divisor of $x$. 63 64 **Tutorial** 65 66 Let the difficulties of the $n$ sub-problems be $a_1,a_2,a_3,\ldots,a_n$. By properties of GCD, $GCD(a_1,a_2,a_3,\ldots,a_n)$ $= GCD(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,a_1+a_2+a_3+\ldots+a_n)$ $= GCD(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,x)$. So, the final answer will always be a divisor of $x$. 67 68 Now, consider a divisor $d$ of $x$. If $n\cdot d\leq x$, you can choose the difficulties of the sub-problems to be $d,d,d,\ldots,x-(n-1)d$ each of which is a multiple of $d$ and hence, the balance of this problemset will be $d$. Otherwise you cannot choose the difficulties of $n$ sub-problems such that each of them is a multiple of $d$. 69 70 Find the maximum $d$ for which this condition holds. This can be done in $\mathcal{O}(\sqrt{x})$ using trivial factorization. 71 72 **Solution** 73 74 ``` 75 #include <bits/stdc++.h> 76 using namespace std; 77 78 int main() 79 { 80 int tc; 81 cin >> tc; 82 while(tc--) 83 { 84 int x,n; 85 cin >> x >> n; 86 int ans = 1; 87 for(int i=1;i*i<=x;i++) 88 { 89 if(x%i==0) 90 { 91 if(n<=x/i) 92 ans=max(ans,i); 93 if(n<=i) 94 ans=max(ans,x/i); 95 } 96 } 97 cout << ans << '\n'; 98 } 99 } 100 ``` 101 102 **Feedback** 103 104 * Good problem: 105 * Ok problem: 106 * Bad problem: 107 * Did not attempt: 108 109 #### [2C/1A. Did We Get Everything Covered?](https://codeforces.com/contest/1924/problem/A) 110 111 Author: [JaySharma1048576](/profile/JaySharma1048576 "Master JaySharma1048576") 112 113 **Hint 1** 114 115 Try to build the counter-case greedily. 116 117 **Hint 2** 118 119 While building the counter-case, it is always optimal to choose the first character as the one whose first index of occurrence in the given string is the highest. 120 121 **Tutorial** 122 123 We will try to construct a counter-case. If we can't the answer is `YES` otherwise `NO`. 124 125 We will greedily construct the counter-case. It is always optimal to choose the first character of our counter-case as the character (among the first $k$ English alphabets) whose first index of occurrence in $s$ is the highest. Add this character to our counter-case, remove the prefix up to this character from $s$ and repeat until the length of the counter-case reaches $n$ or we reach the end of $s$. 126 127 If the length of the counter-case is less than $n$, find a character which does not appear in the last remaining suffix of $s$. Keep adding this character to the counter-case until its length becomes $n$. This is a valid string which does not occur as a subsequence of $s$. 128 129 Otherwise, all possible strings of length $n$ formed using the first $k$ English alphabets occur as a subsequence of $s$. 130 131 **Solution** 132 133 ``` 134 #include <bits/stdc++.h> 135 using namespace std; 136 137 int main() 138 { 139 std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); 140 int t; 141 cin>>t; 142 while(t--) 143 { 144 int n, k, m; 145 cin>>n>>k>>m; 146 string s; 147 cin>>s; 148 string res=""; 149 bool found[k]; 150 memset(found, false, sizeof(found)); 151 int count=0; 152 for(char c:s) 153 { 154 if(res.size()==n) 155 break; 156 count+=(!found[c-'a']); 157 found[c-'a']=true; 158 if(count==k) 159 { 160 memset(found, false, sizeof(found)); 161 count=0; 162 res+=c; 163 } 164 } 165 if(res.size()==n) 166 cout<<"YES\n"; 167 else 168 { 169 cout<<"NO\n"; 170 for(int i=0;i<k;i++) 171 { 172 if(!found[i]) 173 { 174 while(res.size()<n) 175 res+=(char)('a'+i); 176 } 177 } 178 cout<<res<<"\n"; 179 } 180 } 181 } 182 ``` 183 184 **Fun fact** 185 186 This problem is essentially "Implement the checker for Div. 2A". It was not among the problems that were initially proposed for the round. While preparing problem 2A, I realized that writing the checker in itself might be a more interesting problem compared to 2A. 187 188 **Feedback** 189 190 * Good problem: 191 * Ok problem: 192 * Bad problem: 193 * Did not attempt: 194 195 #### [2D. Good Trip](https://codeforces.com/contest/1925/problem/D) 196 197 Author: [yash_daga](/profile/yash_daga "Grandmaster yash_daga") 198 199 **Hint 1** 200 201 Since expected value is linear, we can consider the contribution of initial friendship values and the contribution of increase in friendship values by repeated excursions independently. 202 203 **Hint 2** 204 205 Contribution of the initial friendship values will be $\dfrac{k\times \sum_{i=1}^{n}f_i}{\binom{n}{2}}$. 206 207 **Hint 3** 208 209 Now we can assume that there are $m$ pair of friends out of a total of $\binom{n}{2}$ pairs of students whose initial friendship value is $0$. 210 211 **Tutorial** 212 213 Since expected value is linear, we can consider the contribution of initial friendship values and the contribution of increase in friendship values by repeated excursions independently. 214 215 Let $d=\binom{n}{2}$ denote the total number of pairs of students that can be formed. 216 217 Contribution of the initial friendship values will be $s=\dfrac{k\cdot \sum_{i=1}^{n}f_i}{d}$. 218 219 Now, to calculate the contribution to the answer by the increase in friendship values due to excursions, for each pair of friends, it will be $\sum_{x=0}^{k}\dfrac{x(x-1)}{2}\cdot P(x)$ where $P(x)$ is the probability of a pair of friends to be selected for exactly $x$ out of the $k$ excursions which is given by $P(x)=\binom{k}{x}\cdot \bigg(\dfrac{1}{d}\bigg)^{x}\cdot \bigg(\dfrac{d-1}{d}\bigg)^{k-x}$. 220 221 Since the increase is uniform for all pair of friends, we just have to multiply this value by $m$ and add it to the answer. 222 223 The time complexity is $\mathcal{O}(m+k\log k)$ per test case. 224 225 **Solution** 226 227 ``` 228 #include <bits/stdc++.h> 229 #define int long long 230 #define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); 231 #define mod 1000000007ll 232 using namespace std; 233 const long long N=200005, INF=2000000000000000000; 234 235 int power(int a, int b, int p) 236 { 237 if(b==0) 238 return 1; 239 if(a==0) 240 return 0; 241 int res=1; 242 a%=p; 243 while(b>0) 244 { 245 if(b&1) 246 res=(1ll*res*a)%p; 247 b>>=1; 248 a=(1ll*a*a)%p; 249 } 250 return res; 251 } 252 int fact[N],inv[N]; 253 void pre() 254 { 255 fact[0]=1; 256 inv[0]=1; 257 for(int i=1;i<N;i++) 258 fact[i]=(i*fact[i-1])%mod; 259 for(int i=1;i<N;i++) 260 inv[i]=power(fact[i], mod-2, mod); 261 } 262 int nCr(int n, int r, int p) 263 { 264 if(r>n || r<0) 265 return 0; 266 if(n==r) 267 return 1; 268 if (r==0) 269 return 1; 270 return (((fact[n]*inv[r]) % p )*inv[n-r])%p; 271 } 272 int32_t main() 273 { 274 IOS; 275 pre(); 276 int t; 277 cin>>t; 278 while(t--) 279 { 280 int n, m, k; 281 cin>>n>>m>>k; 282 int sum=0; 283 for(int i=0;i<m;i++) 284 { 285 int a, b, f; 286 cin>>a>>b>>f; 287 sum=(sum + f)%mod; 288 } 289 int den=((n*(n-1))/2ll)%mod; 290 int den_inv=power(den, mod-2, mod); 291 int base=(((sum*k)%mod)*den_inv)%mod; 292 int avg_inc=0; 293 for(int i=1;i<=k;i++) 294 { 295 // Extra sum added to ans if a particular pair of friends is picked i times. 296 int sum=((i*(i-1))/2ll)%mod; 297 int prob = (nCr(k, i, mod)*power(den_inv, i, mod))%mod; 298 // Probablity that a particular pair in unpicked for a given excursion. 299 int unpicked_prob = ((den-1)*den_inv)%mod; 300 // Probability that a particular pair is picked exactly i times. 301 prob=(prob * power(unpicked_prob, k-i, mod))%mod; 302 avg_inc = (avg_inc + (sum*prob)%mod)%mod; 303 } 304 int ans = (base + (m*avg_inc)%mod)%mod; 305 cout<<ans<<'\n'; 306 } 307 } 308 ``` 309 310 **Feedback** 311 312 * Good problem: 313 * Ok problem: 314 * Bad problem: 315 * Did not attempt: 316 317 #### [2E/1B. Space Harbour](https://codeforces.com/contest/1924/problem/B) 318 319 Author: [yash_daga](/profile/yash_daga "Grandmaster yash_daga") 320 321 **Hint** 322 323 Segment Tree with Lazy Propogation 324 325 **Tutorial** 326 327 We can maintain a segment tree of size $n$ which initially stores the cost of all the ships. 328 329 Now there are 2 types of updates when we add an harbour: 330 331 * The ships to the left of the new harbour have their cost decreased by a fixed amount. 332 * The ships to the right of the harbour have their cost changed by the value equivalent to product of distance from the harbour on their right (which remains unchanged) and the difference in values of the previous and new harbour to their left. 333 334 **Example of updates** 335 336 Let $n=8$ and there be harbours on point $1$ and $8$ with values $10$ and $15$ respectively. 337 Now we add a harbour at point $x=4$ with value $5$. 338 339 * Case 1: $(x=2, 3)$ Cost for both ships get decreased by $10 \times (8-4)$ 340 * Case 2: $(x=5,6,7)$ Cost for the ships get increased by $(5-10) \times 3, (5-10) \times 2, (5-10) \times 1$ respectively. 341 342 There are multiple ways to handle both the updates simultaneously, a simple way would be to use a struct simulating an arithmetic progression. It can contain two values 343 344 * Base: Simply a value which has to be added to all values belonging to the segment. 345 * Difference: For each node of the segment, $dif \times dist$ will be added to the node, where $dist$ is the distance of node from the end of the segment. 346 347 Using summation of arithmetic progression we can make sure that the updates on Difference can be applied to an entire segment lazily. You can see the code for more details. 348 349 **Solution** 350 351 ``` 352 #include <bits/stdc++.h> 353 #define int long long 354 #define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); 355 using namespace std; 356 const long long N=300005; 357 358 struct ap { 359 int base, dif; 360 }; 361 362 ap add(ap a, ap b) 363 { 364 ap res; 365 res.base = a.base + b.base; 366 res.dif = a.dif + b.dif; 367 return res; 368 } 369 370 int convert(ap a, int n) 371 { 372 int res = (n*a.base); 373 res += ((n*(n-1))/2ll)*a.dif; 374 return res; 375 } 376 377 int st[4*N], cost[N]; 378 ap lazy[4*N]; 379 ap zero = {0, 0}; 380 381 void propogate(int node, int l, int r) 382 { 383 st[node] += convert(lazy[node], r-l+1); 384 if(l!=r) 385 { 386 lazy[node*2+1] = add(lazy[node*2+1], lazy[node]); 387 int mid = (l+r)/2; 388 int rig = (r-mid); 389 lazy[node].base += (rig*lazy[node].dif); 390 lazy[node*2] = add(lazy[node*2], lazy[node]); 391 } 392 lazy[node] = zero; 393 } 394 void build(int node, int l, int r) 395 { 396 if(l==r) 397 { 398 st[node] = cost[l]; 399 lazy[node] = zero; 400 return; 401 } 402 int mid=(l+r)/2; 403 build(node*2, l, mid); 404 build(node*2+1, mid+1, r); 405 st[node] = (st[node*2] + st[node*2+1]); 406 lazy[node] = zero; 407 return; 408 } 409 void update(int node, int l, int r, int x, int y, ap val) 410 { 411 if(lazy[node].base != 0 || lazy[node].dif != 0) 412 propogate(node, l, r); 413 if(y<x||x>r||y<l) 414 return; 415 if(l>=x&&r<=y) 416 { 417 st[node] += convert(val, r-l+1); 418 if(l!=r) 419 { 420 lazy[node*2+1] = add(lazy[node*2+1], val); 421 int mid = (l+r)/2; 422 int rig = (r-mid); 423 val.base += (rig*val.dif); 424 lazy[node*2] = add(lazy[node*2], val); 425 } 426 return; 427 } 428 int mid=(l+r)/2; 429 update(node*2+1, mid+1, r, x, y, val); 430 if(y>mid) 431 { 432 int rig = (min(y, r)-mid); 433 val.base += (rig*val.dif); 434 } 435 update(node*2, l, mid, x, y, val); 436 st[node] = st[node*2] + st[node*2+1]; 437 return; 438 } 439 int query(int node, int l, int r, int x, int y) 440 { 441 if(lazy[node].base != 0 || lazy[node].dif != 0) 442 propogate(node, l, r); 443 if(y<x||y<l||x>r) 444 return 0; 445 if(l>=x&&r<=y) 446 return st[node]; 447 int mid=(l+r)/2; 448 return query(node*2, l, mid, x, y) + query(node*2+1, mid+1, r, x, y); 449 } 450 451 int32_t main() 452 { 453 IOS; 454 int n, m, q; 455 cin>>n>>m>>q; 456 set <int> harbours; 457 int X[m], V[n+1]; 458 for(int i=0;i<m;i++) 459 { 460 cin>>X[i]; 461 harbours.insert(X[i]); 462 } 463 for(int i=0;i<m;i++) 464 { 465 int v; 466 cin>>v; 467 cost[X[i]] = v; 468 V[X[i]] = v; 469 } 470 for(int i=1;i<=n;i++) 471 { 472 if(cost[i] == 0) 473 cost[i] = cost[i-1]; 474 } 475 int dist=0; 476 for(int i=n;i>0;i--) 477 { 478 if(harbours.find(i) != harbours.end()) 479 dist=0; 480 else 481 dist++; 482 cost[i] *= dist; 483 } 484 build(1, 1, n); 485 while(q--) 486 { 487 int typ; 488 cin>>typ; 489 if(typ == 1) 490 { 491 int x, v; 492 cin>>x>>v; 493 V[x] = v; 494 auto it = harbours.lower_bound(x); 495 int nxt = (*it); 496 it--; 497 int prev = (*it); 498 ap lef = {(V[prev]*(x-nxt)), 0}; 499 ap rig = {0, V[x]-V[prev]}; 500 update(1, 1, n, prev+1, x, lef); 501 update(1, 1, n, x+1, nxt, rig); 502 harbours.insert(x); 503 } 504 else 505 { 506 int l, r; 507 cin>>l>>r; 508 cout<<query(1, 1, n, l, r)<<'\n'; 509 } 510 } 511 } 512 ``` 513 514 **Feedback** 515 516 * Good problem: 517 * Ok problem: 518 * Bad problem: 519 * Did not attempt: 520 521 #### [2F/1C. Fractal Origami](https://codeforces.com/contest/1924/problem/C) 522 523 Author: [mexomerf](/profile/mexomerf "Candidate Master mexomerf") 524 525 **Hint 1** 526 527 You need more math and less paper :) 528 529 **Hint 2** 530 531 The length of mountain crease lines and valley crease lines created in each operation is the same, except for the first operation. 532 533 **Tutorial** 534 535 Let there be an upside of the paper and a downside of the paper, initially the upside of the paper is facing up. With a little imagination, we can see that the mountain crease lines on the upside of the paper will be valley crease lines on the downside of the paper, and vice versa. 536 537  538 539 Grey is the upside and orange is the downside 540 541 After the first operation, what once was a single layer of square paper turns into a square with two overlapping layers of paper. The layer at the bottom has its upside facing up, and the layer at the top has its downside facing up. 542 543 After this first operation, whatever crease lines are formed on the upside of the bottom layer will be the same as the ones formed on the bottom layer of the top layer, which means when the paper is unfolded and the upside of the entire paper is facing up, the mountain crease lines and the valley crease lines created after the first operation will be equal. 544 545 Let $M$ be the length of mountain crease lines and $V$ be the length of valley crease lines after $N$ moves, and the side of the square paper is $1$. 546 547 Let $diff = V - M = $ Length of valley crease lines created in the first operation $ = 2\sqrt{2}$. 548 549 It is easy to calculate the total crease lines that are created (mountain and valley) in $N$ operations. It is the sum of a GP. 550 551 Let $sum = V + M = {\displaystyle\sum_{i = 1}^{N}}2^{i - 1}\cdot2\sqrt{2}\cdot{(\dfrac{1}{\sqrt{2}})}^{i - 1} = {\displaystyle\sum_{i = 1}^{N}}(\sqrt{2})^{i + 2}$ 552 553 Now to find $\dfrac{M}{V}$, we use the age-old componendo and dividendo. 554 555 $\dfrac{M}{V} = \dfrac{sum - diff}{sum + diff}$ 556 557 And then rationalize it to find the coefficient of $\sqrt{2}$. 558 559 **Why unusual modulo?** 560 561 The reason for the uncommon modulo in the problem is that the irrational part of $\dfrac{M}{V}$ is of the form $\dfrac{a\sqrt{2}}{b^2 - 2}$, where $a$ and $b$ are some integers. If there exists any $b$ such that $b^2 \equiv 2 \pmod m$, then the denominator becomes $0$. 562 563 To avoid this situation, such a prime modulo $m$ was taken for which $2$ is not a [quadratic residue](https://en.wikipedia.org/wiki/Quadratic_residue) modulo $m$. It can be seen that $999999893\bmod 8 = 5$ and so, the [Legendre symbol](https://en.m.wikipedia.org/wiki/Legendre_symbol) $\bigg(\dfrac{2}{999999893}\bigg) = -1$ meaning that $2$ is a quadratic non-residue modulo $999999893$. 564 565 **Solution** 566 567 ``` 568 // library link: https://github.com/manan-grover/My-CP-Library/blob/main/library.cpp 569 #include <bits/stdc++.h> 570 #include <ext/pb_ds/assoc_container.hpp> 571 #include <ext/pb_ds/tree_policy.hpp> 572 using namespace std; 573 using namespace __gnu_pbds; 574 #define asc(i,a,n) for(I i=a;i<n;i++) 575 #define dsc(i,a,n) for(I i=n-1;i>=a;i--) 576 #define forw(it,x) for(A it=(x).begin();it!=(x).end();it++) 577 #define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++) 578 #define pb push_back 579 #define mp make_pair 580 #define fi first 581 #define se second 582 #define lb(x) lower_bound(x) 583 #define ub(x) upper_bound(x) 584 #define fbo(x) find_by_order(x) 585 #define ook(x) order_of_key(x) 586 #define all(x) (x).begin(),(x).end() 587 #define sz(x) (I)((x).size()) 588 #define clr(x) (x).clear() 589 #define U unsigned 590 #define I long long int 591 #define S string 592 #define C char 593 #define D long double 594 #define A auto 595 #define B bool 596 #define CM(x) complex<x> 597 #define V(x) vector<x> 598 #define P(x,y) pair<x,y> 599 #define OS(x) set<x> 600 #define US(x) unordered_set<x> 601 #define OMS(x) multiset<x> 602 #define UMS(x) unordered_multiset<x> 603 #define OM(x,y) map<x,y> 604 #define UM(x,y) unordered_map<x,y> 605 #define OMM(x,y) multimap<x,y> 606 #define UMM(x,y) unordered_multimap<x,y> 607 #define BS(x) bitset<x> 608 #define L(x) list<x> 609 #define Q(x) queue<x> 610 #define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update> 611 #define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update> 612 #define pi (D)acos(-1) 613 #define md 999999893 614 #define rnd randGen(rng) 615 I modex(I a,I b,I m){ 616 a=a%m; 617 if(b==0){ 618 return 1; 619 } 620 I temp=modex(a,b/2,m); 621 temp=(temp*temp)%m; 622 if(b%2){ 623 temp=(temp*a)%m; 624 } 625 return temp; 626 } 627 I mod(I a,I b,I m){ 628 a=a%m; 629 b=b%m; 630 I c=__gcd(a,b); 631 a=a/c; 632 b=b/c; 633 c=modex(b,m-2,m); 634 return (a*c)%m; 635 } 636 int main(){ 637 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 638 uniform_int_distribution<I> randGen; 639 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 640 #ifndef ONLINE_JUDGE 641 freopen("input.txt", "r", stdin); 642 freopen("out04.txt", "w", stdout); 643 #endif 644 I temp=md; 645 I t; 646 cin>>t; 647 while(t--){ 648 I n; 649 cin>>n; 650 I b=modex(2,n/2,md)-1; 651 I a; 652 if(n%2){ 653 a=modex(2,n/2+1,md)-1; 654 }else{ 655 a=modex(2,n/2,md)-1; 656 } 657 I temp=(a+1)*(a+1); 658 temp%=md; 659 temp-=2*b*b; 660 temp%=md; 661 I ans=mod(2*b,temp,md); 662 ans+=md; 663 ans%=md; 664 cout<<ans<<"\n"; 665 } 666 return 0; 667 } 668 ``` 669 670 **Feedback** 671 672 * Good problem: 673 * Ok problem: 674 * Bad problem: 675 * Did not attempt: 676 677 #### [1D. Balanced Subsequences](https://codeforces.com/contest/1924/problem/D) 678 679 Author: [yash_daga](/profile/yash_daga "Grandmaster yash_daga") 680 681 **Hint 1** 682 683 Consider a function $f(n, m, k)$ which returns the number of permutations such that length of longest regular bracket subsequence is at most $2 \cdot k$ where $n$ is the number of '(' and $m$ is the number of ')'. 684 685 **Hint 2** 686 687 Answer to the problem is $f(n, m, k) - f(n, m, k-1)$ 688 689 **Tutorial** 690 691 Now to compute $f(n, m, k)$, we can consider the following cases: 692 693 * Case 1: $k \ge min(n, m)\rightarrow$ Here, the answer is ${n+m} \choose {m}$, since none of the strings can have a subsequence of length greater than $k$. 694 * Case 2: $k \lt min(n, m)\rightarrow$ Here we can write $f(n, m, k) = f(n-1, m, k-1) + f(n, m-1, k)$ since all strings will either start with: 695 a) ')' $\rightarrow$ Here, count is equal to $f(n, m-1, k)$. 696 b) '(' $\rightarrow$ Here, count is equal to $f(n-1, m, k-1)$, the first opening bracket will always add $1$ to the optimal subsequence length because all strings where each of the $m$ ')' is paired to some '(' don't contribute to the count since $k \lt m$. 697 698 After this recurrence relation we have 2 base cases: 699 700 * $k=0\rightarrow$ Here, count is $1$ which can also be written as ${n+m} \choose {k}$. 701 * $k=min(n, m)\rightarrow$ Here, count is ${n+m} \choose {m}$ (as proved in Case 1) which can also be written as ${n+m} \choose {k}$. 702 703 Now using induction we can prove that the value of $f(n, m, k)$ for Case 2 is ${n+m} \choose {k}$. 704 705 **Solution** 706 707 ``` 708 #include <bits/stdc++.h> 709 #define int long long 710 using namespace std; 711 const long long N=4005, mod=1000000007; 712 713 int power(int a, int b, int p) 714 { 715 if(a==0) 716 return 0; 717 int res=1; 718 a%=p; 719 while(b>0) 720 { 721 if(b&1) 722 res=(1ll*res*a)%p; 723 b>>=1; 724 a=(1ll*a*a)%p; 725 } 726 return res; 727 } 728 729 int fact[N], inv[N]; 730 void pre() 731 { 732 fact[0]=inv[0]=1; 733 for(int i=1;i<N;i++) 734 fact[i]=(fact[i-1]*i)%mod; 735 for(int i=1;i<N;i++) 736 inv[i]=power(fact[i], mod-2, mod); 737 } 738 int nCr(int n, int r) 739 { 740 if(min(n, r)<0 || r>n) 741 return 0; 742 if(n==r) 743 return 1; 744 return (((fact[n]*inv[r])%mod)*inv[n-r])%mod; 745 } 746 int f(int n, int m, int k) 747 { 748 if(k>=min(n, m)) 749 return nCr(n+m, m); 750 return nCr(n+m, k); 751 } 752 int32_t main() 753 { 754 pre(); 755 int t; 756 cin>>t; 757 while(t--) 758 { 759 int n, m, k; 760 cin>>n>>m>>k; 761 cout<<(f(n, m, k) - f(n, m, k-1) + mod)%mod<<"\n"; 762 } 763 } 764 ``` 765 766 **Feedback** 767 768 * Good problem: 769 * Ok problem: 770 * Bad problem: 771 * Did not attempt: 772 773 #### [1E. Paper Cutting Again](https://codeforces.com/contest/1924/problem/E) 774 775 Author: [yash_daga](/profile/yash_daga "Grandmaster yash_daga") 776 777 **Hint 1** 778 779 Can you solve it for $k=2$? 780 781 **Hint 2** 782 783 Using linearity of expectation, we can say that expected number of cuts is same as sum of probability of each line being cut and for $k=2$, we need to cut the paper until we achieve a $1 \times 1$ piece of paper. 784 785 Probability of each horizontal line being cut is $\dfrac {1}{count \thinspace of \thinspace lines \thinspace above \thinspace it + 1}$ Probability of each vertical line being cut is $\dfrac {1}{count \thinspace of \thinspace lines \thinspace left \thinspace to \thinspace it + 1}$ 786 787 Now for $k=2$ we just have to calculate the sum of all these probabilities. 788 789 **Tutorial** 790 791 For the given problem we can solve it by dividing it into 4 cases: 792 793 1. Only Vertical Cuts: 794 Let the largest integer $y$ for which $n\cdot y \lt k$ be $reqv$. 795 796 The probability of achieving the goal using only vertical cuts is $\frac{reqv}{reqv+n-1}$ since one of the $reqv$ lines needs to be cut before all the horizontal lines. Now we will multiply this with the sum of conditional probabilities for each of the vertical line. 797 798 Sum of conditional probabilities of being cut for all lines from $1$ to $reqv$ is exactly $1$, since for area to be smaller than $k$, one of them needs to be cut and as soon as one is cut, the area becomes less than $k$ so no further cuts are required. Now for the lines from $reqv+1$ to $m-1$, their conditional probabilities will form the following harmonic progression: 799 800 $\frac{1}{n+reqv} + \frac{1}{n+reqv+1} + .... + \frac{1}{n+m-2}$ 801 This is due to the fact that for a line to be cut it needs to occur before all horizontal lines and all vertical lines smaller than it. 802 2. Case with only horizontal cuts can be handled similarly. 803 3. Case when the overall last cut is a horizontal one and there is at least one vertical cut: 804 805 For this, we iterate over the last cut among all the vertical cuts. 806 807 Let the last vertical cut be $x$. We now find the largest $y$ such that $(y\cdot x) \lt k$. Let this value be $reqh$. 808 809 The objective can be achieved using this case if the vertical line $x$ occurs before all the horizontal lines from $1$ to $reqh$ and all the vertical lines from $1$ to $x-1$, and after that any one of the horizontal line from $1$ to $reqh$ occur before all the vertical lines from $1$ to $x-1$. 810 811 The probability of this happening is $\frac{1}{x+reqh}\times\frac{reqh}{reqh+x-1}$. 812 813 Now we just add the the conditional probabilities of being cut for every line and multiply this with the above probability to find the contribution of this case to the final answer. 814 815 a. Firstly the conditional probability of the vertical line $x$ being cut is $1$. 816 817 b. The sum of conditional probabilities for horizontal lines $1$ to $reqh$ is also $1$. 818 819 The order of the first $x$ vertical cuts and the first $reqh$ horizontal cuts for the given case would look like: 820 $x_v$, $y1_h$, ($(x-1)$ vertical lines and $(reqh-1)$ horizontal lines in any relative ordering) [Total $x+reqh$ elements in the sequence]. 821 822 $x_v$ denotes the $x^{th}$ vertical cut. 823 $y1_h$ denotes the horizontal cut which occurs first among all the first $reqh$ horizontal cuts. 824 825 c. Vertical cuts from $x+1$ to $m-1$: 826 827 For the $(x+1)^{th}$ cut, we can look at this like it needs to occur before the $x^{th}$ vertical cut (or it has one gap in the sequence to choose from a total of $(x+reqh+1)$ gaps). 828 829 So the probability is $\frac{1}{x+reqh+1}$. 830 831 For the $(x+2)^{th}$ cut, we can first place the $(x+2)^{th}$ cut with probability $\frac{1}{x+reqh+1}$ now we need to place the $(x+1)^{th}$ cut after of this which will happen with the probability of $\frac{x+reqh+1}{x+reqh+2}$. 832 833 So the overall probability is the product i.e., $\frac{1}{x+reqh+2}$. 834 835 Similarly, the probability for $(x+i)^{th}$ cut is $\frac{1}{x+reqh+i}$. 836 837 The sum of this Harmonic Progression can be computed in $\mathcal{O}(1)$ using pre computation. 838 839 d. Horizontal cuts from 840 841 Unable to parse markup [type=CF_MATHJAX] 842 843 to $n-1$ (Trickiest Case imo) 844 845 Let us see the case for the $(reqh+1)^{th}$ cut $\rightarrow$ It has $2$ optimal gaps (before $x_v$ and the gap between $x_v$ and $y1_h$) so the probability is $\frac{2}{x+reqh+1}$. 846 847 Now for finding the probability for $(reqh+i)^{th}$ cut, we first place this cut into one of the $2$ gaps and handle both cases separately. 848 849 Gap before $x_v$: this case is similar to case 3c and the answer is just $\frac{1}{x+reqh+i}$. 850 851 Gap between $x_v$ and $y1_h$. Here we again have to ensure that all lines from $reqh+1$ to $reqh+i-1$ occur after $reqh+i$. 852 853 So we multiply $\frac{reqh+x}{reqh+x+2}\times\frac{reqs+x+1}{reqh+x+3}$ since after we place the $(reqh+i)^{th}$ cut, we have $(reqh+x)$ good gaps among a total of $(reqh+x+2)$ and so on for all the other lines we place (Their relative ordering does not matter since we are only concerned with $(reqh+i)^{th}$ cut). 854 855 The final term for $(reqh+i)^{th}$ cut occurs out to be: $\frac{x+reqh}{(x+reqh+i)\cdot(x+reqh+i-1)}$. 856 857 858 This forms a quadratic Harmonic Progression, the sum of which can be computed in $\mathcal{O}(1)$ using precomputation. 859 4. Case when the overall last cut is a vertical one and there is at least one horizontal cut: 860 This case can be handled in a similar way as the previous case. 861 862 **Solution** 863 864 ``` 865 #include <bits/stdc++.h> 866 #define int long long 867 using namespace std; 868 const long long N=2000005, mod=1000000007; 869 870 int power(int a, int b, int p) 871 { 872 if(a==0) 873 return 0; 874 int res=1; 875 a%=p; 876 while(b>0) 877 { 878 if(b&1) 879 res=(1ll*res*a)%p; 880 b>>=1; 881 a=(1ll*a*a)%p; 882 } 883 return res; 884 } 885 886 int pref[N], inv[N], pref2[N], hp2[N]; 887 888 // Returns (1/l + 1/(l+1) + ... + 1/r) 889 int cal(int l, int r) 890 { 891 if(l>r) 892 return 0; 893 return (pref[r]-pref[l-1]+mod)%mod; 894 } 895 896 // Returns (1/(l*(l+1)) + ... + 1/(r(r+1))) 897 int cal2(int l, int r) 898 { 899 if(l>r) 900 return 0; 901 return (pref2[r]-pref2[l-1]+mod)%mod; 902 } 903 void pre() 904 { 905 pref[0]=0; 906 pref2[0]=0; 907 for(int i=1;i<N;i++) 908 { 909 inv[i]=power(i, mod-2, mod); 910 pref[i]=(pref[i-1]+inv[i])%mod; 911 int mul2=(i*(i+1))%mod; 912 pref2[i]=(pref2[i-1] + power(mul2, mod-2, mod))%mod; 913 hp2[i]=((i*(i-1))%mod)%mod; 914 } 915 } 916 int solve2(int n, int m, int k) 917 { 918 if((n*m)<k) 919 return 0; 920 int ans=0; 921 int reqv=(k-1)/n; 922 if(reqv<m) 923 { 924 int prob=(reqv*inv[reqv+n-1])%mod; 925 int exp=(prob*(1ll + cal(n+reqv, m+n-2)))%mod; 926 ans=(ans + exp)%mod; 927 } 928 int reqh=(k-1)/m; 929 if(reqh<n) 930 { 931 int prob=(reqh*inv[reqh+m-1])%mod; 932 int exp=(prob*(1ll + cal(m+reqh, m+n-2)))%mod; 933 ans=(ans + exp)%mod; 934 } 935 for(int i=1;i<min(n, k);i++) 936 { 937 reqv=(k-1)/i; 938 if(reqv>=m) 939 continue; 940 int prob=(inv[i+reqv]*reqv)%mod; 941 prob=(prob*inv[i-1+reqv])%mod; 942 int num1=(hp2[i+reqv+1]*cal2(i+reqv, i+m-2))%mod; 943 int num2=((i+reqv+1)*cal(i+reqv+1, i+m-1))%mod; 944 int num=((num1+num2)*inv[i+reqv+1])%mod; 945 int exp=(prob*(2ll + cal(i+reqv+1, reqv+(n-1))+num))%mod; 946 ans=(ans + exp)%mod; 947 } 948 for(int i=1;i<min(m, k);i++) 949 { 950 reqh=(k-1)/i; 951 if(reqh>=n) 952 continue; 953 int prob=(inv[i+reqh]*reqh)%mod; 954 prob=(prob*inv[i-1+reqh])%mod; 955 // Sum for cases when the (reqh+i)th horizontal line occurs in the gap b/w x_v and y1_h 956 int num1=(hp2[i+reqh+1]*cal2(i+reqh, i+n-2))%mod; 957 // Sum for cases when the (reqh+i)th horizontal line occurs in the gap to the left of x_v 958 int num2=((i+reqh+1)*cal(i+reqh+1, i+n-1))%mod; 959 int num=((num1+num2)*inv[i+reqh+1])%mod; 960 int exp=(prob*(2ll + cal(i+reqh+1, reqh+(m-1))+num))%mod; 961 ans=(ans + exp)%mod; 962 } 963 return ans; 964 } 965 int32_t main() 966 { 967 pre(); 968 int t; 969 cin>>t; 970 while(t--) 971 { 972 int n, m, k; 973 cin>>n>>m>>k; 974 cout<<solve2(n, m, k)<<"\n"; 975 } 976 } 977 ``` 978 979 **Feedback** 980 981 * Good problem: 982 * Ok problem: 983 * Bad problem: 984 * Did not attempt: 985 986 #### [1F. Anti-Proxy Attendance](https://codeforces.com/contest/1924/problem/F) 987 988 Author: [JaySharma1048576](/profile/JaySharma1048576 "Master JaySharma1048576") 989 990 **Hint 1** 991 992 $\sqrt[4]{1.5}=1.1069$ 993 994 **Hint 2** 995 996 Try to do a $3\rightarrow 2$ reduction in $4$ queries. 997 998 **Hint 3** 999 1000 Try to do a $3\rightarrow 2$ reduction in such a way that if the middle part is eliminated $3$ queries are used otherwise $4$ queries are used. 1001 1002 **Hint 4** 1003 1004 Instead of dividing the search space into $3$ equal parts, divide it into parts having size $36\%$, $28\%$ and $36\%$. 1005 1006 **Tutorial** 1007 1008 There might be multiple strategies to solve this problem. I will describe one of them. 1009 1010 First, let's try to solve a slightly easier version where something like $\lceil \log_{1.1} n\rceil$ queries are allowed and subset queries are allowed instead of range queries. 1011 1012 The main idea is to maintain a search space of size $S$ and reduce it to a search space of size $\big\lceil \frac{2S}{3}\big\rceil$ using atmost $4$ queries. At the end, there will be exactly $2$ elements remaining in the search space which can be guessed. The number of queries required to reduce a search space of size $n$ to a search space of size $2$ using the above strategy will be equal to $4\cdot\log_{\frac{3}{2}}\frac{n}{2}$ $= \frac{\ln\frac{n}{2}}{0.25\ln 1.5}$ $= \frac{\ln n - \ln 2}{\ln 1.1067}$ $ \lt \frac{\ln n - \ln 2}{\ln 1.1}$ $= \log_{1.1} n - 9.01$ $ \lt \lceil\log_{1.1} n\rceil$. 1013 1014 Given below is one of the strategies how this can be achieved. Let the current search space be $T$. Divide $T$ into $3$ disjoint exhaustive subsets $T_1$, $T_2$ and $T_3$ of nearly equal size. Then follow the decision tree given below to discard one of the three subsets using at most $4$ queries. 1015 1016  1017 1018 It can seen that all the leaf nodes discard at least one-third of the search space based on the previous three queries. 1019 1020 Now, coming back to the problem where only ranges are allowed to be queried. This can be easily solved by choosing $T_1$, $T_2$ and $T_3$ in such a way that all elements of $T_1$ are less than all elements of $T_2$ and all elements of $T_2$ are less than all elements of $T_3$. Then all queries used in the above decision tree can be reduced to range queries since it really doesn't matter what are the actual elements of $T_1$, $T_2$ and $T_3$. 1021 1022 Finally, there is just one small optimization left to be done. Notice that when $T_2$ gets eliminated, only $3$ queries are used and when $T_1$ and $T_3$ get eliminated, $4$ queries are used. So, it must be more optimal to keep the size of $T_2$ smaller than $T_1$ and $T_3$ but by how much? The answer is given by the equation $(1-x)^3 = (2x)^4$. It has two imaginary and two real roots out of which only one is positive $x=0.35843$. So by taking the size of the segments approximately $36\%$, $28\%$ and $36\%$, you can do it in lesser number of queries which is less than $\max(\lceil\log_{\sqrt[4]{0.64^{-1}}} n\rceil, \lceil\log_{\sqrt[3]{0.72^{-1}}} n\rceil)-\log_{1.116} 2$ which is less than $\lceil\log_{1.116} n\rceil-1$. 1023 1024 **Harder bonus tasks** 1025 1026 During testing, the testers were able to come up with harder versions requiring lesser number of queries. Specifically, try to solve the problem under the following constraints assuming $n\leq 10^5$: 1027 1028 * Harder version: $70$ queries by [dario2994](/profile/dario2994 "International Grandmaster dario2994") 1029 * Even harder version: $55$ queries by [kevinsogo](/profile/kevinsogo "Grandmaster kevinsogo") 1030 1031 **Solution** 1032 1033 ``` 1034 #include <bits/stdc++.h> 1035 using namespace std; 1036 1037 void assemble(vector<int> &x,vector<int> &x1,vector<int> &x2,vector<int> &x3,string mask) 1038 { 1039 x.clear(); 1040 if(mask[0]=='1') 1041 { 1042 for(int i=0;i<x1.size();i++) 1043 x.push_back(x1[i]); 1044 } 1045 if(mask[1]=='1') 1046 { 1047 for(int i=0;i<x2.size();i++) 1048 x.push_back(x2[i]); 1049 } 1050 if(mask[2]=='1') 1051 { 1052 for(int i=0;i<x3.size();i++) 1053 x.push_back(x3[i]); 1054 } 1055 } 1056 1057 bool query(vector<int> &x1,vector<int> &x2,vector<int> &x3,string mask) 1058 { 1059 vector<int> x; 1060 assemble(x,x1,x2,x3,mask); 1061 int l=x[0],r=x.back(); 1062 cout << "? " << l << " " << r << endl; 1063 int y; 1064 cin >> y; 1065 return (y==r-l); 1066 } 1067 1068 void guess(int x) 1069 { 1070 cout << "! " << x << endl; 1071 int y; 1072 cin >> y; 1073 } 1074 1075 void finish() 1076 { 1077 cout << "#" << endl; 1078 } 1079 1080 int main() 1081 { 1082 int tc; 1083 cin >> tc; 1084 while(tc--) 1085 { 1086 int n; 1087 cin >> n; 1088 vector<int> x; 1089 for(int i=1;i<=n;i++) 1090 x.push_back(i); 1091 while(x.size()>2) 1092 { 1093 int m = x.size(); 1094 int k = round(0.36*m); 1095 vector<int> x1,x2,x3; 1096 for(int i=0;i<k;i++) 1097 x1.push_back(x[i]); 1098 for(int i=k;i<m-k;i++) 1099 x2.push_back(x[i]); 1100 for(int i=m-k;i<m;i++) 1101 x3.push_back(x[i]); 1102 if(query(x1,x2,x3,"110")) 1103 { 1104 if(query(x1,x2,x3,"100")) 1105 { 1106 if(query(x1,x2,x3,"111")) 1107 { 1108 assemble(x,x1,x2,x3,"011"); 1109 } 1110 else 1111 { 1112 assemble(x,x1,x2,x3,"110"); 1113 } 1114 } 1115 else 1116 { 1117 if(query(x1,x2,x3,"110")) 1118 { 1119 assemble(x,x1,x2,x3,"101"); 1120 } 1121 else 1122 { 1123 if(query(x1,x2,x3,"111")) 1124 { 1125 assemble(x,x1,x2,x3,"110"); 1126 } 1127 else 1128 { 1129 assemble(x,x1,x2,x3,"011"); 1130 } 1131 } 1132 } 1133 } 1134 else 1135 { 1136 if(query(x1,x2,x3,"100")) 1137 { 1138 if(query(x1,x2,x3,"110")) 1139 { 1140 if(query(x1,x2,x3,"111")) 1141 { 1142 assemble(x,x1,x2,x3,"011"); 1143 } 1144 else 1145 { 1146 assemble(x,x1,x2,x3,"110"); 1147 } 1148 } 1149 else 1150 { 1151 assemble(x,x1,x2,x3,"101"); 1152 } 1153 } 1154 else 1155 { 1156 if(query(x1,x2,x3,"111")) 1157 { 1158 assemble(x,x1,x2,x3,"110"); 1159 } 1160 else 1161 { 1162 assemble(x,x1,x2,x3,"011"); 1163 } 1164 } 1165 } 1166 } 1167 guess(x[0]); 1168 guess(x[1]); 1169 finish(); 1170 } 1171 } 1172 ``` 1173 1174 **Feedback** 1175 1176 * Good problem: 1177 * Ok problem: 1178 * Bad problem: 1179 * Did not attempt: