2030.md (33902B)
1 Source: https://codeforces.com/blog/entry/135218 2 3 Below is a timeline of the changes made to the round from start to finish. I hope this can depict what setting a contest is actually like for aspiring problemsetters. Please give me feedback about this in the comments. What else about the round would you like to know? Was this helpful? 4 5 **Round Timeline** 6 7 To denote problems, I will use quotes to denote the number of problems proposed for that postion so far (e.g. A' represents the first A proposed for the round, A'' represents second A proposed, etc). If the problem is in the final set, then it will be **bolded**. For dates, I will use the american standard notation (mm/dd). 8 9 Also, I will not go in detail about why problems were rejected/unused because they might appear in the future. 10 11 8/11: [Codeforces Round 965 (Div. 2)](/contest/1998 "Codeforces Round 965 (Div. 2)") has just concluded and [sum](/profile/sum "Мастер sum") has shipped himself off to college and won't have time due to ~~attending frat parties~~ his studies. I invite [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") to problemset with me. We decide to get cooking straight away. 12 13 8/12: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes D'. Gets accepted. 14 15 8/13: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes E'. Problem accepted for backup. 16 17 8/14: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes D''. Problem accepted for backup. 18 19 8/19: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes E'', F' and G'. Both gets accepted for main set at the time. Seriously, bro just became the new BledDest. 20 21 8/21: We got bored and decided to focus on [Codeforces Round 971 (Div. 4)](/contest/2009 "Codeforces Round 971 (Div. 4)"). Due to difficulty issues, we transfered problem E from that contest to problem B1 and B2 for this contest. B2 ultimately became **D** :) 22 23 8/22: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes B', but [satyam343](/profile/satyam343 "Мастер satyam343") buffs it into **F** instead. Somewhere along the lines I also came up with A' and B'', both getting initially accepted. 24 25 8/23: Round gets put up for testing with 7 problems. 26 27 8/25: I came up with an idea for D'''. Also, [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes **C**, but initially gets ignored lmao. 28 29 8/26: [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D''''. Later, I also propose E''''. 30 31 8/28: [satyam343](/profile/satyam343 "Мастер satyam343") tries to modifies B'' again into C''. [sum](/profile/sum "Мастер sum") wakes up from his slumber and proposes F''. 32 33 8/29: I propose A''. 34 35 8/31: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes D''''' and gets accepted. 36 37 9/2: [satyam343](/profile/satyam343 "Мастер satyam343") buffs D''' and it became [NOTEQUALTREE](https://www.codechef.com/problems/NOTEQUALTREE). 38 39 9/6: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") and [satyam343](/profile/satyam343 "Мастер satyam343") modifies D' and it becomes **G** (G1). Later, [A_G](/profile/A_G "Международный гроссмейстер A_G") solved it in subquadratic, and it became G2. 40 41 9/9: I modify B'' into D''''''. 42 43 9/11: [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D'''''''. We hold a poll in our testing server to choose the victor among D'''''' and D'''''''. 44 45 9/12: I invent and propose C''', but wasn't accepted. [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D'''''''', but unused due to difficulty issues. 46 47 9/14: I invent and propose D''''''''', which was unused due to difficulty issues. Later that night, the aforementioned poll concludes, crowning D'''''' with 7 votes to 2. However, both candidates had difficulty issues so we still decided against using any of them (essentially we polled for nothing). 48 49 9/15: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes B'''' and gets initially accepted, however, was later rejected. 50 51 9/17: I propose A''' but it wasn't great. 52 53 9/20: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") brings **C** up again and it gets prepared. 54 55 9/23: [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D'''''''''', but as the original author of B'', I didn't like it. 56 57 9/24: [satyam343](/profile/satyam343 "Мастер satyam343") modifies D''''''''' into D''''''''''', and it gets prepared. 58 59 9/28: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") modifies a unused problem I proposed for [Codeforces Round 965 (Div. 2)](/contest/1998 "Codeforces Round 965 (Div. 2)") into A'''', but unused due to difficulty issues. 60 61 9/30: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes and prepares **B**. Later that night, [satyam343](/profile/satyam343 "Мастер satyam343") has conflicting thoughts whether to replace D''''''''''' yet again, but I ~~held him at gunpoint to accept the problem~~ spent 30 minutes convincing him that it is a good problem. This problem became **E**. For those of you who enjoyed the problem, you're welcome lmao. 62 63 10/02 — 10/17: Final testing and preparation. 64 65 10/13: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes current **A**. 66 67 ## Please check out this amazing animated [video tutorial](https://www.youtube.com/watch?v=CpSIK4YPi00) by one of our beloved testers [redpanda](/profile/redpanda "Эксперт redpanda")!!! 68 69 #### [2030A - Подарок от орангутана](/contest/2030/problem/A "Codeforces Round 979 (Div. 2)") 70 71 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") 72 Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") 73 74 **Solution** 75 76 First, what is the maximum possible value of $c_i-b_j$ for any $i,j$? Since $c_i$ is the maximum element of some subset of $a$ and $b_i$ is the minimum element of some subset of $a$, the maximum possible value of $c_i-b_j$ is $max(a)-min(a)$. 77 78 Also note that $c_1=b_1$ for any reordering of $a$. By reordering such that the largest element of $a$ appears first and the smallest element of $a$ appears second, the maximum possible value of the score is achieved. This results in a score of $(max(a)-min(a))\cdot(n-1)$. 79 80 **Code (Python)** 81 82 ``` 83 for i in range(int(input())): 84 n = int(input()) 85 mx = 0 86 mn= 1000000 87 lst = input().split() 88 for j in range(n): 89 x = int(lst[j]) 90 mx = max(mx, x) 91 mn = min(mn, x) 92 print((mx-mn)*(n-1)) 93 ``` 94 95 #### [2030B - Минимизируйте единичность](/contest/2030/problem/B "Codeforces Round 979 (Div. 2)") 96 97 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") 98 Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") 99 100 **Solution** 101 102 **Observation**: $f(t)-g(t)$ is odd. 103 104 Proof: $f(t)+g(t)$ is the set of all non-empty subsets of $t$, which is $2^{|t|}-1$, which is odd. The sum and difference of two integers has the same parity, so $f(t)-g(t)$ is always odd. 105 106 By including exactly one $1$ in the string $s$, we can make $f(s)=2^{n-1}-1$ and $g(s)=2^{n-1}$, or $f(s)-g(s)=1$ by the multiplication principle. Clearly, this is the best we can do. So, we print out any string with exactly one $1$. 107 108 **Code (C++)** 109 110 ``` 111 #include <bits/stdc++.h> 112 using namespace std; 113 114 int main() { 115 int t; 116 cin >> t; 117 while(t--) { 118 int n; 119 cin >> n; 120 cout << '1'; 121 for(int i = 1; i < n; i++) cout << '0'; 122 cout << endl; 123 } 124 } 125 ``` 126 127 #### [2030C - ИСТИННАЯ битва](/contest/2030/problem/C "Codeforces Round 979 (Div. 2)") 128 129 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") 130 Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") 131 132 **Solution** 133 134 Let's understand what Alice wants to do. She wants to separate a statement that evaluates to `true` between two `or`'s. This guarantees her victory since `or` is evaluated after all `and`'s. 135 136 First, if the first or last boolean is `true`, then Alice instantly wins by placing `or` between the first and second, or second to last and last booleans. 137 138 Otherwise, if there are two `true`'s consecutively, Alice can also win. Alice may place `or` before the first of the two on her first move. If Bob does not put his operator between the two `true`'s, then Alice will put an `or` between the two `true`'s on her next move and win. Otherwise, Bob does place his operator between the two `true`'s. However, no matter what Bob placed, the two `true`'s will always evaluate to `true`, so on her second move Alice can just place an `or` on the other side of the two `true`'s to win. 139 140 We claim these are the only two cases where Alice wins. This is because otherwise, there does not contain two `true`'s consecutively. Now, whenever Alice places an `or` adjacent to a `true`, Bob will respond by placing `and` after the `true`, which will invalidate this clause to be false. 141 142 **Code (C++)** 143 144 ``` 145 #include <bits/stdc++.h> 146 using namespace std; 147 148 int main() { 149 int t; 150 cin >> t; 151 while(t--) { 152 int n; 153 cin >> n; 154 string s; 155 cin >> s; 156 vector<int> v(n); 157 for(int i = 0; i < n; i++) { 158 if(s[i]=='1') v[i]=1; 159 } 160 bool win = false; 161 if(v[0]||v[n-1]) win=true; 162 for(int i = 1; i < n; i++) { 163 if(v[i]&&v[i-1]) win=true; 164 } 165 if(win) cout << "YES" << endl; 166 else cout << "NO" << endl; 167 } 168 } 169 ``` 170 171 #### [2030D - Любимая перестановка ЧТД](/contest/2030/problem/D "Codeforces Round 979 (Div. 2)") 172 173 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [cry](/profile/cry "Международный мастер cry") 174 Analysis: [cry](/profile/cry "Международный мастер cry") 175 176 **Solution** 177 178 Observation: Through a series of swaps, we can swap an element from position $i$ to position $j$ (WLOG, assume $i \lt j$) if there is no such $k$ such that $i \leq k \lt j$ such that $s_k = \texttt{L}$ and $s_{k+1} = \texttt{R}$. 179 180 Let's mark all indices $i$ such that $s_i = \texttt{L}$ and $s_{i+1} = \texttt{R}$ as bad. If $pos_i$ represents the position of $i$ in $p$, then we must make sure it is possible to swap from $\min(i, pos_i)$ to $\max(i, pos_i)$. As you can see, we can model these conditions as intervals. We must make sure there are no bad indices included in any intervals. 181 182 We need to gather indices $i$ such that $i$ is included in at least one interval. This can be done with difference array. Let $d_i$ denote the number of intervals that include $i$. If $d_i \gt 0$, then we need to make sure $i$ is not a bad index. 183 184 We can keep all bad indices in a set. Notice that when we update $i$, we can only potentially toggle indices $i$ and $i-1$ from good to bad (or vice versa). For example, if $s_i = \texttt{L}$, $s_i = \texttt{R}$, $d_i \gt 0$ and index $i$ is not in the bad set, then we will insert it. After each query, if the bad set is empty, then the answer is "YES". 185 186 **Code (C++)** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 using namespace std; 192 193 int main() { 194 int t; 195 cin >> t; 196 while(t--) { 197 int n,q; 198 cin >> n >> q; 199 vector<int> perm(n); 200 for(int i = 0; i < n; i++) cin >> perm[i]; 201 for(int i = 0; i < n; i++) perm[i]--; 202 vector<int> invperm(n); 203 for(int i = 0; i < n; i++) invperm[perm[i]]=i; 204 vector<int> diffArr(n); 205 for(int i = 0; i < n; i++) { 206 diffArr[min(i, invperm[i])]++; 207 diffArr[max(i, invperm[i])]--; 208 } 209 for(int i = 1; i < n; i++) diffArr[i]+=diffArr[i-1]; 210 string s; 211 cin >> s; 212 set<int> problems; 213 for(int i = 0; i < n-1; i++) { 214 if(s[i]=='L'&&s[i+1]=='R'&&diffArr[i]!=0) { 215 problems.insert(i); 216 } 217 } 218 while(q--) { 219 int x; 220 cin >> x; 221 x--; 222 if(s[x]=='L') { 223 s[x]='R'; 224 } else { 225 s[x]='L'; 226 } 227 if(s[x-1]=='L'&&s[x]=='R'&&diffArr[x-1]!=0) { 228 problems.insert(x-1); 229 } else { 230 problems.erase(x-1); 231 } 232 if(s[x]=='L'&&s[x+1]=='R'&&diffArr[x]!=0) { 233 problems.insert(x); 234 } else { 235 problems.erase(x); 236 } 237 if(problems.size()) { 238 cout << "NO" << endl; 239 } else { 240 cout << "YES" << endl; 241 } 242 } 243 } 244 } 245 ``` 246 247 #### [2030E - MEXимизируйте счёт](/contest/2030/problem/E "Codeforces Round 979 (Div. 2)") 248 249 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [cry](/profile/cry "Международный мастер cry"), [satyam343](/profile/satyam343 "Мастер satyam343") 250 Analysis: [cry](/profile/cry "Международный мастер cry") 251 252 **Solution** 253 254 Observation: The score of $b$ is equivalent to $f_0$ + $\min(f_0, f_1)$ + $\ldots$ + $\min(f_0, \ldots, f_{n-1})$ where $f_i$ stores the frequency of integer $i$ in $b$. 255 256 Intuition: We can greedily construct the $k$ arrays by repeating this step: Select the minimum $j$ such that $f_j = 0$ and $\min(f_0, \ldots f_{j-1}) \gt 0$, and construct the array $[0, 1, \ldots, j-1]$. This is optimal because every element we add will increase the MEX by $1$, which will increase the score by $1$. If we add $j$, the MEX will not increase. Also, when we add an element, we cannot increase the score by more than $1$. Adding less than $j$ elements cannot increase MEX for future arrays. 257 258 From this observation, we can see that only the frequency array of $a$ matters. From now on, let's denote the frequency of $i$ in $a$ as $f_i$. We can find the sum over all subsequences using dynamic programming. 259 260 Let's denote $dp[i][j]$ as the number of subsequences containing only the first $i$ integers and $min(f_0, \ldots, f_i) = j$. Initially, $dp[0][i] = \binom{f_0}{i}$. To transition, we need to consider two cases: 261 262 In the first case, let's assume $j \lt \min(f_0, \ldots, f_{i-1})$. The number of subsequences that can be created is $(\sum_{k=j+1}^n dp[i-1][k]) \cdot \binom{f_i}{j}$. That is, all the subsequences from previous length such that it is possible for $j$ to be the new minimum, multiplied by the number of subsequences where $f_i = j$. 263 264 In the second case, let's assume $j \geq \min(f_0, \ldots, f_{i-1})$. The number of subsequences that can be created is $(\sum_{k=j}^{f_i} \binom{f_i}{k}) \cdot dp[i-1][j]$. That is, all subsequences containing at least $j$ elements of $i$, multiplied by all previous subsequences with minimum already equal to $j$. 265 266 The total score is $dp[i][j] \cdot j \cdot 2^{f_{i+1} + \dots + f_{n-1}}$ over the length of the prefix $i$ and prefix minimum $j$. 267 268 We can speed up the calculations for both cases using suffix sums, however, this still yields an $O(n^2)$ algorithm. However, $j$ is bounded to the interval $[1, f_i]$ for each $i$. Since the sum of $f_i$ is $n$, the total number of secondary states is $n$. This becomes just a constant factor, so the total complexity is $O(n)$. 269 270 **Code (C++)** 271 272 ``` 273 #include <bits/stdc++.h> 274 #define int long long 275 #define ll long long 276 #define pii pair<int,int> 277 #define piii pair<pii,pii> 278 #define fi first 279 #define se second 280 #pragma GCC optimize("O3,unroll-loops") 281 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 282 using namespace std; 283 284 const int MX = 2e5; 285 ll fact[MX+1]; 286 ll ifact[MX+1]; 287 ll MOD=998244353; 288 289 ll binPow(ll base, ll exp) { 290 ll ans = 1; 291 while(exp) { 292 if(exp%2) { 293 ans = (ans*base)%MOD; 294 } 295 base = (base*base)%MOD; 296 exp /= 2; 297 } 298 return ans; 299 } 300 301 int nCk(int N, int K) { 302 if(K>N||K<0) { 303 return 0; 304 } 305 return (fact[N]*((ifact[K]*ifact[N-K])%MOD))%MOD; 306 } 307 308 void ICombo() { 309 fact[0] = 1; 310 for(int i=1;i<=MX;i++) { 311 fact[i] = (fact[i-1]*i)%MOD; 312 } 313 ifact[MX] = binPow(fact[MX],MOD-2); 314 for(int i=MX-1;i>=0;i--) { 315 ifact[i] = (ifact[i+1]*(i+1))%MOD; 316 } 317 } 318 319 void solve() { 320 int n, ans=0; cin >> n; 321 vector<int> c(n); 322 for (int r:c) { 323 cin >> r; c[r]++; 324 } 325 vector<vector<int>> dp(n,vector<int>(1)); 326 vector<int> ps, co; 327 for (int i = 1; i <= c[0]; i++) dp[0].push_back(nCk(c[0],i)); 328 for (int i = 1; i < n; i++) { 329 ps.resize(1); co=ps; 330 for (int r:dp[i-1]) ps.push_back((ps.back()+r)%MOD); 331 int m=ps.size()-1; 332 dp[i].resize(min(m,c[i]+1)); 333 for (int j = 0; j <= c[i]; j++) co.push_back((co.back()+nCk(c[i],j))%MOD); 334 for (int j = 1; j < dp[i].size(); j++) dp[i][j]=nCk(c[i],j)*(ps[m]-ps[j]+MOD)%MOD+(co.back()-co[j+1]+MOD)*dp[i-1][j]%MOD; 335 } 336 int j=0; 337 for (auto r:dp) { 338 n-=c[j++]; 339 for (int i = 1; i < r.size(); i++) (ans+=i*r[i]%MOD*binPow(2,n))%=MOD; 340 } 341 cout << ans << "\n"; 342 } 343 344 int32_t main() { 345 ios::sync_with_stdio(0); cin.tie(0); 346 ICombo(); 347 int t = 1; cin >> t; 348 while (t--) solve(); 349 } 350 ``` 351 352 #### [2030F - Орангутано-одобренный массив](/contest/2030/problem/F "Codeforces Round 979 (Div. 2)") 353 354 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [satyam343](/profile/satyam343 "Мастер satyam343") 355 Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") 356 357 **Solution** 358 359 First, let's try to find whether a single array is orangutan-approved or not. 360 361 **Claim**: The array $b$ of size $n$ is not orangutan-approved if and only if there exists indices $1\leq w \lt x \lt y \lt z \leq n$ such that $b_w=b_y$, $b_x=b_z$, and $b_w\neq b_x$. 362 363 **Proof**: Let's prove this with strong induction. For $n=0$, the claim is true because the empty array is orangutan-approved. Now, let's suppose that the claim is true for all $m \lt n$. 364 365 Now, let $s$ be a sorted sequence such that $x$ is in $s$ if and only if $b_x=b_1$. Suppose $s$ is length $k$. We can split the array $b$ into disjoint subarrays $c_1, c_2, \ldots, c_k$ such that $c_i$ is the subarray $b[s_i+1\ldots s_{i+1}-1]$ for all $1 \leq i \lt k$ and $c_k=b[s_k+1\ldots n]$ That is, $c_i$ is the subarray that lies between each occurrence of $b_1$ in the array $b$. 366 367 First, we note that the set of unique elements of $c_i$ and $c_j$ cannot contain any elements in common for all $i\neq j$. This is because suppose that there exists $i$ and $j$ such that $i \lt j$ and the set of unique values in $c_i$ and $c_j$ both contain $y$. Then, in the original array $b$, there must exist a subsequence $b_1, y, b_1, y$. This makes our premise false. 368 369 By our inductive claim, each of the arrays $c_1, c_2, \ldots, c_k$ must be orangutan-approved. Since there are no overlapping elements, we may delete each of the arrays $c_1, c_2, \ldots, c_k$ separately. Finally, the array $b$ is left with $k$ copies of $b_1$, and we can use one operation to delete all remaining elements in the array $b$. 370 371 Now, how do we solve for all queries? First, precompute the array $last$, which is the array containing for each $i$ the largest index $j \lt i$ such that $a[j]=a[i]$. Let's then use two pointers to compute the last element $j \lt i$ such that $a[j\ldots i]$ is orangutan-approved but $a[j-1\ldots i]$ is not, and store this in an array called $left$. Let's also keep a maximum segment tree $next$ such that $next[i]$ is the first element $j \gt i$ such that $a_j=a_i$. As we sweep from $i-1$ to $i$, we do the following: 372 373 1. Set $L=left[i-1]$ 374 2. Otherwise, while $\max(next[L...last[i]-1] \gt last[i]$ and $last[i]\neq-1$), increment $L$ by $1$. 375 3. Set $left[i]=L$ 376 377 When the $left$ array is fully calculated, we can solve each query in $O(1)$. 378 379 **Code (C++)** 380 381 ``` 382 #pragma GCC optimize("Ofast") 383 384 #include <bits/stdc++.h> 385 using namespace std; 386 #define ll long long 387 #define nline "\n" 388 #define f first 389 #define s second 390 #define sz(x) x.size() 391 #define all(x) x.begin(),x.end() 392 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 393 const ll INF_ADD=1e18; 394 const ll MOD=1e9+7; 395 const ll MAX=1048579; 396 class ST { 397 public: 398 vector<ll> segs; 399 ll size = 0; 400 ll ID = 0; 401 402 ST(ll sz) { 403 segs.assign(2 * sz, ID); 404 size = sz; 405 } 406 407 ll comb(ll a, ll b) { 408 return max(a, b); 409 } 410 411 void upd(ll idx, ll val) { 412 segs[idx += size] = val; 413 for(idx /= 2; idx; idx /= 2) segs[idx] = comb(segs[2 * idx], segs[2 * idx + 1]); 414 } 415 416 ll query(ll l, ll r) { 417 ll lans = ID, rans = ID; 418 for(l += size, r += size + 1; l < r; l /= 2, r /= 2) { 419 if(l & 1) lans = comb(lans, segs[l++]); 420 if(r & 1) rans = comb(segs[--r], rans); 421 } 422 return comb(lans, rans); 423 } 424 }; 425 void solve(){ 426 ll n,q,l=1; cin>>n>>q; 427 ST track(n+5); 428 vector<ll> a(n+5),last(n+5,0),lft(n+5); 429 for(ll i=1;i<=n;i++){ 430 cin>>a[i]; 431 ll till=last[a[i]]; 432 while(track.query(l,till)>=till+1){ 433 l++; 434 } 435 if(till){ 436 track.upd(till,i); 437 } 438 lft[i]=l; 439 last[a[i]]=i; 440 } 441 while(q--) { 442 ll l,r; cin>>l>>r; 443 if(lft[r]<=l){ 444 cout<<"YES\n"; 445 } 446 else{ 447 cout<<"NO\n"; 448 } 449 } 450 } 451 int main() 452 { 453 ios_base::sync_with_stdio(false); 454 cin.tie(NULL); 455 ll test_cases=1; 456 cin>>test_cases; 457 while(test_cases--){ 458 solve(); 459 } 460 } 461 ``` 462 463 #### [2030G1 - Уничтожение Вселенной (простая версия)](/contest/2030/problem/G1 "Codeforces Round 979 (Div. 2)") and [2030G2 - Уничтожение Вселенной (сложная версия)](/contest/2030/problem/G2 "Codeforces Round 979 (Div. 2)") 464 465 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [satyam343](/profile/satyam343 "Мастер satyam343") 466 Analysis: [satyam343](/profile/satyam343 "Мастер satyam343") 467 468 **Solution (Easy Version)** 469 470 To find the score of a set of intervals $([l_1, r_1], [l_2, r_2], \ldots, [l_v, r_v])$, we follow these steps: 471 472 Initially, the score is set to $0$. 473 474 We perform the following process repeatedly: 475 476 * Let $x$ be the interval with the smallest $r_i$ among all active intervals. 477 * Let $y$ be the interval with the largest $l_i$ among all active intervals. 478 * If $r_x \lt l_y$, add $l_y - r_x$ to the score, mark intervals $x$ and $y$ as inactive, and continue the process. 479 * If $r_x \geq l_y$, stop the process. 480 481 At the end of this process, all active intervals will intersect at least one common point. 482 483 Now, we need to prove that the process indeed gives us the minimum possible score. We can prove this by induction. 484 485 Let $S$ be some set of intervals, and let $x$ and $y$ be the intervals defined above. Consider the set $S' = S \setminus {x, y}$ (i.e., $S'$ is the set $S$ excluding $x$ and $y$). We claim that: 486 487 $ \text{score}(S) \geq \text{score}(S') + \text{distance}(x, y) $ 488 489 This is true because, for $x$ and $y$ to intersect, we must perform at least $\text{distance}(x, y)$ operations. Our construction achieves the lower bound of $\text{score}(S') + \text{distance}(x, y)$. Thus, 490 491 $ \text{score}(S) = \text{score}(S') + \text{distance}(x, y) $ 492 493 During the process, we pair some intervals (possibly none). Specifically, in the $k$-th step, we pair the interval with the $k$-th smallest $r_i$ with the interval having the $k$-th largest $l_j$, and add the distance between them to the score. 494 495 In the problem G1, we can compute the contribution of each pair of intervals as follows: 496 497 Suppose we consider a pair $(i, j)$. Without loss of generality, assume that $r_i \lt l_j$. 498 499 The pair $(i, j)$ will be considered in some subset $S$ if there are exactly $x$ intervals $p$ such that $r_p \lt r_i$ and exactly $x$ intervals $p$ such that $l_p \gt l_j$, for some non-negative integer $x$. 500 501 Let there be $g$ intervals $p$ such that $r_p \lt r_i$ and $h$ intervals $p$ such that $l_p \gt l_j$. 502 503 For $(i, j)$ to be paired in some subset $S$, we must choose $x$ intervals from the $g$ intervals on the left and $x$ intervals from the $h$ intervals on the right, for some non-negative integer $x$. There are no restrictions on the remaining $n - 2 - g - h$ intervals. 504 505 Therefore, the contribution of $(i, j)$ is: 506 507 $ \sum_{x = 0}^{g} (l_j - r_i) \cdot \binom{g}{x} \cdot \binom{h}{x} \cdot 2^{n - 2 - g - h} $ 508 509 We can simplify this sum using the identity: 510 511 $ \sum_{x = 0}^{g} \binom{g}{x} \cdot \binom{h}{x} = \binom{g + h}{g} $ 512 513 (This is a form of the Vandermonde Identity.) 514 515 Thus, the contribution of $(i, j)$ becomes: 516 517 $ (l_j - r_i) \cdot \binom{g + h}{g} \cdot 2^{n - 2 - g - h} $ 518 519 This can be computed in $O(1)$ time. 520 521 Note that in the explanation above, we assumed that the interval endpoints are distinct for simplicity. If they are not, we can order the intervals based on their $l_i$ values to maintain consistency. 522 523 **Solution (Hard Version)** 524 525 Let us find the contribution of $r[i]$, the right endpoint of $i$-th interval. 526 527 Let $x$ be the number of intervals $j$ such that $r[j] \lt r[i]$, and let $y$ be the number of intervals $j$ such that $l[j] \gt r[i]$. 528 529 To determine the contribution of $r[i]$ to the final answer, we consider selecting $p$ intervals from the $x$ intervals to the left and $q$ intervals from the $y$ intervals to the right, with the constraint that $p \lt q$. We require $p \lt q$ so that interval $i$ is paired with some other interval on the right (as discussed in the solution for G1). Therefore, the contribution of $r[i]$ can be expressed as: 530 531 $ \text{Contribution} = -r[i] \cdot \text{ways}(x, y) \cdot 2^{n - 1 - x - y} $ 532 533 Here, $\text{ways}(x, y)$ represents the number of valid selections where $p \lt q$. 534 535 **Calculating $\text{ways}(x, y)$** 536 537 To compute $\text{ways}(x, y)$, we can use the Vandermonde identity to simplify the expression: 538 539 $ \text{ways}(x, y) = \sum_{\substack{0 \leq p \lt q \leq y}} \binom{x}{p} \binom{y}{q} $ 540 541 This can be rewritten as: 542 543 $ \text{ways}(x, y) = \sum_{p=0}^{x} \sum_{k=1}^{y} \binom{x}{p} \binom{y}{p + k} $ 544 545 Define the function $g(k)$ as: 546 547 $ g(k) = \sum_{p=0}^{x} \binom{x}{p} \binom{y}{p + k} $ 548 549 By applying the Vandermonde identity, we get: 550 551 $ g(k) = \binom{x + y}{x + k} $ 552 553 Thus, the total number of ways is: 554 555 $ \text{ways}(x, y) = \sum_{k=1}^{y} \binom{x + y}{x + k} $ 556 557 We can simplify this summation using the property of binomial coefficients: 558 559 $ \text{ways}(x, y) = 2^{x + y} - h(x + y, x) $ 560 561 where the function $h(p, q)$ is defined as: 562 563 $ h(p, q) = \sum_{i=0}^{q} \binom{p}{i} $ 564 565 **Efficient Computation of $h(p, q)$** 566 567 Note that: 568 569 $ h(p, q) = 2 \cdot h(p - 1, q) - \binom{p - 1}{q} $ 570 571 Suppose throughout the solution, we call the function $h(p, q)$ $d$ times for pairs $(p_1, q_1), (p_2, q_2), \ldots, (p_d, q_d)$, in that order. We can observe that: 572 573 $ \sum_{i=2}^{d} |p_i - p_{i-1}| + |q_i - q_{i-1}| = O(n) $ 574 575 Since $h(p_i, q_i)$ can be computed from $h(p_{i-1}, q_{i-1})$ in $|p_i - p_{i-1}| + |q_i - q_{i-1}|$ operations, the amortized time complexity for this part is $O(n)$. 576 577 **Final Contribution** 578 579 Combining the above results, the contribution of $r[i]$ to the answer is: 580 581 $ -r[i] \cdot \left(2^{x + y} - h(x + y, x)\right) \cdot 2^{n - 1 - x - y} $ 582 583 A similar calculation can be applied to the contribution of $l[i]$. By summing these contributions across all relevant intervals, we obtain the final answer. 584 585 **G1 Code (C++)** 586 587 ``` 588 #pragma GCC optimize("Ofast") 589 590 #include <bits/stdc++.h> 591 #include <ext/pb_ds/tree_policy.hpp> 592 #include <ext/pb_ds/assoc_container.hpp> 593 using namespace __gnu_pbds; 594 using namespace std; 595 #define ll long long 596 #define ld long double 597 #define nline "\n" 598 #define f first 599 #define s second 600 #define sz(x) (ll)x.size() 601 #define vl vector<ll> 602 const ll INF_MUL=1e13; 603 const ll INF_ADD=1e18; 604 #define all(x) x.begin(),x.end() 605 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 606 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 607 //-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 608 const ll MOD=998244353; 609 const ll MAX=500500; 610 vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1); 611 ll binpow(ll a,ll b,ll MOD){ 612 ll ans=1; 613 a%=MOD; 614 while(b){ 615 if(b&1) 616 ans=(ans*a)%MOD; 617 b/=2; 618 a=(a*a)%MOD; 619 } 620 return ans; 621 } 622 ll inverse(ll a,ll MOD){ 623 return binpow(a,MOD-2,MOD); 624 } 625 void precompute(ll MOD){ 626 for(ll i=2;i<MAX;i++){ 627 fact[i]=(fact[i-1]*i)%MOD; 628 } 629 inv_fact[MAX-1]=inverse(fact[MAX-1],MOD); 630 for(ll i=MAX-2;i>=0;i--){ 631 inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD; 632 } 633 } 634 ll nCr(ll a,ll b,ll MOD){ 635 if((a<0)||(a<b)||(b<0)) 636 return 0; 637 ll denom=(inv_fact[b]*inv_fact[a-b])%MOD; 638 return (denom*fact[a])%MOD; 639 } 640 ll l[MAX],r[MAX],lft[MAX],rght[MAX],power[MAX]; 641 void solve(){ 642 ll n; cin>>n; 643 power[0]=1; 644 for(ll i=1;i<=n;i++){ 645 cin>>l[i]>>r[i]; 646 power[i]=(power[i-1]*2ll)%MOD; 647 } 648 for(ll i=1;i<=n;i++){ 649 lft[i]=rght[i]=0; 650 for(ll j=1;j<=n;j++){ 651 if(make_pair(r[i],i)>make_pair(r[j],j)){ 652 lft[i]++; 653 } 654 if(make_pair(l[i],i)<make_pair(l[j],j)){ 655 rght[i]++; 656 } 657 } 658 } 659 ll ans=0; 660 for(ll i=1;i<=n;i++){ 661 for(ll j=1;j<=n;j++){ 662 if(r[i]<l[j]){ 663 ll found=lft[i]+rght[j]; 664 ll now=nCr(found,lft[i],MOD)*(l[j]-r[i]); 665 now%=MOD; 666 ll remaining=n-found-2; 667 ans=(ans+now*power[remaining])%MOD; 668 } 669 } 670 } 671 cout<<ans<<nline; 672 return; 673 } 674 int main() 675 { 676 ios_base::sync_with_stdio(false); 677 cin.tie(NULL); 678 ll test_cases=1; 679 cin>>test_cases; 680 precompute(MOD); 681 while(test_cases--){ 682 solve(); 683 } 684 cout<<fixed<<setprecision(12); 685 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 686 } 687 ``` 688 689 **G2 Code (C++)** 690 691 ``` 692 #pragma GCC optimize("Ofast") 693 694 #include <bits/stdc++.h> 695 #include <ext/pb_ds/tree_policy.hpp> 696 #include <ext/pb_ds/assoc_container.hpp> 697 using namespace __gnu_pbds; 698 using namespace std; 699 #define ll long long 700 #define ld long double 701 #define nline "\n" 702 #define f first 703 #define s second 704 #define sz(x) (ll)x.size() 705 #define vl vector<ll> 706 const ll INF_MUL=1e13; 707 const ll INF_ADD=1e18; 708 #define all(x) x.begin(),x.end() 709 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 710 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 711 //-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 712 const ll MOD=998244353; 713 const ll MAX=5000500; 714 vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1); 715 ll binpow(ll a,ll b,ll MOD){ 716 ll ans=1; 717 a%=MOD; 718 while(b){ 719 if(b&1) 720 ans=(ans*a)%MOD; 721 b/=2; 722 a=(a*a)%MOD; 723 } 724 return ans; 725 } 726 ll inverse(ll a,ll MOD){ 727 return binpow(a,MOD-2,MOD); 728 } 729 void precompute(ll MOD){ 730 for(ll i=2;i<MAX;i++){ 731 fact[i]=(fact[i-1]*i)%MOD; 732 } 733 inv_fact[MAX-1]=inverse(fact[MAX-1],MOD); 734 for(ll i=MAX-2;i>=0;i--){ 735 inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD; 736 } 737 } 738 ll nCr(ll a,ll b,ll MOD){ 739 if((a<0)||(a<b)||(b<0)) 740 return 0; 741 ll denom=(inv_fact[b]*inv_fact[a-b])%MOD; 742 return (denom*fact[a])%MOD; 743 } 744 ll l[MAX],r[MAX],power[MAX]; 745 ll ans=0,on_left=0,on_right,len; 746 ll x=0,y=0,ways=0,inv2; 747 ll getv(){ 748 while(x>=len+1){ 749 ways=((ways+nCr(x-1,y,MOD))*inv2)%MOD; 750 x--; 751 } 752 while(x<=len-1){ 753 ways=(2ll*ways-nCr(x,y,MOD)+MOD)%MOD; 754 x++; 755 } 756 while(y<=on_left-1){ 757 ways=(ways+nCr(x,y+1,MOD))%MOD; 758 y++; 759 } 760 return ways; 761 } 762 void solve(){ 763 ll n; cin>>n; 764 power[0]=1; 765 vector<array<ll,2>> track; 766 multiset<ll> consider; 767 for(ll i=1;i<=n;i++){ 768 cin>>l[i]>>r[i]; 769 track.push_back({r[i],l[i]}); 770 consider.insert(l[i]); 771 power[i]=(power[i-1]*2ll)%MOD; 772 } 773 ans=on_left=0; 774 on_right=len=n; 775 x=y=0; ways=1; 776 sort(all(track)); 777 for(auto it:track){ 778 while(!consider.empty()){ 779 if(*consider.begin() <= it[0]){ 780 consider.erase(consider.begin()); 781 on_right--,len--; 782 } 783 else{ 784 break; 785 } 786 } 787 ll now=power[len]-getv(); 788 now=(now*power[n-1-len])%MOD; 789 now=(now*it[0])%MOD; 790 ans=(ans+MOD-now)%MOD; 791 on_left++,len++; 792 } 793 track.clear(); consider.clear(); 794 for(ll i=1;i<=n;i++){ 795 track.push_back({l[i],r[i]}); 796 consider.insert(r[i]); 797 } 798 sort(all(track)); 799 reverse(all(track)); 800 on_left=0; 801 on_right=len=n; 802 x=y=0; ways=1; 803 for(auto it:track){ 804 while(!consider.empty()){ 805 if(*(--consider.end()) >= it[0]){ 806 consider.erase(--consider.end()); 807 on_right--,len--; 808 } 809 else{ 810 break; 811 } 812 } 813 ll now=power[len]-getv(); 814 now=(now*power[n-1-len])%MOD; 815 now=(now*it[0])%MOD; 816 ans=(ans+now)%MOD; 817 on_left++,len++; 818 } 819 ans=(ans+MOD)%MOD; 820 cout<<ans<<nline; 821 return; 822 } 823 int main() 824 { 825 ios_base::sync_with_stdio(false); 826 cin.tie(NULL); 827 ll test_cases=1; 828 cin>>test_cases; 829 precompute(MOD); 830 inv2=inverse(2,MOD); 831 while(test_cases--){ 832 solve(); 833 } 834 cout<<fixed<<setprecision(12); 835 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 836 } 837 ```