codeforces-scrape

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

1924.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 ![](/predownloaded/25/05/250523406d6708ebcbd971943191773ac99feee3.png)
    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 ![Decison-Tree](/predownloaded/c3/fe/c3fe495eef7256184346c9c162471cbb37075137.jpg)
   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: