codeforces-scrape

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

1844.md (22076B)


      1 Source: https://codeforces.com/blog/entry/118128
      2 
      3 Video editorials for [B](https://www.youtube.com/watch?v=5nzUni8dFLQ), [C](https://www.youtube.com/watch?v=8mz7gnAJ5QM), and [D](https://www.youtube.com/watch?v=ahnNAwpGwHc) are available on [competitive__programmer](/profile/competitive__programmer "Specialist competitive__programmer")'s channel.
      4 
      5 ### [1844A - Subtraction Game](/contest/1844/problem/A)
      6 
      7 **Hint 1**
      8 
      9 There exists a small $n$ where the second player can win.
     10 
     11 **Hint 2**
     12 
     13 If $a \ge 2$, then $n = 1$ works.
     14 
     15 **Solution**
     16 
     17 Tutorial is loading...
     18 
     19 **Implementation**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 using namespace std;
     24 
     25 int main() {
     26     int t,a,b;
     27     scanf("%d",&t);
     28     while (t--) {
     29         scanf("%d %d",&a,&b);
     30         printf("%d\n",a+b);
     31     }
     32     return 0;
     33 }
     34 ```
     35 
     36 ### [1844B - Permutations & Primes](/contest/1844/problem/B)
     37 
     38 **Hint 1**
     39 
     40 In order for $(l,r)$ to contribute to the primality, we must have $\operatorname{MEX}(a_l,\dots,a_r) \ge 2$, so there is some value $1$ between indices $l$ and $r$.
     41 
     42 **Hint 2**
     43 
     44 To maximize the number of pairs $(l,r)$ that contain the value $1$, we should put $1$ near the middle of the array.
     45 
     46 **Hint 3**
     47 
     48 To minimize the number of pairs $(l,r)$ where $\operatorname{MEX}(a_l,\dots,a_r) \ge 2$ but is not prime, we should put $2$ and $3$ at the ends of the array.
     49 
     50 **Solution**
     51 
     52 Tutorial is loading...
     53 
     54 **Implementation**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 using namespace std;
     59 
     60 int a[200000];
     61 int main() {
     62     int i;
     63     int t,n;
     64     scanf("%d",&t);
     65     while (t--) {
     66         scanf("%d",&n);
     67         if (n == 1) printf("1\n");
     68         else if (n == 2) printf("1 2\n");
     69         else {
     70             int c = 4;
     71             fill(a,a+n,0);
     72             a[0] = 2,a[n/2] = 1,a[n-1] = 3;
     73             for (i = 0; i < n; i++) {
     74                 if (a[i] == 0) a[i] = c++;
     75             }
     76             for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
     77         }
     78     }
     79     return 0;
     80 }
     81 ```
     82 
     83 ### [1844C - Particles](/contest/1844/problem/C)
     84 
     85 **Hint 1**
     86 
     87 The answer is the sum of some subset of $c_1,\dots,c_n$. Think about which subsets are obtainable.
     88 
     89 **Hint 2**
     90 
     91 Consider the set of even-indexed particles and the set of odd-indexed particles.
     92 
     93 **Solution**
     94 
     95 Tutorial is loading...
     96 
     97 **Implementation**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101 using namespace std;
    102 typedef long long int LLI;
    103 
    104 int c[200000];
    105 int main() {
    106     int i;
    107     int t,n;
    108     scanf("%d",&t);
    109     while (t--) {
    110         scanf("%d",&n);
    111         for (i = 0; i < n; i++) scanf("%d",&c[i]);
    112 
    113         int allneg = 1;
    114         for (i = 0; i < n; i++) allneg &= (c[i] < 0);
    115         if (allneg) printf("%d\n",*max_element(c,c+n));
    116         else {
    117             LLI ans1 = 0,ans2 = 0;
    118             for (i = 0; i < n; i++) {
    119                 if (i & 1) ans1 += max(c[i],0);
    120                 else ans2 += max(c[i],0);
    121             }
    122             printf("%lld\n",max(ans1,ans2));
    123         }
    124     }
    125     return 0;
    126 }
    127 ```
    128 
    129 ### [1844D - Row Major](/contest/1844/problem/D)
    130 
    131 **Hint 1**
    132 
    133 Describe, using a graph, all the pairs of characters in $s$ that need to be different.
    134 
    135 **Hint 2**
    136 
    137 Consider the smallest positive integer that does not divide $n$.
    138 
    139 **Solution**
    140 
    141 Tutorial is loading...
    142 
    143 **Implementation**
    144 
    145 ```
    146 #include <bits/stdc++.h>
    147 using namespace std;
    148 
    149 char s[1000001];
    150 int main() {
    151     int i;
    152     int t,n;
    153     scanf("%d",&t);
    154     while (t--) {
    155         scanf("%d",&n);
    156         int c = 1;
    157         while ((n % c) == 0) c++;
    158         for (i = 0; i < n; i++) s[i] = 'a'+(i % c);
    159         s[n] = '\0';
    160         printf("%s\n",s);
    161     }
    162     return 0;
    163 }
    164 ```
    165 
    166 ### [1844E - Great Grids](/contest/1844/problem/E)
    167 
    168 **Hint 1**
    169 
    170 Try to find a characterization of all great grids.
    171 
    172 **Hint 2**
    173 
    174 There are two approaches that lead to the same conclusion. Approach 1 is more clever and leads more easily to the conclusion, while approach 2 is perhaps more natural to consider. Feel free to read the hint towards the approach that sounds better.
    175 
    176 **Hint Towards Approach 1**
    177 
    178 Think of the letters as numbers modulo $3$ and look at differences of adjacent cells.
    179 
    180 **Hint Towards Approach 2**
    181 
    182 Draw a `/` or `\` for each $2 \times 2$ subgrid connecting the equal letters, and look for patterns.
    183 
    184 **Hint 3**
    185 
    186 In either approach, we can associate a type to each row and column, which has one of two possibilities. The constraints correspond to a row and a column needing to have the same or different types.
    187 
    188 **Hint 4**
    189 
    190 The problem reduces to checking the $2$-colourability of a graph.
    191 
    192 **Solution**
    193 
    194 Tutorial is loading...
    195 
    196 **Implementation**
    197 
    198 ```
    199 #include <bits/stdc++.h>
    200 using namespace std;
    201 typedef vector<pair<int,int> > vpii;
    202 #define mp make_pair
    203 #define pb push_back
    204 
    205 vpii adjList[4000];
    206 int colour[4000],bad = 0;
    207 int doDFS(int u,int c) {
    208     if (colour[u] != -1) {
    209         if (colour[u] != c) bad = 1;
    210         return 0;
    211     }
    212     colour[u] = c;
    213     for (auto [v,e]: adjList[u]) doDFS(v,c^e);
    214     return 0;
    215 }
    216 int main() {
    217     int i;
    218     int t,n,m,k;
    219     int x1,y1,x2,y2;
    220     scanf("%d",&t);
    221     while (t--) {
    222         scanf("%d %d %d",&n,&m,&k);
    223         for (i = 0; i < k; i++) {
    224             scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    225             x1--,y1--,x2--,y2--;
    226             adjList[min(x1,x2)].pb(mp(n+min(y1,y2),(x1+y1 != x2+y2)));
    227             adjList[n+min(y1,y2)].pb(mp(min(x1,x2),(x1+y1 != x2+y2)));
    228         }
    229 
    230         fill(colour,colour+n+m,-1),bad = 0;
    231         for (i = 0; i < n+m; i++) {
    232             if (colour[i] == -1) doDFS(i,0);
    233         }
    234         printf(bad ? "NO\n":"YES\n");
    235 
    236         for (i = 0; i < n+m; i++) adjList[i].clear();
    237     }
    238     return 0;
    239 }
    240 ```
    241 
    242 ### [1844F1 - Min Cost Permutation (Easy Version)](/contest/1844/problem/F1)
    243 
    244 **Hint 1**
    245 
    246 Solve the case $c \ge 0$ first. There is a very simple description of the answer.
    247 
    248 **Another Hint**
    249 
    250 What is the answer when $c = 0$?
    251 
    252 **Hint 2**
    253 
    254 When $c \ge 0$, the answer is the array sorted in nondecreasing order.
    255 
    256 **Hint 3**
    257 
    258 When $c \lt 0$, the minimum cost is achieved by sorting the array in nonincreasing order, but this is not the lexicographically smallest. Try to greedily form the lexicographically smallest array one element at a time.
    259 
    260 **Solution (easy version)**
    261 
    262 Tutorial is loading...
    263 
    264 **Implementation**
    265 
    266 ```
    267 #include <bits/stdc++.h>
    268 using namespace std;
    269 typedef long long int LLI;
    270 
    271 int a[200000];
    272 int main() {
    273     int i,j;
    274     int t,n,c;
    275     scanf("%d",&t);
    276     while (t--) {
    277         scanf("%d %d",&n,&c);
    278         for (i = 0; i < n; i++) scanf("%d",&a[i]);
    279         if (c >= 0) {
    280             sort(a,a+n);
    281             for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
    282             continue;
    283         }
    284 
    285         sort(a,a+n,greater<int>());
    286         for (i = 0; i < n; i++) {
    287             for (j = n-1; j > i; j--) {
    288                 LLI diff = -abs(a[j]-a[j-1]-c);
    289                 if (j < n-1) {
    290                     diff -= abs(a[j+1]-a[j]-c);
    291                     diff += abs(a[j+1]-a[j-1]-c);
    292                 }
    293                 if (i == 0) diff += abs(a[i]-a[j]-c);
    294                 else {
    295                     diff -= abs(a[i]-a[i-1]-c);
    296                     diff += abs(a[i]-a[j]-c);
    297                     diff += abs(a[j]-a[i-1]-c);
    298                 }
    299                 if (diff == 0) {
    300                     for (; j > i; j--) swap(a[j],a[j-1]);
    301                 }
    302             }
    303         }
    304         for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
    305     }
    306     return 0;
    307 }
    308 ```
    309 
    310 ### [1844F2 - Min Cost Permutation (Hard Version)](/contest/1844/problem/F2)
    311 
    312 These hints and solution continue from the solution for the easy version, so please read the solution for the easy version first.
    313 
    314 **Hint 4**
    315 
    316 We need to optimize the $\mathcal{O}(n^2)$ greedy with some data structures. There exist solutions with varying levels of data structure implementation depending on how much effort is put into characterizing the answer array. For a short solution, start by simplifying the formula $(*)$ (in the solution for the easy version) to get a cleaner description.
    317 
    318 **Hint 5**
    319 
    320 The condition is actually equivalent to ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$) and ($b_{k-1}-a_i \le |c|$).
    321 
    322 **Hint 6**
    323 
    324 Maintain a linked list of the unused entries of $a$ and a set of unused entries that satisfy ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$).
    325 
    326 **Solution (hard version)**
    327 
    328 ### [1844F2 - Min Cost Permutation (Hard Version)](/contest/1844/problem/F2)
    329 
    330 Let $c \lt 0$.
    331 
    332 We now simplify condition $(*)$, which involves considering a few cases depending on the sign of the terms. It turns out that the condition is equivalent to ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$) and ($b_{k-1}-a_i \le |c|$) (for full details, see the overall proof below).
    333 
    334 Sort $a$ in nonincreasing order so that $a_1 \ge a_2 \ge \dots \ge a_n$. We can simulate the greedy algorithm from the easy version with the help of a linked list of the unused elements of $a$ and a set of $a_i$ which satisfy the first part of the condition, ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$). Here, $a_{i-1}$ and $a_{i+1}$ actually refer to the closest unused elements of $a$, which are $a_i$'s left and right pointers in the linked list, respectively.
    335 
    336 Each time, we query the set for its smallest element $a_i$ that satisfies $a_i \ge b_{k-1}-|c|$. If this element does not exist, then we take $a_i$ to be the largest element in the linked list. Then, we set $b_k := a_i$, delete $a_i$ from the linked list, and update the set with the left and right elements of $a_i$ if they now satisfy the condition.
    337 
    338 One small observation is that in the answer $b$, $b_1 = a_1$ and $b_n = a_n$. This may simplify the implementation since it means that some edge cases of $(*)$ actually don't need to be checked. It is also actually not necessary to check the $a_{i-1} = a_i$ or $a_i = a_{i+1}$ condition.
    339 
    340 The time complexity is $\mathcal{O}(n \log n)$.
    341 
    342 **Proofs**
    343 
    344 The case $n \le 2$ is trivial. In the following, we only consider the case $c \lt 0$ and $n \ge 3$. The case $c \ge 0$ follows by symmetry (reverse the array).
    345 
    346 Let $c' := -c$ to reduce confusion with negative signs, and WLOG let $a_1 \ge a_2 \ge \dots \ge a_n$.
    347 
    348 Instead of considering $\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$, consider a permutation $b$ that minimizes the *augmented cost* $|b_1-b_n-c|+\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$. By circular symmetry, WLOG rotate $b$ so that $b_n = a_n$.
    349 
    350 We will perform a sequence of steps to sort $b$ in nonincreasing order without ever increasing the augmented cost. Consider looking at $b_{n-1},b_{n-2},\dots,b_1$ in order, such that when we look at $b_k$, we have the invariant that $b_{k+1} \ge b_{k+2} \ge \dots \ge b_n = a_n$. If $b_k \ge b_{k+1}$, do not do anything. Otherwise, since $b_k \ge a_n = b_n$, there exists an index $k+1 \le i \lt n$ such that $b_i \ge b_k \ge b_{i+1}$. Consider deleting $b_k$ from the array and reinserting it between index $i$ and $i+1$. We have the following results:
    351 
    352 **Claim 1**: Deleting $b_k$ decreases the augmented cost by at least $c'$.
    353 
    354 **Proof**: Let $x := b_{k-1}-b_k$ (or $b_n-b_1$ if $k = 1$) and $y := b_{k+1}-b_k \ge 0$. We need to check that $|x-y-c'|+c' \le |x-c'|+|-y-c'|$, which follows from $|x-c'|+|-y-c'| = |x-c'|+y+c' \ge |x-y-c'|+c'$ (we use the triangle inequality in the last step).
    355 
    356 Note that equality holds if and only if $x-c' \le 0$, i.e. $b_{k-1}-b_k \le c'$.
    357 
    358 **Claim 2**: Reinserting $b_k$ increases the augmented cost by at most $c'$.
    359 
    360 **Proof**: Let $x := b_i-b_k \ge 0$ and $y := b_k-b_{i+1} \ge 0$. We need to check that $|x-c'|+|y-c'| \le |x+y-c'|+c'$. Consider four cases:
    361 
    362 * If $x,y \ge c'$, then $|x-c'|+|y-c'| = x+y-2c' \lt (x+y-c')+c' = |x+y-c'|+c'$.
    363 * If $x \ge c', y \le c'$, then $|x-c'|+|y-c'| = x-y \le (x+y-c')+c' = |x+y-c'|+c'$.
    364 * If $x \le c', y \ge c'$, then $|x-c'|+|y-c'| = y-x \le (x+y-c')+c' = |x+y-c'|+c'$.
    365 * If $x,y \le c'$, then $|x-c'|+|y-c'| = 2c'-x-y = (c'-x-y)+c' \le |x+y-c'|+c'$.
    366 
    367 Note that equality holds if and only if $x = 0$ or $y = 0$ or $c'-x-y \ge 0$, i.e. $b_i-b_{i+1} \le c'$ or $b_i = b_k$ or $b_k = b_{i+1}$.
    368 
    369 Therefore, each step does not increase the augmented cost. After all the steps, $b$ will be sorted in nonincreasing order. Therefore, the smallest possible augmented cost is $|a_1-a_n-c|+\sum_{i=1}^{n-1} |a_{i+1}-a_i-c|$.
    370 
    371 Now note that $|a_1-a_n-c| = (a_1-a_n)+c'$ is the *maximum* possible value of $|b_1-b_n-c|$! This means that the minimum cost cannot be less than the minimum augmented cost minus $(a_1-a_n)+c'$. It follows that the minimum cost is obtained by sorting $a$ in nonincreasing order, and furthermore, *any* optimal permutation $b$ satisfies $b_1 = a_1$ and $b_n = a_n$.
    372 
    373 Furthermore, suppose we have fixed $b_1,\dots,b_k$ and also $b_n = a_n$. By a similar argument (looking at $b_{n-1},\dots,b_{k+1}$ and reinserting them to the right), one optimal permutation $b_{k+1},\dots,b_n$ of the remaining elements is to sort them in nonincreasing order. Our greedy algorithm can only reach states where the optimal remaining permutation satisfies $b_n = a_n$, so it is correct.
    374 
    375 Note that condition $(*)$ is similar to equality being achieved in both claim 1 and claim 2. It follows that $(*)$ is equivalent to ($a_{i-1}-a_{i+1} \le |c|$ or $a_{i-1} = a_i$ or $a_i = a_{i+1}$) and ($b_{k-1}-a_i \le |c|$) as claimed.
    376 
    377 **Implementation**
    378 
    379 ```
    380 #include <bits/stdc++.h>
    381 using namespace std;
    382 typedef pair<int,int> pii;
    383 #define mp make_pair
    384 
    385 int a[200000],b[200000],l[200000],r[200000];
    386 set<pii> S;
    387 int main() {
    388     int i;
    389     int t,n,c;
    390     scanf("%d",&t);
    391     while (t--) {
    392         scanf("%d %d",&n,&c);
    393         for (i = 0; i < n; i++) scanf("%d",&a[i]);
    394         if (c >= 0) {
    395             sort(a,a+n);
    396             for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
    397             continue;
    398         }
    399 
    400         sort(a,a+n,greater<int>());
    401         b[0] = a[0];
    402         for (i = 0; i < n; i++) l[i] = (i+n-1) % n,r[i] = (i+1) % n;
    403         for (i = 2; i < n-1; i++) {
    404             if (a[l[i]]-a[r[i]] <= -c) S.insert(mp(a[i],i));
    405         }
    406         for (i = 1; i < n; i++) {
    407             int u;
    408             auto it = S.lower_bound(mp(b[i-1]+c,0));
    409             if (it == S.end()) u = r[0];
    410             else u = it->second,S.erase(it);
    411             b[i] = a[u];
    412             int x = l[u],y = r[u];
    413             r[x] = y,l[y] = x;
    414             S.erase(mp(a[x],x)),S.erase(mp(a[y],y));
    415             if ((x != 0) && (l[x] != 0) && (r[x] != 0) && (a[l[x]]-a[r[x]] <= -c)) S.insert(mp(a[x],x));
    416             if ((y != 0) && (l[y] != 0) && (r[y] != 0) && (a[l[y]]-a[r[y]] <= -c)) S.insert(mp(a[y],y));
    417         }
    418         for (i = 0; i < n; i++) printf("%d%c",b[i],(i == n-1) ? '\n':' ');
    419     }
    420     return 0;
    421 }
    422 ```
    423 
    424 ### [1844G - Tree Weights](/contest/1844/problem/G)
    425 
    426 **Hint 1**
    427 
    428 Model the problem as a system of linear equations.
    429 
    430 **Hint 2**
    431 
    432 Let $x_u$ be the sum of the weights of the edges on the path from node $1$ to node $u$. The equations are of the form $x_i + x_{i+1} - 2x_{\text{lca}(i,i+1)} = d_i$.
    433 
    434 **Hint 3**
    435 
    436 The intended solution does not do anything like attempt to maintain paths/virtual trees of known weight. One easily overlooked detail that is essential to the solution is that $x_i$ are integers.
    437 
    438 **Hint 4**
    439 
    440 Solve the equations modulo $2$ first, so that the $2x_{\text{lca}(i,i+1)}$ term disappears.
    441 
    442 **Hint 5**
    443 
    444 After solving the equations modulo $2$, we can similarly solve modulo $4$, $8$, etc.
    445 
    446 **Solution**
    447 
    448 Tutorial is loading...
    449 
    450 **Implementation**
    451 
    452 ```
    453 #include <bits/stdc++.h>
    454 using namespace std;
    455 typedef long long int LLI;
    456 typedef vector<pair<int,int> > vpii;
    457 #define mp make_pair
    458 #define pb push_back
    459 
    460 vpii adjList[100000];
    461 LLI d[100000];
    462 int parent[100000][17],parenti[100000],depth[100000];
    463 int doDFS(int u,int p,int d) {
    464     parent[u][0] = p,depth[u] = d;
    465     for (auto [v,i]: adjList[u]) {
    466         if (v != p) parenti[v] = i,doDFS(v,u,d+1);
    467     }
    468     return 0;
    469 }
    470 int logn;
    471 int lca(int u,int v) {
    472     int i;
    473     if (depth[u] < depth[v]) swap(u,v);
    474     for (i = logn-1; i >= 0; i--) {
    475         if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i];
    476     }
    477     if (u == v) return u;
    478     for (i = logn-1; i >= 0; i--) {
    479         if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i];
    480     }
    481     return parent[u][0];
    482 }
    483 int lcas[100000],bit[100000];
    484 LLI ans[100000],w[100000];
    485 int main() {
    486     int i;
    487     int n,u,v;
    488     scanf("%d",&n);
    489     for (i = 0; i < n-1; i++) {
    490         scanf("%d %d",&u,&v);
    491         u--,v--;
    492         adjList[u].pb(mp(v,i));
    493         adjList[v].pb(mp(u,i));
    494     }
    495     for (i = 0; i < n-1; i++) scanf("%lld",&d[i]);
    496 
    497     int j;
    498     doDFS(0,-1,0);
    499     for (i = 1; (1 << i) < n; i++) {
    500         for (j = 0; j < n; j++) {
    501             if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
    502             else parent[j][i] = -1;
    503         }
    504     }
    505     logn = i;
    506     for (i = 0; i < n-1; i++) lcas[i] = lca(i,i+1);
    507 
    508     for (i = 0; i < 57; i++) {
    509         bit[0] = 0;
    510         for (j = 0; j < n-1; j++) bit[j+1] = bit[j]^(d[j] & 1);
    511         for (j = 0; j < n-1; j++) d[j] = (d[j]-bit[j]-bit[j+1]+2*bit[lcas[j]])/2;
    512         for (j = 0; j < n; j++) ans[j] |= ((LLI) bit[j] << i);
    513     }
    514     for (i = 0; i < n-1; i++) {
    515         if (d[i] != 0) {
    516             printf("-1\n");
    517             return 0;
    518         }
    519     }
    520     for (i = 1; i < n; i++) {
    521         w[parenti[i]] = ans[i]-ans[parent[i][0]];
    522         if (w[parenti[i]] <= 0) {
    523             printf("-1\n");
    524             return 0;
    525         }
    526     }
    527     for (i = 0; i < n-1; i++) printf("%lld\n",w[i]);
    528 
    529     return 0;
    530 }
    531 ```
    532 
    533 ### [1844H - Multiple of Three Cycles](/contest/1844/problem/H)
    534 
    535 **Hint 1**
    536 
    537 The partially formed permutation is composed of several paths and cycles. Only the length of each path/cycle modulo $3$ matters.
    538 
    539 **Hint 2**
    540 
    541 The problem reduces to the following: Given $a$ $1$s, $b$ $2$s, and $c$ $0$s, how many ways are there to build a permutation on these objects so that each cycle sums to a multiple of $3$? Let $f(a,b,c)$ be the answer. Write some dynamic programming recurrences for $f(a,b,c)$.
    542 
    543 **Hint 3**
    544 
    545 Note that $f(a,b,c) = (a+b+c)f(a,b,c-1)$ (choose the next object of any $0$ and merge them).
    546 
    547 **Why is this useful?**
    548 
    549 This allows us to eliminate the $c$ parameter, multiplying the answer by a factorial and inverse factorial.
    550 
    551 **Hint 4**
    552 
    553 Let $f(a,b) = f(a,b,0)$. Write down not one, but two recurrence relations $f(a,b)$ satisfies.
    554 
    555 **What are the recurrences?**
    556 
    557 We have $f(a,b) = b(a+b-1)f(a-1,b-1) + (a-1)f(a-2,b+1)$ when $a \gt 0$ (choose the next object of any $1$ and merge them) and also $f(a,b) = a(a+b-1)f(a-1,b-1) + (b-1)f(a+1,b-2)$ when $b \gt 0$ (choose the next object of any $2$ and merge them).
    558 
    559 **Hint 5**
    560 
    561 These recurrences mean that given any two of $f(a,b),f(a-1,b-1),f(a+2,b-1),f(a-1,b+2)$, we can solve for the other two.
    562 
    563 **Hint 6**
    564 
    565 Consider the pairs $(a,b)$ that arise from the $n$ queries. These pairs can be visualized as a walk in the plane, where each each pair does not differ from the previous pair by much. If we carefully use the recurrences to solve for values of $f(a,b)$ from values we already know, we can answer all queries on this walk while calculating only $\mathcal{O}(n)$ values of $f(a,b)$.
    566 
    567 **Solution**
    568 
    569 Tutorial is loading...
    570 
    571 **Implementation**
    572 
    573 ```
    574 #include <bits/stdc++.h>
    575 using namespace std;
    576 typedef long long int LLI;
    577 #define MOD 998244353
    578 
    579 int parent[300000],siz[300000];
    580 int find(int n) {
    581     if (parent[n] != n) parent[n] = find(parent[n]);
    582     return parent[n];
    583 }
    584 int queries[600000][3],ans[600000];
    585 int fact[300000],invfact[300000],invn[300000];
    586 int inv(int n) {
    587     int e = MOD-2,r = 1;
    588     while (e > 0) {
    589         if (e & 1) r = ((LLI) r*n) % MOD;
    590         e >>= 1;
    591         n = ((LLI) n*n) % MOD;
    592     }
    593     return r;
    594 }
    595 int main() {
    596     int i;
    597     int n,x,y,bad = 1e9;
    598     int num[3];
    599     scanf("%d",&n);
    600     for (i = 0; i < n; i++) parent[i] = i,siz[i] = 1;
    601     num[0] = 0,num[1] = n,num[2] = 0;
    602     for (i = 0; i < n; i++) {
    603         scanf("%d %d",&x,&y);
    604         x--,y--;
    605         if (find(x) != find(y)) {
    606             num[siz[find(x)] % 3]--;
    607             num[siz[find(y)] % 3]--;
    608             siz[find(y)] += siz[find(x)];
    609             parent[find(x)] = find(y);
    610             num[siz[find(y)] % 3]++;
    611         }
    612         else if ((siz[find(x)] % 3) == 0) num[0]--;
    613         else if (bad == 1e9) bad = i;
    614         copy(num,num+3,queries[i]);
    615     }
    616 
    617     fact[0] = 1;
    618     for (i = 1; i < n; i++) fact[i] = ((LLI) i*fact[i-1]) % MOD;
    619     invfact[n-1] = inv(fact[n-1]);
    620     for (i = n-2; i >= 0; i--) invfact[i] = ((LLI) (i+1)*invfact[i+1]) % MOD;
    621     for (i = 1; i < n; i++) invn[i] = ((LLI) invfact[i]*fact[i-1]) % MOD;
    622 
    623     int m = n;
    624     while (num[1]+num[2] > 0) {
    625         int a = (num[1] > 0) ? 1:2;
    626         num[a]--;
    627         int b = (num[1] > 0) ? 1:2;
    628         num[b]--;
    629         num[(a+b) % 3]++;
    630         copy(num,num+3,queries[m++]);
    631     }
    632     x = 1,y = 1;
    633     int u = 1,v = 8;
    634     auto f = [&]() {
    635         assert(x > 0);
    636         int nu = (((v-(((LLI) (y+1)*(x+y+1)) % MOD)*u) % MOD)*invn[x]) % MOD;
    637         int nv = ((((LLI) x*(x+y+2)) % MOD)*nu+(LLI) (y+2)*v) % MOD;
    638         x--,y += 2,u = nu,v = nv;
    639         if (u < 0) u += MOD;
    640         if (v < 0) v += MOD;
    641     };
    642     auto g = [&]() {
    643         assert(y > 0);
    644         int nu = (((v-(((LLI) (x+1)*(x+y+1)) % MOD)*u) % MOD)*invn[y]) % MOD;
    645         int nv = ((((LLI) y*(x+y+2)) % MOD)*nu+(LLI) (x+2)*v) % MOD;
    646         x += 2,y--,u = nu,v = nv;
    647         if (u < 0) u += MOD;
    648         if (v < 0) v += MOD;
    649     };
    650     for (i = m-1; i >= 0; i--) {
    651         int a = queries[i][1],b = queries[i][2],c = queries[i][0];
    652         if ((a == 0) && (b == 0)) ans[i] = 1;
    653         else if ((a == x) && (b == y)) ans[i] = u;
    654         else if ((a == x-1) && (b == y+2)) f(),ans[i] = u;
    655         else if ((a == x+2) && (b == y-1)) g(),ans[i] = u;
    656         else if ((a == x+1) && (b == y+1)) {
    657             if (x > 0) f(),g(),ans[i] = u;
    658             else g(),f(),ans[i] = u;
    659         }
    660         else assert(0);
    661         ans[i] = ((LLI) ans[i]*fact[a+b+c]) % MOD;
    662         ans[i] = ((LLI) ans[i]*invfact[a+b]) % MOD;
    663     }
    664     for (i = 0; i < n; i++) printf("%d\n",(i >= bad) ? 0:ans[i]);
    665 
    666     return 0;
    667 }
    668 ```