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: