codeforces-scrape

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

1726.md (38845B)


      1 Source: https://codeforces.com/blog/entry/106675
      2 
      3 We'd like to thank you all for participating in the contest, and hope you enjoyed it. Hope to see you again next year!
      4 
      5 ~~The editorial for problem F will be added soon.~~ It is now added.
      6 
      7 ---
      8 
      9 ## [1726A - Mainak and Array](/contest/1726/problem/A)
     10 
     11 Idea: [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")   
     12  Editorial: [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")
     13 
     14 **Hint 1**
     15 
     16 Which subsegments are relevant?
     17 
     18 **Hint 2**
     19 
     20 $a_n$ and $a_1$ can be taken up only by *some* combination of elements, not all.
     21 
     22 **Solution**
     23 
     24 Tutorial is loading...
     25 
     26 **Implementation**
     27 
     28 **C++**
     29 
     30 ```
     31 #include<bits/stdc++.h>
     32 using namespace std;
     33 
     34 inline void test_case(){
     35 	
     36 	int N;
     37 	cin >> N;
     38 
     39 	int A[N];
     40 	int ans = -1000000007;
     41 
     42 	for(int i = 0; i < N; ++i){
     43 		cin >> A[i];
     44 	}
     45 
     46 	for(int i = 0; i < N; ++i){
     47 		ans = max(ans, A[(i - 1 + N) % N] - A[i]);
     48 	}
     49 
     50 	for(int i = 1; i < N; ++i){
     51 		ans = max(ans, A[i] - A[0]);
     52 	}
     53 
     54 	for(int i = 0; i < N - 1; ++i){
     55 		ans = max(ans, A[N - 1] - A[i]);
     56 	}
     57 
     58 	cout << ans << '\n';
     59 }
     60 
     61 signed main(){
     62 
     63 	int test_case_number;
     64 	cin>>test_case_number;
     65 	while(test_case_number--)
     66 		test_case();
     67 	
     68 	return 0;
     69 }
     70 ```
     71 
     72 **Python**
     73 
     74 ```
     75 t=int(input())
     76 for _ in range(t):
     77     n=int(input())
     78     a=[int(x) for x in input().split()]
     79     ans=max(a[-1]-min(a),max(a)-a[0])
     80     for i in range(n):
     81         ans=max(ans,a[i-1]-a[i])
     82     print(ans)
     83 ```
     84 
     85 ## [1726B - Mainak and Interesting Sequence](/contest/1726/problem/B)
     86 
     87 Idea: [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")   
     88  Editorial: [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")
     89 
     90 **Hint 1**
     91 
     92 Which cases of $n$ and $m$ are easy to come up with a solution? Which cases is it easy to show that no solution exist?
     93 
     94 **Hint 2**
     95 
     96 What happens when $n$ is even but $m$ is odd?
     97 
     98 **Solution**
     99 
    100 Tutorial is loading...
    101 
    102 **Implementation**
    103 
    104 **C++**
    105 
    106 ```
    107 #include<bits/stdc++.h>
    108 using namespace std;
    109 
    110 inline void test_case(){
    111 	
    112 	int N, M;
    113 	cin >> N >> M;
    114 
    115 	if(((N % 2 == 0) && (M % 2 == 1)) || (M < N)){ // impossible cases, M < N and (M - odd, N - even)
    116 		cout << "NO\n";
    117 	}else if((N % 2) == 1){ // (N - odd)
    118 		cout << "YES\n";
    119 		for(int i = 1; i < N; ++i){
    120 			cout << "1 ";
    121 		}
    122 		cout << M - N + 1 << '\n';
    123 	}else{ // (N - even, M - even)
    124 		cout << "YES\n";
    125 		for(int i = 2; i < N; ++i){
    126 			cout << "1 ";
    127 		}
    128 		cout << (M - N + 2) / 2 << ' ' << (M - N + 2) / 2 << '\n';
    129 	}
    130 
    131 }
    132 
    133 signed main(){
    134 
    135 	ios_base::sync_with_stdio(false);
    136 	cin.tie(NULL);
    137 	cout.tie(NULL);
    138 
    139 	int test_case_number;
    140 	cin>>test_case_number;
    141 	while(test_case_number--)
    142 		test_case();
    143 	
    144 	return 0;
    145 }
    146 ```
    147 
    148 **Python**
    149 
    150 ```
    151 import sys
    152 input = sys.stdin.readline
    153 
    154 t=int(input())
    155 for _ in range(t):
    156     n,m=map(int,input().split())
    157     if n>m or (n%2==0 and m%2==1):
    158         print("NO")
    159     else:
    160         print("YES")
    161         ans=[]
    162         if n%2==1:
    163             ans.extend([1]*(n-1)+[m-n+1])
    164         else:
    165             ans.extend([1]*(n-2)+[(m-n+2)//2]*2)
    166         print(*ans,sep=' ')
    167 ```
    168 
    169 ## [1726C - Jatayu's Balanced Bracket Sequence](/contest/1726/problem/C)
    170 
    171 Idea: [Newtech66](/profile/Newtech66 "Master Newtech66")   
    172  Editorial: [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")
    173 
    174 **Hint 1**
    175 
    176 When can a connected component begin?
    177 
    178 **Hint 2**
    179 
    180 What when two `'('` appear consecutively?
    181 
    182 **Solution**
    183 
    184 There are several ways to solve this problem (even bash-able with data structures like DSU and Segment Trees), but here is the one that is easiest to code.
    185 
    186 Tutorial is loading...
    187 
    188 **Implementation**
    189 
    190 **C++**
    191 
    192 ```
    193 #include<bits/stdc++.h>
    194 using namespace std;
    195 
    196 inline void test_case(){
    197 	
    198 	int N;
    199 	string S;
    200 
    201 	cin >> N >> S;
    202 	N <<= 1;
    203 	
    204 	int ans = 1; // ans = 1 + count("((")
    205 	for(int i = 1; i < N; ++i){
    206 		if(S[i] == '(' && S[i - 1] == '('){ // adding 1 for count("((")
    207 			++ans;
    208 		}
    209 	}
    210 
    211 	cout << ans << '\n'; 
    212 }
    213 
    214 signed main(){
    215 
    216 	ios_base::sync_with_stdio(false);
    217 	cin.tie(NULL);
    218 	cout.tie(NULL);
    219 
    220 	int test_case_number;
    221 	cin>>test_case_number;
    222 	while(test_case_number--)
    223 		test_case();
    224 	
    225 	return 0;
    226 }
    227 ```
    228 
    229 **Python**
    230 
    231 ```
    232 t=int(input())
    233 for _ in range(t):
    234     n=int(input())
    235     s=input()
    236     print(1+s.count("(")-s.count("()"))
    237 ```
    238 
    239 ## [1726D - Edge Split](/contest/1726/problem/D)
    240 
    241 Idea: [Newtech66](/profile/Newtech66 "Master Newtech66")   
    242  Editorial: [Newtech66](/profile/Newtech66 "Master Newtech66")
    243 
    244 **Hint 1**
    245 
    246 what does $m \le n + 2$ mean?
    247 
    248 **Hint 2**
    249 
    250 What if we look at a spanning tree?
    251 
    252 **Hint 3**
    253 
    254 Does any arbitrary spanning tree work?
    255 
    256 **Solution**
    257 
    258 Tutorial is loading...
    259 
    260 **Implementation**
    261 
    262 ```
    263 #include<bits/stdc++.h>
    264 using namespace std;
    265 using lol=long long int;
    266 #define endl "\n"
    267 
    268 void dfs(int u,const vector<vector<pair<int,int>>>& g,vector<bool>& vis,vector<int>& dep,vector<int>& par,string& s)
    269 {
    270     vis[u]=true;
    271     for(auto [v,idx]:g[u])
    272     {
    273         if(vis[v])  continue;
    274         dep[v]=dep[u]+1;
    275         par[v]=u;
    276         s[idx]='1';
    277         dfs(v,g,vis,dep,par,s);
    278     }
    279 }
    280 
    281 int main()
    282 {
    283 ios_base::sync_with_stdio(false);
    284 cin.tie(NULL);
    285 int _=1;
    286 cin>>_;
    287 while(_--)
    288 {
    289     int n,m;
    290     cin>>n>>m;
    291     vector<vector<pair<int,int>>> g(n+1);
    292     vector<pair<int,int>> edges(m);
    293     string s(m,'0');
    294     for(int i=0;i<m;i++)
    295     {
    296         int u,v;
    297         cin>>u>>v;
    298         edges[i]={u,v};
    299         g[u].push_back({v,i});
    300         g[v].push_back({u,i});
    301     }
    302     vector<bool> vis(n+1,false);
    303     vector<int> dep(n+1,0),par(n+1,-1);
    304     dfs(1,g,vis,dep,par,s);
    305     map<int,int> cnt;
    306     for(int i=0;i<m;i++)
    307     {
    308         if(s[i]=='0')
    309         {
    310             cnt[edges[i].first]++;
    311             cnt[edges[i].second]++;
    312         }
    313     }
    314     if(cnt.size()==3)
    315     {
    316         int mn=2*n+5,mx=0;
    317         for(auto [_,c]:cnt)
    318         {
    319             mn=min(mn,c);
    320             mx=max(mx,c);
    321         }
    322         if(mn==mx && mn==2)
    323         {
    324             vector<pair<int,int>> can;
    325             for(auto [v,_]:cnt) can.push_back({dep[v],v});
    326             sort(can.rbegin(),can.rend());
    327             int u=can[0].second;
    328             int i,j;    //replace edge i with edge j
    329             for(auto [v,idx]:g[u])
    330             {
    331                 if(s[idx]=='0') i=idx;
    332                 else if(v==par[u])    j=idx;
    333             }
    334             s[i]='1';
    335             s[j]='0';
    336         }
    337     }
    338     cout<<s<<endl;
    339 }
    340 return 0;
    341 }
    342 ```
    343 
    344 ## [1726E - Almost Perfect](/contest/1726/problem/E)
    345 
    346 Idea: [Newtech66](/profile/Newtech66 "Master Newtech66")   
    347  Editorial: [Newtech66](/profile/Newtech66 "Master Newtech66"), [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")
    348 
    349 **Hint 1**
    350 
    351 How will the permutation cycles look like ?
    352 
    353 **Hint 2**
    354 
    355 Can we fix the number of the largest sized permutation cycles and calculate the number of perfect permutations?
    356 
    357 **Hint 3**
    358 
    359 How do we handle the smaller permutation cycles?
    360 
    361 **Key fact**
    362 
    363 **Key fact:** There are only $3$ kinds of cycles in almost perfect permutations: $(i)$, $(i, j)$ and $(i, j, i + 1, j + 1)$.
    364 
    365 **Proof:**
    366 
    367 * Cycle size cannot be $3$: Take $(a, b, c)$ as a cycle with $a \lt b \lt c$, then $p_b = a$, $p^{-1}_b = c$, but $a \lt b \lt c$ implies $\lvert a - c \rvert \gt 1$.
    368 * Cycle size cannot be more than $4$: Let $(a_1, a_2, a_3, a_4, a_5, \ldots, a_k)$ be consecutive elements of a cycle with size $k$ ($k \geq 5$). This means $a_1 \ne a_5$, but $\lvert a_1 - a_3 \rvert = 1$ and $\lvert a_3 - a_5 \rvert = 1$. For now assume $a_1 - a_3 = 1$ (proof of $a_1 - a_3 = -1$ is very similar). This means $a_3 - a_5 = 1$ (as $a_1 \ne a_5$) and similarly $a_7 - a_5 = 1$ and so on (if $k \leq 6$, $a_7$ is basically $a_{7 \bmod k}$; i.e. it wraps around). Now, we observe that if $a_1 = x$, then $a_3 = x - 1$, $a_5 = x - 2$, $a_7 = x - 3$. Therefore $a_{k + 1} = x - (k + 1)$. But since that cycle is of size $k$, $a_{k + 1}$ = $a_j$, for some $j \leq k$. Therefore $(x - (k + 1)) = (x - j)$, for some $j \leq k$; which means $(k + 1) \leq k$ — A contradiction.
    369 * works for any $2$ sized cycles $(i, j)$: Proof is trivial.
    370 * works for any $4$ sized cycles $(i, j, i + 1, j + 1)$: Proof is trivial.
    371 * works **only for** $4$ sized cycles $(i, j, i + 1, j + 1)$: Consider cycle $(a, b, c, d)$. $\lvert a - c \rvert = 1$, $\lvert b - d \rvert = 1$. WLOG assume $a \lt c$ (therefore $c = a + 1$).
    372 
    373 1. *Case I*: $b \lt d$. therefore cycle is $(a, b, a + 1, b + 1)$ — of the given form.
    374 2. *Case II*: $b \gt d$. therefore cycle is $(a, d + 1, a + 1, d)$, which is same as $(d, a, d + 1, a + 1)$ — also of the given form.
    375 
    376 **Solution 1: the easy way**
    377 
    378 Special thanks to [Um_nik](/profile/Um_nik "Legendary Grandmaster Um_nik") for sharing this solution!
    379 
    380 Let's call $(i)$ as type $1$ cycles, $(i,j)$ as type $2$ cycles and $(i,j,i+1,j+1)$ as type $3$ cycles.
    381 
    382 What we will do, is we will fix the number of type $3$ and type $2$ cycles and come up with a formula.
    383 
    384 Let's say there are $s$ type $3$ cycles. We need to pick $2s$ numbers from $[1,n-1]$ such that no two are adjacent. The number of ways to do this is $\binom{n-2s}{2s}$. Then we can permute these numbers in $(2s)!$ ways and group the numbers in pairs of two, but these $s$ pairs can be permuted to get something equivalent, so we need to divide by $s!$. Hence we get:
    385 
    386 $\begin{aligned}\binom{n - 2s}{2s} \frac{(2s)!}{s!} \end{aligned}$
    387 
    388 Now, for the remaining $(n - 4s)$ elements, we know that only cycles will be of length $2$ or $1$. Let $I_k$ denote the number of permutations with cycles only of length $2$ and $1$. Then the final answer would be
    389 
    390 $\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\binom{n - 2s}{2s} \frac{(2s)!}{s!} I_{n - 4s}} \end{aligned}$
    391 
    392 Now, we would be done if we found out $I_k$ for all $k \in {1, 2, ... n}$. Observe that $I_1 = 1$ and $I_2 = 2$. Further for $k \gt 2$, the $k$-th element can appear in a cycle of length $1$, where there are $I_{k - 1}$ ways to do it; and the $k$-th element can appear in a cycle of length two, which can be done in $(k - 1) \cdot I_{k - 2}$ ways. Therefore we finally have:
    393 
    394 $\begin{aligned} I_k = I_{k - 1} + (k - 1) \cdot I_{k - 2}\end{aligned}$
    395 
    396 This completes the solution. Time complexity: $\mathcal{O}(n)$.
    397 
    398 **Solution 2: the hard way**
    399 
    400 Using the observations in **Solution 1** this can be reduced to a counting problem using generating functions. Details follow.
    401 
    402 Now, from the remaining $n-4s$ numbers, let's pick $2k$ numbers to form $k$ type $2$ cycles. We can do this in $\binom{n-4s}{2k}$ ways. Like before, we can permute them in $(2k)!$ ways, but we can shuffle these $k$ pairs around so we have to divide by $k!$. Also, $(i,j)$ and $(j,i)$ are the same cycle, so we also need to divide by $2^k$ because we can flip the pairs and get the same thing.
    403 
    404 Finally, we have the following formula:
    405 
    406 $\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\sum_{k=0}^{\lfloor \frac{n-4s}{2} \rfloor}{\frac{(2s)!}{s!}\binom{n-2s}{2s}\binom{n-4s}{2k}\frac{(2k)!}{2^k k!}}} \end{aligned}$
    407 
    408 We can simplify this to get,
    409 
    410 $\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\frac{(n-2s)!}{s!}\sum_{k=0}^{\lfloor \frac{n-4s}{2} \rfloor}{\frac{1}{2^k (n-4s-2k)! k!}}} \end{aligned}$
    411 
    412 Now, observe that the answer is in the form of two nested summations. Let us focus on precomputing the inner summation using generating functions. We define the following generating function:
    413 
    414 $\begin{aligned} P(x) &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{1}{2^k (r-2k)! k!}} \Bigg) } x^r \\ &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^r}{2^k (r-2k)! k!}} \Bigg) } \\ &=\sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^{(r - 2k)}}{(r-2k)!} \cdot \frac{x^{2k}}{2^k k!}} \Bigg) } \\ &= \sum_{r \ge 0}{ \Bigg( \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor}{\frac{x^{(r - 2k)}}{(r-2k)!} \cdot \frac{\big(\frac {x^2}{2} \big)^k}{k!}} \Bigg) } \\ &= \Bigg(\sum_{i \ge 0}{\frac{x^{i}}{i!} \Bigg)} \cdot \Bigg( \sum_{j \ge 0}{ \frac{\big(\frac {x^2}{2} \big)^j}{j!}} \Bigg) \\ P(x) &= \big(e^x \big) \cdot \big( e^{\frac {x^2}{2}} \big) = e^{x + \frac{x^2}{2}} \end{aligned} $
    415 
    416 We can compute the first few terms of $e^x = \sum_{i \ge 0}{\frac{x^{i}}{i!}}$ and $e^{\frac {x^2}{2}} = \sum_{j \ge 0}{ \frac{x^{2j}}{2^j j!}}$; and using FFT, we can multiply these (in $\mathcal O(n \log n)$ time) to get the first few terms of $P(x) = e^{x + \frac{x^2}{2}}$.
    417 
    418 Finally, we can get the answer (in $\mathcal O(n)$ time) as,
    419 
    420 $\begin{aligned} \sum_{s=0}^{\lfloor \frac{n}{4} \rfloor}{\frac{(n-2s)!}{s!} \Big([x^{n-4s}] P(x) \Big)} \end{aligned}$
    421 
    422 where $[x^m]F(x)$ is the coefficient of $x^m$ in the Taylor expansion of $F(x)$.
    423 
    424 Time complexity: $\mathcal{O}(\max{(t_i)}\log{\max{(t_i)}} + \sum{t_i})$, where $t_i$ is the value of $n$ in the $i$-th test case.
    425 
    426 **Implementation**
    427 
    428 **Solution 1**
    429 
    430 ```
    431 #include <iostream>
    432 #include <cstdio>
    433 #include <cstdlib>
    434 #include <algorithm>
    435 #include <cmath>
    436 #include <vector>
    437 #include <set>
    438 #include <map>
    439 #include <unordered_set>
    440 #include <unordered_map>
    441 #include <queue>
    442 #include <ctime>
    443 #include <cassert>
    444 #include <complex>
    445 #include <string>
    446 #include <cstring>
    447 #include <chrono>
    448 #include <random>
    449 #include <bitset>
    450 #include <array>
    451 using namespace std;
    452 
    453 #ifdef LOCAL
    454 	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
    455 #else
    456 	#define eprintf(...) 42
    457 #endif
    458 
    459 using ll = long long;
    460 using ld = long double;
    461 using uint = unsigned int;
    462 using ull = unsigned long long;
    463 template<typename T>
    464 using pair2 = pair<T, T>;
    465 using pii = pair<int, int>;
    466 using pli = pair<ll, int>;
    467 using pll = pair<ll, ll>;
    468 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    469 ll myRand(ll B) {
    470 	return (ull)rng() % B;
    471 }
    472 
    473 #define pb push_back
    474 #define mp make_pair
    475 #define all(x) (x).begin(),(x).end()
    476 #define fi first
    477 #define se second
    478 
    479 clock_t startTime;
    480 double getCurrentTime() {
    481 	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
    482 }
    483 
    484 const uint MOD = 998244353;
    485 template<uint mod = MOD> struct mint { // 1000000007  1000000009
    486 	uint x;
    487 
    488 	mint() : x(0) {}
    489 	mint(ll _x) {
    490 		_x %= mod;
    491 		if (_x < 0) _x += mod;
    492 		x = _x;
    493 	}
    494 
    495 	mint& operator += (const mint &a) {
    496 		x += a.x;
    497 		if (x >= mod) x -= mod;
    498 		return *this;
    499 	}
    500 	mint& operator -= (const mint &a) {
    501 		x += mod - a.x;
    502 		if (x >= mod) x -= mod;
    503 		return *this;
    504 	}
    505 	mint& operator *= (const mint &a) {
    506 		x = (ull)x * a.x % mod;
    507 		return *this;
    508 	}
    509 	mint pow(ll pw) const {
    510 		mint res = 1;
    511 		mint cur = *this;
    512 		while(pw) {
    513 			if (pw & 1) res *= cur;
    514 			cur *= cur;
    515 			pw >>= 1;
    516 		}
    517 		return res;
    518 	}
    519 	mint inv() const {
    520 		assert(x != 0);
    521 		uint t = x;
    522 		uint res = 1;
    523 		while(t != 1) {
    524 			uint z = mod / t;
    525 			res = (ull)res * (mod - z) % mod;
    526 			t = mod - t * z;
    527 		}
    528 		return res;
    529 	}
    530 	mint& operator /= (const mint &a) {
    531 		return *this *= a.inv();
    532 	}
    533 	mint operator + (const mint &a) const {
    534 		return mint(*this) += a;
    535 	}
    536 	mint operator - (const mint &a) const {
    537 		return mint(*this) -= a;
    538 	}
    539 	mint operator * (const mint &a) const {
    540 		return mint(*this) *= a;
    541 	}
    542 	mint operator / (const mint &a) const {
    543 		return mint(*this) /= a;
    544 	}
    545 
    546 	bool sqrt(mint &res) const {
    547 		if (mod == 2 || x == 0) {
    548 			res = *this;
    549 			return true;
    550 		}
    551 		if (pow((mod - 1) / 2) != 1) return false;
    552 		if (mod % 4 == 3) {
    553 			res = pow((mod + 1) / 4);
    554 			return true;
    555 		}
    556 		int pw = (mod - 1) / 2;
    557 		int K = 30;
    558 		while((1 << K) > pw) K--;
    559 		while(true) {
    560 			mint t = myRand(mod);
    561 			mint a = 0, b = 0, c = 1;
    562 			for (int k = K; k >= 0; k--) {
    563 				a = b * b;
    564 				b = b * c * 2;
    565 				c = c * c + a * *this;
    566 				if (((pw >> k) & 1) == 0) continue;
    567 				a = b;
    568 				b = b * t + c;
    569 				c = c * t + a * *this;
    570 			}
    571 			if (b == 0) continue;
    572 			c -= 1;
    573 			c *= mint() - b.inv();
    574 			if (c * c == *this) {
    575 				res = c;
    576 				return true;
    577 			}
    578 		}
    579 		assert(false);
    580 	}
    581 
    582 	bool operator == (const mint &a) const {
    583 		return x == a.x;
    584 	}
    585 	bool operator != (const mint &a) const {
    586 		return x != a.x;
    587 	}
    588 	bool operator < (const mint &a) const {
    589 		return x < a.x;
    590 	}
    591 };
    592 template<uint mod = MOD> struct Factorials {
    593 	using Mint = mint<mod>;
    594 	vector<Mint> f, fi;
    595 
    596 	Factorials() : f(), fi() {}
    597 	Factorials(int n) {
    598 		n += 10;
    599 		f = vector<Mint>(n);
    600 		fi = vector<Mint>(n);
    601 		f[0] = 1;
    602 		for (int i = 1; i < n; i++)
    603 			f[i] = f[i - 1] * i;
    604 		fi[n - 1] = f[n - 1].inv();
    605 		for (int i = n - 1; i > 0; i--)
    606 			fi[i - 1] = fi[i] * i;
    607 	}
    608 
    609 	Mint C(int n, int k) {
    610 		if (k < 0 || k > n) return 0;
    611 		return f[n] * fi[k] * fi[n - k];
    612 	}
    613 };
    614 template<uint mod = MOD> struct Powers {
    615 	using Mint = mint<mod>;
    616 	vector<Mint> p, pi;
    617 
    618 	Powers() : p(), pi() {}
    619 	Powers(int n, Mint x) {
    620 		n += 10;
    621 		if (x == 0) {
    622 			p = vector<Mint>(n);
    623 			p[0] = 1;
    624 		} else {
    625 			p = vector<Mint>(n);
    626 			pi = vector<Mint>(n);
    627 			p[0] = pi[0] = 1;
    628 			Mint xi = x.inv();
    629 			for (int i = 1; i < n; i++) {
    630 				p[i] = p[i - 1] * x;
    631 				pi[i] = pi[i - 1] * xi;
    632 			}
    633 		}
    634 	}
    635 
    636 	Mint pow(int n) {
    637 		if (n >= 0)
    638 			return p[n];
    639 		else
    640 			return pi[-n];
    641 	}
    642 };
    643 template<uint mod = MOD> struct Inverses {
    644 	using Mint = mint<mod>;
    645 	vector<Mint> ii;
    646 
    647 	Inverses() : ii() {}
    648 	Inverses(int n) {
    649 		n += 10;
    650 		ii = vector<Mint>(n);
    651 		ii[1] = 1;
    652 		for (int x = 2; x < n; x++)
    653 			ii[x] = Mint() - ii[mod % x] * (mod / x);
    654 	}
    655 
    656 	Mint inv(Mint x) {
    657 		assert(x != 0);
    658 		uint t = x.x;
    659 		uint res = 1;
    660 		while(t >= (int)ii.size()) {
    661 			uint z = mod / t;
    662 			res = (ull)res * (mod - z) % mod;
    663 			t = mod - t * z;
    664 		}
    665 		return ii[t] * res;
    666 	}
    667 };
    668 using Mint = mint<>;
    669 
    670 const int N = 300300;
    671 Factorials F(N);
    672 Mint F2[N];
    673 Powers P2(N, Mint(2));
    674 Mint invol[N];
    675 
    676 void precalc() {
    677 	F2[0] = 1;
    678 	for (int i = 1; i < N; i++)
    679 		F2[i] = F2[i - 1] * (2 * i - 1);
    680 	invol[0] = invol[1] = 1;
    681 	for (int i = 2; i < N; i++)
    682 		invol[i] = invol[i - 1] + invol[i - 2] * (i - 1);
    683 }
    684 
    685 void solve() {
    686 	int n;
    687 	scanf("%d", &n);
    688 	Mint ans = 0;
    689 	for (int k = 0; 4 * k <= n; k++) {
    690 		Mint cur = invol[n - 4 * k];
    691 		cur *= F.C(n - 2 * k, 2 * k);
    692 		cur *= F2[k];
    693 		cur *= P2.pow(k);
    694 		ans += cur;
    695 	}
    696 	printf("%u\n", ans.x);
    697 }
    698 
    699 int main()
    700 {
    701 	startTime = clock();
    702 //	freopen("input.txt", "r", stdin);
    703 //	freopen("output.txt", "w", stdout);
    704 
    705 	precalc();
    706 
    707 	int t;
    708 	scanf("%d", &t);
    709 	while(t--) solve();
    710 
    711 	return 0;
    712 }
    713 ```
    714 
    715 **Solution 2**
    716 
    717 ```
    718 #include<bits/stdc++.h>
    719 
    720 using namespace std;
    721 
    722 #define ll long long
    723 const int MAXN = 300005;
    724 
    725 /* PARTS OF CODE for fft taken from https://cp-algorithms.com/algebra/fft.html */
    726 
    727 const ll mod = 998244353;
    728 const ll root = 15311432; // which is basically 3 ^ 119 
    729 const ll root_1 = 469870224;
    730 const ll root_pw = (1 << 23);
    731 
    732 ll fact[MAXN + 1], ifact[MAXN + 1], sum_pow[MAXN + 1];
    733 vector<ll> P(MAXN); // this will be the first few terms of e^(x + (x^2)/2).
    734 
    735 ll fxp(ll a, ll n){ // returns a ^ n modulo mod in O(log(mod)) time
    736 	if(!n){
    737 		return 1;
    738 	}else if(n & 1){
    739 		return a * fxp(a, n ^ 1) % mod;
    740 	}else{
    741 		ll v = fxp(a, n >> 1);
    742 		return v * v % mod;
    743 	}
    744 }
    745 
    746 inline ll inverse(ll a){ // returns the modular inverse of 
    747 	return fxp(a % mod, mod -2);
    748 }
    749 
    750 void init_fact(){ // initializes fact[ ] and ifact[ ]
    751 	fact[0] = ifact[0] = 1;
    752 	for(int i = 1; i <= MAXN; ++i){
    753 		fact[i] = fact[i - 1]  * i% mod;
    754 		ifact[i] = inverse(fact[i]);
    755 	}
    756 }
    757 
    758 ll C(ll n, ll r){ // returns nCr in O(1) time
    759 	return (r > n || r < 0) ? 0 : (ifact[r] * ifact[n - r] % mod * fact[n] % mod);
    760 }
    761 
    762 // code for fft in O(nlogn)
    763 void fft(vector<ll>& a, bool invert){
    764 	int n = a.size();
    765 
    766 	/// this does the bit inversion 
    767 	for(int i = 1, j = 0; i < n; ++i){
    768 		int bit = n >> 1;
    769 		for(; j & bit; bit >>= 1){
    770 			j ^= bit;
    771 		}
    772 		j ^= bit;
    773 		if(i < j){
    774 			swap(a[i], a[j]);
    775 		}
    776 	}
    777 
    778 	for(int len = 2; len <= n; len <<= 1){
    779 		ll wlen = invert ? root_1: root;
    780 		for(int i = len; i < root_pw; i <<= 1){
    781 			wlen = wlen * wlen % mod;
    782 		}
    783 		for(int i = 0; i < n; i += len){
    784 			ll w = 1;
    785 			for(int j = 0; j < len / 2; ++j){
    786 				ll u = a[i + j], v = a[i + j + len / 2] * w % mod;
    787 				a[i + j] = u + v < mod ? u + v : u + v - mod;
    788 				a[i + j + len / 2] = u - v >= 0 ? u - v : u - v + mod;
    789 				w = w * wlen % mod;
    790 			}
    791 		}
    792 	}
    793 
    794 	if(invert){
    795 		ll n_1 = inverse(n);
    796 		for(ll& x : a){
    797 			x = x * n_1 % mod;
    798 		}
    799 	}
    800 }
    801 
    802 //multiplying two polynomials a and b using ntt in O(max(A, B)log(max(A, B))), where A, B are degrees of a, b respectively
    803 vector<ll> mul(vector<ll> const& a, vector<ll> const& b){
    804 
    805 	vector<ll> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    806 	int n = 1;
    807 	while(n < (int)a.size() + (int)b.size()){
    808 		n <<= 1;
    809 	}
    810 	fa.resize(n);
    811 	fb.resize(n);
    812 
    813 	fft(fa, false);
    814 	fft(fb, false);
    815 	for(int i = 0; i < n; ++i){
    816 		fa[i] = fa[i] * fb[i] % mod;
    817 	}
    818 	fft(fa, true);
    819 	while(fa.size() > 1 && fa[fa.size() - 1] == 0){
    820 		fa.pop_back();
    821 	}
    822 
    823 	return fa;
    824 }
    825 
    826 /* End of FFT Template */
    827 
    828 inline void init(){ // precomputes the first few terms of P(x) = e^(x + (x ^ 2) / 2)
    829 	init_fact();
    830 	vector<ll> e_x(MAXN), e_x2_by2(MAXN);
    831 	ll modular_inverse_of_2 = (mod + 1) / 2; 
    832 
    833 	for(int i = 0; i < MAXN; ++i){
    834 		e_x[i] = ifact[i]; // e^x = sum{x^k / k!}
    835 		e_x2_by2[i] = ((i & 1)) ? 0 : ifact[i / 2] * fxp(modular_inverse_of_2, i / 2) % mod; // e^((x^2)/2) = sum{(x^2k)/(k!.(2^k))}
    836 	}
    837 
    838 	P = mul(e_x, e_x2_by2); // P(x) = e^(x + (x ^ 2) / 2) = (e ^ x) . (e ^ ((x ^ 2) / 2))
    839 }
    840 
    841 void test_case(){
    842 
    843 	int N;
    844 	cin >> N;
    845 
    846 	ll ans = 0;
    847 	for(int s = 0; s <= N / 4; ++s){ // computing the answer for N using the precomputed P(x) polynomial
    848 		ans = (ans + fact[N - 2 * s] * ifact[s] % mod * P[N - 4 * s]) % mod;
    849 	}
    850 
    851 	cout << ans << '\n';
    852 }
    853 
    854 signed main(){
    855 
    856 	ios_base::sync_with_stdio(false);
    857 	cin.tie(NULL);
    858 	cout.tie(NULL);
    859 	
    860 	init();
    861 	int test_case_number;
    862 	cin>>test_case_number;
    863 	while(test_case_number--)
    864 		test_case();
    865 	
    866 	return 0;
    867 }
    868 ```
    869 
    870 ## [1726F - Late For Work (submissions are not allowed)](/contest/1726/problem/F)
    871 
    872 Please note that it is no longer possible to submit solutions to this problem on Codeforces. You can read the details [here](https://codeforces.com/blog/entry/106700).
    873 
    874 Idea: [little_angel](/profile/little_angel "Candidate Master little_angel")   
    875  Editorial: [Newtech66](/profile/Newtech66 "Master Newtech66")
    876 
    877 **Hints**
    878 
    879 **Hint 1**
    880 
    881 The $d_i$ are irrelevant. Take partial sums and add them to each $c_i$ modulo $T$.
    882 
    883 **Hint 2**
    884 
    885 If your start time is fixed, it is never beneficial to wait at a green light. Drive whenever you can.
    886 
    887 **Hint 3**
    888 
    889 Visualise the problem as $n$ parallel lines, each coloured with a red and green interval. Now imagine the car moving up (and looping back at $T$) whenever it has to wait at a red light, and shooting to the right immediately when the lights are green.
    890 
    891 **Hint 4**
    892 
    893 You can model this as a shortest paths problem.
    894 
    895 **Solution**
    896 
    897 There are solutions to this problem using lazy segment trees, or say, sets and maps. I'll describe my own solution here, which converts the problem to a shortest paths problem.
    898 
    899 First of all, the $d_i$ are irrelevant, since we can take partial sums and add them to $c_i$. In the final answer, just add the sum of all $d_i$.
    900 
    901 Now, we can offset the green (or red) intervals by the modified $c_i$ to get new red and green intervals modulo $T$.
    902 
    903 Imagine $n$ parallel lines of length $T$, with the corresponding intervals coloured red and green. Now, consider the intervals to be static. In this picture, the car can be visualised to be moving upwards along the line (looping back at $T$) when on red intervals and shooting to the right when it reaches a green interval. Notice that for a fixed starting time, it is always optimal to drive whenever you can. So essentially, fixing your start time also fixes your answer.
    904 
    905 Now let's convert this to a graph. Notice that only the endpoints of green intervals matter, so overall, we'll have $2n$ nodes in our graph, plus a dummy node representing the start of the journey that connects to all endpoints that can be reached without being blocked by a red interval, and a dummy node representing the end of the journey that connects to all endpoints from which you can reach the end without being blocked by a red interval. So in total, $2n+2$ nodes.
    906 
    907 We'll add an edge between two nodes with a weight equal to the amount of time we'll have to spend waiting for the red light to turn green. We can achieve this with a multiset storing all currently visible endpoints, and then doing a little casework to add edges from nodes blocked by the current red interval and then deleting them, and adding new ones. We'll do this only $\mathcal{O}(n)$ times. In the end, whatever is left in the multiset are all the visible endpoints and we can connect them to the dummy node for the end. We can repeat this in the backward direction to get the endpoints for the dummy node for the start, though in my code, I elected to do this with an interval union data structure.
    908 
    909 Finally, just run Dijkstra's algorithm on this graph. The answer is the sum of all $d_i$ plus the shortest path between the dummy node for the start and the dummy node for the end.
    910 
    911 Time complexity: $\mathcal{O}(n \log n)$
    912 
    913 **Implementation**
    914 
    915 ```
    916 #include<bits/stdc++.h>
    917 using namespace std;
    918 using lol=long long int;
    919 const lol inf=1e18+8;
    920  
    921 struct IntervalUnion{
    922     set<int> lf,ri;
    923     map<int,int> lr,rl;
    924     void add(int l,int r)
    925     {
    926         if(!ri.empty())
    927         {
    928             auto it=ri.lower_bound(r);
    929             if(it!=ri.end() && rl[*it]<=l)  return;
    930         }
    931         while(!lf.empty())
    932         {
    933             auto it=lf.lower_bound(l);
    934             if(it==lf.end() || r<*it)    break;
    935             int nl=*it;
    936             r=max(r,lr[nl]);
    937             rl.erase(lr[nl]);
    938             ri.erase(lr[nl]);
    939             lr.erase(nl);
    940             lf.erase(nl);
    941         }
    942         while(!ri.empty())
    943         {
    944             auto it=ri.lower_bound(l);
    945             if(it==ri.end() || r<rl[*it])   break;
    946             int nl=rl[*it];
    947             l=min(l,nl);
    948             rl.erase(lr[nl]);
    949             ri.erase(lr[nl]);
    950             lr.erase(nl);
    951             lf.erase(nl);
    952         }
    953         lf.insert(l);
    954         ri.insert(r);
    955         lr[l]=r;
    956         rl[r]=l;
    957     }
    958     bool contains(int x)
    959     {
    960         auto it=ri.upper_bound(x);
    961         if(it==ri.end())    return false;
    962         return rl[*it]<=x;
    963     }
    964 };
    965  
    966 int main()
    967 {
    968 ios_base::sync_with_stdio(false);
    969 cin.tie(NULL);
    970 int n,t;
    971 cin>>n>>t;
    972 vector<pair<int,int>> gc(n);
    973 for(auto& [g,c]:gc) cin>>g>>c;
    974 lol sum=0;
    975 for(int i=1;i<n;i++)
    976 {
    977     int d;
    978     cin>>d;
    979     sum+=d;
    980     gc[i].second=(gc[i].second+(sum%t))%t;
    981 }
    982 vector<vector<pair<int,int>>> gr(2*n+2);
    983 multiset<pair<int,int>> ms;
    984 IntervalUnion iu;
    985 for(int i=0;i<n;i++)
    986 {
    987     auto [g,c]=gc[i];
    988     int l=(g-c+t)%t,r=t-c;
    989     if(l<r)
    990     {
    991         while(!ms.empty())
    992         {
    993             auto it=ms.lower_bound({l,-1});
    994             if(it==ms.end() || it->first>=r)    break;
    995             gr[2*i].push_back({it->second,r-it->first});
    996             ms.erase(it);
    997         }
    998     }else
    999     {
   1000         while(!ms.empty())
   1001         {
   1002             auto it=ms.lower_bound({l,-1});
   1003             if(it==ms.end() || it->first>=t)    break;
   1004             gr[2*i].push_back({it->second,r+t-it->first});
   1005             ms.erase(it);
   1006         }
   1007         while(!ms.empty())
   1008         {
   1009             auto it=ms.lower_bound({0,-1});
   1010             if(it==ms.end() || it->first>=r)    break;
   1011             gr[2*i].push_back({it->second,r-it->first});
   1012             ms.erase(it);
   1013         }
   1014     }
   1015     ms.insert({r%t,2*i});
   1016     ms.insert({(l-1+t)%t,2*i+1});
   1017     if(!iu.contains(r%t)) gr[2*i].push_back({2*n+1,0});
   1018     if(!iu.contains((l-1+t)%t)) gr[2*i+1].push_back({2*n+1,0});
   1019     if(l<r) iu.add(l,r);
   1020     else
   1021     {
   1022         iu.add(l,t);
   1023         iu.add(0,r);
   1024     }
   1025 }
   1026 while(!ms.empty())
   1027 {
   1028     auto it=ms.begin();
   1029     gr[2*n].push_back({it->second,0});
   1030     ms.erase(it);
   1031 }
   1032 //do dijkstra on this graph
   1033 vector<lol> sp(2*n+2,inf);
   1034 priority_queue<pair<lol,int>,vector<pair<lol,int>>,greater<pair<lol,int>>> pq;
   1035 pq.push({0,2*n});
   1036 sp[2*n]=0;
   1037 while(!pq.empty())
   1038 {
   1039     auto [dist,u]=pq.top();
   1040     pq.pop();
   1041     if(dist>sp[u])   continue;
   1042     for(auto [v,w]:gr[u])
   1043     {
   1044         if(dist+w<sp[v])
   1045         {
   1046             sp[v]=dist+w;
   1047             pq.push({sp[v],v});
   1048         }
   1049     }
   1050 }
   1051 cout<<sum+sp[2*n+1];
   1052 return 0;
   1053 }
   1054 ```
   1055 
   1056 ## [1726G - A Certain Magical Party](/contest/1726/problem/G)
   1057 
   1058 Idea: [Newtech66](/profile/Newtech66 "Master Newtech66")   
   1059  Editorial: [Newtech66](/profile/Newtech66 "Master Newtech66"), [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")
   1060 
   1061 **Hints**
   1062 
   1063 **Hint 1**
   1064 
   1065 The happiness of a person can never decrease. It is obvious.
   1066 
   1067 **Hint 2**
   1068 
   1069 Let $T$ be the final value all elements are equal to. For all $x \lt T$, there can be at most one occurrence of $ \lt x,1 \gt $ in the array, where $ \lt a,b \gt $ means a person with happiness $a$ and personality $b$.
   1070 
   1071 **Hint 3**
   1072 
   1073 There is only one possible $T$, given by $m+n-1$.
   1074 
   1075 **Hint 4**
   1076 
   1077 If it is possible to place multiple numbers in the order at a certain point (i.e. if there are multiple possible $ \lt u,v \gt $ which when placed will all yield $ \lt T,v \gt $), it is always better to prefer the larger number, and to place a number with personality $1$ over one with personality $0$ in case of a tie.
   1078 
   1079 **Subhint**
   1080 
   1081 If $T=M$, the $ \lt M,1 \gt $ group is special, since it doesn't matter when you place it since the final happiness value will still be $M$, and it won't affect any other group's viability either.
   1082 
   1083 **Hint 5**
   1084 
   1085 For a valid ordering (if exists), the $0$ behaving people would be sorted in non-decreasing order of initial happiness.
   1086 
   1087 **Hint 6**
   1088 
   1089 For a valid ordering (if exists) and at any intermediate step, for all $1$ behaving people $ \lt u, 1 \gt $ yet to speak, the number of people with a larger happiness than $u$ cannot exceed $(T - u)$. In other words, if we placed $ \lt u, 1 \gt $ at any intermediate step, its final happiness would not exceed $T$.
   1090 
   1091 **Solution**
   1092 
   1093 Tutorial is loading...
   1094 
   1095 **Implementation**
   1096 
   1097 ```
   1098 #include<bits/stdc++.h>
   1099 
   1100 #define ll long long
   1101 #define pb push_back
   1102 #define mp make_pair
   1103 #define pii pair<int, int>
   1104 #define pll pair<ll, ll>
   1105 #define ff first 
   1106 #define ss second
   1107 #define vi vector<int>
   1108 #define vl vector<ll>
   1109 #define vii vector<pii>
   1110 #define vll vector<pll>
   1111 #define FOR(i,N) for(i=0;i<(N);++i)
   1112 #define FORe(i,N) for(i=1;i<=(N);++i)
   1113 #define FORr(i,a,b) for(i=(a);i<(b);++i)
   1114 #define FORrev(i,N) for(i=(N);i>=0;--i)
   1115 #define F0R(i,N) for(int i=0;i<(N);++i)
   1116 #define F0Re(i,N) for(int i=1;i<=(N);++i)
   1117 #define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
   1118 #define F0Rrev(i,N) for(int i=(N);i>=0;--i)
   1119 #define all(v) (v).begin(),(v).end()
   1120 #define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
   1121 #define ldd long double
   1122 
   1123 using namespace std;
   1124 
   1125 const int Alp = 26;
   1126 const int __PRECISION = 9;
   1127 const int inf = 1e9 + 8;
   1128 
   1129 const ldd PI = acos(-1);
   1130 const ldd EPS = 1e-7;
   1131 
   1132 const ll MOD = 998244353;
   1133 const ll MAXN = 260007;
   1134 const ll ROOTN = 320;
   1135 const ll LOGN = 18;
   1136 const ll INF = 1e18 + 1022;
   1137 
   1138 int N;
   1139 int A[MAXN];
   1140 bool B[MAXN];
   1141 vi a[2];
   1142 pii people[MAXN];
   1143 ll fact[MAXN + 1], ifact[MAXN + 1];
   1144 
   1145 ll fxp(ll a, ll n){
   1146 	if(n == 0) return 1;
   1147 	if(n % 2 == 1) return a * fxp(a, n - 1) % MOD;
   1148 	return fxp(a * a % MOD, n / 2);
   1149 }
   1150 
   1151 ll inv(ll a){
   1152 	return fxp(a % MOD, MOD - 2);
   1153 }
   1154 void init(){
   1155 	fact[0] = ifact[0] = 1;
   1156 	F0Re(i, MAXN){
   1157 		fact[i] = fact[i - 1] * i % MOD;
   1158 		ifact[i] = inv(fact[i]);
   1159 	}
   1160 }
   1161 
   1162 struct SegTree_sum{
   1163 	int st[4*MAXN];
   1164 	void upd(int node, int ss, int se, int i, int val){
   1165 		if(ss > i or se < i)	return;
   1166 		if(ss == se)	{st[node] += val; return;}
   1167 		int mid = (ss + se) / 2;
   1168 		upd(node*2+1, ss, mid, i, val);
   1169 		upd(node*2+2, mid+1, se, i, val);
   1170 		st[node] = st[node*2+1] + st[node*2+2];
   1171 	}
   1172 	int quer(int node,int ss, int se, int l, int r){
   1173 		if(ss > r or se < l)	return 0;
   1174 		if(ss >= l and se <= r)	return st[node];
   1175 		int mid = (ss + se)/2;
   1176 		return quer(node*2+1, ss, mid, l ,r) + quer(node*2+2, mid + 1, se, l,r);
   1177 	}
   1178 	SegTree_sum()	{F0R(i, MAXN*4) st[i] = 0;}
   1179 	inline void update(int i, int val) {upd(0, 0, 2 * MAXN, i, val);}
   1180 	inline int query(int l, int r) {return quer(0, 0, 2 * MAXN, l, r);}
   1181 }S_sum;
   1182 
   1183 struct Segtree_max{
   1184 	int st[4 * MAXN], lz[4 * MAXN];
   1185 	inline void push(int node, int ss, int se){
   1186 		if(lz[node] == 0) return;
   1187 		st[node] += lz[node];
   1188 		if(ss != se) lz[node * 2 + 1] += lz[node], lz[node * 2 + 2] += lz[node];
   1189 		lz[node] = 0;
   1190 	}
   1191 	void upd(int node, int ss, int se, int l, int r, int val){
   1192 		push(node, ss, se);
   1193 		if(ss > r or se < l) return;
   1194 		if(ss >= l and se <= r) {lz[node] += val; push(node, ss, se); return;}
   1195 		int mid = (ss + se)/2;
   1196 		upd(node * 2 + 1, ss, mid, l, r, val);
   1197 		upd(node * 2 + 2, 1 + mid, se, l, r, val);
   1198 		st[node] = max(st[node * 2 + 1], st[node * 2 + 2]);
   1199 	}
   1200 	int quer(int node, int ss, int se, int tar){
   1201 		push(node, ss, se);
   1202 		if(st[node] < tar || st[node] > tar){
   1203 			return -1;
   1204 		}
   1205 		if(ss == se){
   1206 			return ss;
   1207 		}
   1208 		int mid = (ss + se) / 2;
   1209 		push(node * 2 + 1, ss, mid);
   1210 		push(node * 2 + 2, mid + 1, se);
   1211 		return (st[node * 2 + 2] < tar) ? quer(node * 2 + 1, ss, mid, tar) : quer(node * 2 + 2, mid + 1, se, tar);
   1212 	}
   1213 	Segtree_max() {F0R(i,MAXN * 4) st[i] = - 10 * MAXN, lz[i] = 0;}
   1214 	inline void update(int l, int r, ll val) {if(l <= r) upd(0, 0, 2 * MAXN, l, r, val);}
   1215 	inline ll query(int v) {return quer(0, 0, 2 * MAXN, v);}
   1216 }S_max;
   1217 
   1218 signed main(){
   1219 
   1220 	
   1221 	ios_base::sync_with_stdio(false);
   1222 	cin.tie(NULL);
   1223 	cout.tie(NULL);
   1224 	
   1225 	init();
   1226 	cin >> N;
   1227 	F0R(i, N){
   1228 		cin >> A[i];
   1229 	}
   1230 	F0R(i, N){
   1231 		cin >> B[i];
   1232 	}
   1233 
   1234 	F0R(i, N){
   1235 		a[B[i]].pb(A[i]);
   1236 		people[i] = {A[i], B[i]};
   1237 		S_sum.update(A[i], 1);
   1238 	}
   1239 
   1240 	sort(all(a[0]));
   1241 	sort(all(a[1]));
   1242 	sort(people, people + N);
   1243 	int m = people[0].ff;
   1244 	int M = people[N - 1].ff;
   1245 	int T = people[0].ff + N - 1;
   1246 
   1247 	if(m == M){
   1248 		cout << fact[N] << '\n';
   1249 		return 0;
   1250 	}else if(people[0].ss == 0){
   1251 		cout << "0\n";
   1252 		return 0;
   1253 	}else if(M > T){
   1254 		cout << "0\n";
   1255 		return 0;
   1256 	}
   1257 
   1258 	int T_cnt = 0;
   1259 
   1260 	F0R(i, (int)a[1].size()){
   1261 		if(a[1][i] == T){
   1262 			++T_cnt;
   1263 		}else if(i + 1 < (int)a[1].size() && a[1][i] == a[1][i + 1]){
   1264 			cout << "0\n";
   1265 			return 0;
   1266 		}
   1267 	}
   1268 
   1269 	ll ans = fact[N] * ifact[N - T_cnt] % MOD;
   1270 	int p = -1, t = 0;
   1271 	for(int x : a[0]){
   1272 		if(p != x){
   1273 			ans = ans * fact[t] % MOD;
   1274 			t = 0;
   1275 		}
   1276 		++t;
   1277 		p = x;
   1278 	}
   1279 	ans = ans * fact[t] % MOD;
   1280 
   1281 	int ptr = 0;
   1282 
   1283 	for(int x : a[1]){
   1284 		if(x == T){
   1285 			break;
   1286 		}
   1287 		int y = x + S_sum.query(x + 1, 2 * MAXN);
   1288 		S_max.update(x, x, y + 10 * MAXN);
   1289 	}
   1290 
   1291 	vii sequence(T_cnt, mp(T, 1));
   1292 
   1293 	F0R(i, N - T_cnt){
   1294 		int zero = T + 1, one = T + 1;
   1295 		if(ptr < (int)a[0].size() && S_sum.query(1, a[0][ptr] - 1) + a[0][ptr] == T){
   1296 			zero = a[0][ptr];
   1297 		}
   1298 		one = S_max.query(T);
   1299 		if(one == -1 && zero == T + 1){
   1300 			cout << "0\n";
   1301 			return 0;
   1302 		}
   1303 		if(zero == T + 1 || one >= zero){
   1304 			sequence.pb({one, 1});
   1305 			S_max.update(one, one, - 10 * N);
   1306 			S_max.update(one + 1, T - 1, 1);
   1307 			S_sum.update(one, -1);
   1308 			S_sum.update(T, 1);
   1309 		}else{
   1310 			sequence.pb({zero, 0});
   1311 			S_sum.update(zero, -1);
   1312 			S_sum.update(T, 1);
   1313 			S_max.update(zero, T - 1, 1);
   1314 			++ptr;
   1315 		}
   1316 	}
   1317 	cout << ans << '\n';
   1318 	
   1319 	return 0;
   1320 }
   1321 ```
   1322 
   1323 ## [1726H - Mainak and the Bleeding Polygon](/contest/1726/problem/H)
   1324 
   1325 Idea: [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")   
   1326  Editorial: [Newtech66](/profile/Newtech66 "Master Newtech66"), [anubhavdhar](/profile/anubhavdhar "Master anubhavdhar")
   1327 
   1328 **Hint 1**
   1329 
   1330 What role does the angles of the polygon play?
   1331 
   1332 **Hint 2**
   1333 
   1334 Is there some overlap in the area of two such regions? How do we account for that?
   1335 
   1336 **Solution**
   1337 
   1338 Tutorial is loading...
   1339 
   1340 **Implementation**
   1341 
   1342 ```
   1343 #include<bits/stdc++.h>
   1344 using namespace std;
   1345 using lol=long long int;
   1346 using ldd=long double;
   1347 #define endl "\n"
   1348 const ldd PI=acos(-1.0);
   1349 const int ITERATIONS = 60;
   1350 const int PRECISION = 11;
   1351 
   1352 struct Point{
   1353     lol x,y;
   1354     Point& operator-=(const Point& rhs){
   1355         x-=rhs.x,y-=rhs.y;
   1356         return *this;
   1357     }
   1358     friend Point operator-(Point lhs,const Point& rhs){
   1359         lhs -= rhs;
   1360         return lhs;
   1361     }
   1362 };
   1363 std::istream& operator>>(std::istream& is, Point& obj){
   1364     is>>obj.x>>obj.y;
   1365     return is;
   1366 }
   1367 
   1368 ldd norm(Point p){
   1369     return p.x*p.x+p.y*p.y;
   1370 }
   1371 ldd cross_product(Point a,Point b){
   1372     return a.x*b.y-a.y*b.x;
   1373 }
   1374 ldd dot_product(Point a,Point b){
   1375     return a.x*b.x+a.y*b.y;
   1376 }
   1377 ldd getalpha(Point a,Point b,Point c){
   1378     return atan2l(cross_product(c-b,a-b),dot_product(c-b,a-b));
   1379 }
   1380 ldd getarea(Point a,Point b,Point c){
   1381     Point l1=c-b,l2=a-b;
   1382     return (dot_product(l1,l2)/cross_product(l1,l2)+atan2l(cross_product(l1,l2),-dot_product(l1,l2))*((norm(l1)*norm(l2))/(cross_product(l1,l2)*cross_product(l1,l2))+2.0))/16.0;
   1383 }
   1384 
   1385 ldd f(ldd theta, ldd alpha){
   1386 	return -cos(theta)+(1.0/tan(alpha))*sin(theta) + (cos(theta)*(1.0/tan(alpha))+sin(theta)) * (sin(2*theta)/2.0);
   1387 }
   1388 ldd g(ldd theta, ldd alpha){
   1389 	return (cos(theta)*(1.0/tan(alpha))+sin(theta)) * (1.0 - cos(2*theta))/2.0;
   1390 }
   1391 ldd get_x(ldd y, ldd alpha, ldd & theta){
   1392 	ldd lo = alpha, hi = PI;
   1393 	for(int it = 0; it < ITERATIONS; ++it){
   1394 		theta = (lo + hi) / 2.0;
   1395 		ldd y_guess = g(theta, alpha);
   1396 		if(y > y_guess){
   1397 			hi = theta;
   1398 		}else{
   1399 			lo = theta;
   1400 		}
   1401 	}
   1402 
   1403 	return f(theta, alpha);
   1404 }
   1405 ldd A(ldd theta, ldd alpha){
   1406 	return (sin(2 * (alpha - 3 * theta)) - sin(2 * (alpha - 2 * theta)) - 4 * sin(2 * (alpha - theta)) - sin(2 * (alpha + theta))
   1407 			- 4 * theta * cos(2 * alpha) + 8 * theta - 2 * sin(4 * theta)) / (64.0 * sin(alpha) * sin(alpha));
   1408 }
   1409 ldd find_overlap_area(ldd alpha_1, ldd alpha_2, ldd L){
   1410 
   1411 	ldd lo = 0, hi = sin(max(alpha_1, alpha_2));
   1412 	ldd theta_1 = PI, theta_2 = PI;
   1413 
   1414 	for(int it = 0; it < ITERATIONS; ++it){
   1415 		ldd mid_y = (lo + hi) / 2;
   1416 		ldd x1 = get_x(mid_y, alpha_1, theta_1);
   1417 		ldd x2 = L - get_x(mid_y, alpha_2, theta_2);
   1418 		if(x1 < x2){
   1419 			hi = mid_y;
   1420 		}else{
   1421 			lo = mid_y;
   1422 		}
   1423 
   1424 	}
   1425 
   1426 	return (A(PI, alpha_1) + A(PI, alpha_2)) - (A(theta_1, alpha_1) + A(theta_2, alpha_2));
   1427 }
   1428 
   1429 int main()
   1430 {
   1431 ios_base::sync_with_stdio(false);
   1432 cin.tie(NULL);
   1433 int n;
   1434 cin>>n;
   1435 vector<Point> v(n);
   1436 for(auto& p:v)  cin>>p;
   1437 if(n == 4){
   1438     int MY = max({v[0].y, v[1].y, v[2].y, v[3].y});
   1439     int my = min({v[0].y, v[1].y, v[2].y, v[3].y});
   1440     int MX = max({v[0].x, v[1].x, v[2].x, v[3].x});
   1441     int mx = min({v[0].x, v[1].x, v[2].x, v[3].x});
   1442     if(MY - my == 1 || MX - mx == 1){
   1443         cout << fixed << setprecision(PRECISION) << 1.0 * (MY - my) * (MX - mx) << endl;
   1444         exit(0);
   1445     }
   1446 }
   1447 double ans=0.0;
   1448 for(int i=0;i<n;i++){
   1449     ans+=getarea(v[(i-1+n)%n],v[i],v[(i+1)%n]);
   1450 }
   1451 for(int i=0;i<n;i++){
   1452     Point a=v[(i-1+n)%n],b=v[i],c=v[(i+1)%n],d=v[(i+2)%n];
   1453     if(norm(c-b)<3){
   1454         ans-=find_overlap_area(getalpha(a,b,c),getalpha(b,c,d),sqrt(norm(c-b)));
   1455     }
   1456 }
   1457 cout<<fixed<<setprecision(PRECISION)<<ans;
   1458 return 0;
   1459 }
   1460 ```
   1461 
   1462 ---
   1463 
   1464 ## Vote for the problems here!
   1465 
   1466 Feel free to vote for your opinion of each problem, and the best problem of the contest.
   1467 
   1468 **Vote here**
   1469 
   1470 **A**
   1471 
   1472 * Best problem:
   1473 * Good problem:
   1474 * Average problem:
   1475 * Bad problem:
   1476 * Did not solve:
   1477 
   1478 **B**
   1479 
   1480 * Best problem:
   1481 * Good problem:
   1482 * Average problem:
   1483 * Bad problem:
   1484 * Did not solve:
   1485 
   1486 **C**
   1487 
   1488 * Best problem:
   1489 * Good problem:
   1490 * Average problem:
   1491 * Bad problem:
   1492 * Did not solve:
   1493 
   1494 **D**
   1495 
   1496 * Best problem:
   1497 * Good problem:
   1498 * Average problem:
   1499 * Bad problem:
   1500 * Did not solve:
   1501 
   1502 **E**
   1503 
   1504 * Best problem:
   1505 * Good problem:
   1506 * Average problem:
   1507 * Bad problem:
   1508 * Did not solve:
   1509 
   1510 **F**
   1511 
   1512 * Best problem:
   1513 * Good problem:
   1514 * Average problem:
   1515 * Bad problem:
   1516 * Did not solve:
   1517 
   1518 **G**
   1519 
   1520 * Best problem:
   1521 * Good problem:
   1522 * Average problem:
   1523 * Bad problem:
   1524 * Did not solve:
   1525 
   1526 **H**
   1527 
   1528 * Best problem:
   1529 * Good problem:
   1530 * Average problem:
   1531 * Bad problem:
   1532 * Did not solve: