1513.md (10118B)
1 Source: https://codeforces.com/blog/entry/89550 2 3 We hope that you have enjoyed this round! Here is the sketch of solutions for the problems. 4 5 ### [A. Array and Peaks](https://codeforces.com/contest/1513/problem/A) 6 7 * Problem Setter: [ajit](/profile/ajit "Master ajit") 8 * Editorialist: [ajit](/profile/ajit "Master ajit") 9 10 **Tutorial** 11 12 Tutorial is loading... 13 14 **Implementation in C++** 15 16 ``` 17 #include<bits/stdc++.h> 18 using namespace std; 19 int main() 20 { 21 int tests; 22 cin>>tests; 23 while(tests--) 24 { 25 int n,k; 26 cin>>n>>k; 27 vector<int> ans(n+1); 28 int num=n; 29 for(int i=2;i<n;i+=2) 30 { 31 if(k==0)break; 32 ans[i]=num--; 33 k--; 34 } 35 if(k) 36 { 37 cout<<-1<<endl; 38 continue; 39 } 40 int cur=1; 41 for(int i=1;i<=n;i++) 42 { 43 if(!ans[i]) 44 ans[i]=cur++; 45 } 46 47 for(int i=1;i<=n;i++) 48 cout<<ans[i]<<" "; 49 cout<<endl; 50 } 51 } 52 ``` 53 54 ### [B. AND Sequences](https://codeforces.com/contest/1513/problem/B) 55 56 * Problem Setter: [ajit](/profile/ajit "Master ajit") 57 * Editorialist: [ajit](/profile/ajit "Master ajit") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Implementation in C++** 64 65 ``` 66 #include<bits/stdc++.h> 67 using namespace std; 68 69 void solveTestCase() 70 { 71 int MOD=1e9+7; 72 int n; 73 cin>>n; 74 vector<int> a(n); 75 for(int i=0;i<n;i++)cin>>a[i]; 76 77 int min1=*min_element(a.begin(),a.end()); 78 int cnt=0; 79 80 for(int x:a) 81 { 82 if(min1==x)cnt++; 83 if((min1&x)!=min1) 84 { 85 printf("0\n"); 86 return; 87 } 88 } 89 90 int fact=1; 91 for(int i=1;i<=n-2;i++)fact=(1LL*fact*i)%MOD; 92 int ans=(1LL * cnt * (cnt-1))%MOD; 93 ans = (1LL * ans * fact) % MOD; 94 printf("%d\n",ans); 95 } 96 97 int main() 98 { 99 int tests; 100 cin>>tests; 101 while(tests--) 102 solveTestCase(); 103 return 0; 104 } 105 ``` 106 107 ### [C. Add One](https://codeforces.com/contest/1513/problem/C) 108 109 * Problem Setter: [kalpitk](/profile/kalpitk "Master kalpitk") 110 * Editorialist: [dvshah](/profile/dvshah "Master dvshah") 111 112 **Tutorial** 113 114 Tutorial is loading... 115 116 **Implementation in C++** 117 118 ``` 119 #include <bits/stdc++.h> 120 using namespace std; 121 122 #define int long long 123 124 const int max_n = 200005, mod = 1000000007; 125 int dp[max_n]; 126 127 signed main(){ 128 129 for(int i=0; i<9; i++)dp[i] = 2; 130 dp[9] = 3; 131 for(int i=10; i<max_n; i++){ 132 dp[i] = (dp[i-9] + dp[i-10])%mod; 133 } 134 135 ios_base::sync_with_stdio(false); 136 cin.tie(NULL); 137 138 int t; 139 cin>>t; 140 while(t--){ 141 int n, m; 142 cin>>n>>m; 143 int ans = 0; 144 while(n > 0){ 145 int x = n%10; 146 ans += ((m + x < 10) ? 1 : dp[m + x - 10]); 147 ans %= mod; 148 n/=10; 149 } 150 cout<<ans<<"\n"; 151 } 152 return 0; 153 } 154 ``` 155 156 ### [D. GCD and MST](https://codeforces.com/contest/1513/problem/D) 157 158 * Problem Setter: [ajit](/profile/ajit "Master ajit") 159 * Editorialist: [ajit](/profile/ajit "Master ajit") 160 161 **Tutorial** 162 163 Tutorial is loading... 164 165 **Implementation in C++** 166 167 ``` 168 #include<bits/stdc++.h> 169 using namespace std; 170 171 void solveTestCase() 172 { 173 int n,x; 174 cin>>n>>x; 175 vector<int> a(n); 176 for(int i=0;i<n;i++)cin>>a[i]; 177 178 //tells whether vertices i and i+1 are connected for 0<=i<n-1 179 vector<bool> isConnected(n); 180 vector<pair<int,int>> vals; 181 182 for(int i=0;i<n;i++) 183 vals.push_back(make_pair(a[i],i)); 184 185 sort(vals.begin(),vals.end()); 186 long long int ans=0; 187 for(auto p:vals) 188 { 189 int cur_val=p.first; 190 int i=p.second; 191 192 if(cur_val>=x)break; 193 194 while(i>0) 195 { 196 if(isConnected[i-1])break; 197 if(a[i-1]%cur_val==0) 198 { 199 isConnected[i-1]=true; 200 ans+=cur_val; 201 i--; 202 } 203 else 204 break; 205 } 206 207 i=p.second; 208 while(i<n-1) 209 { 210 if(isConnected[i])break; 211 if(a[i+1]%cur_val==0) 212 { 213 isConnected[i]=true; 214 ans+=cur_val; 215 i++; 216 } 217 else 218 break; 219 } 220 221 } 222 223 for(int i=0;i<n-1;i++) 224 { 225 if(!isConnected[i]) 226 ans+=x; 227 } 228 229 cout<<ans<<endl; 230 } 231 232 int main() 233 { 234 int T; 235 cin>>T; 236 while(T--) 237 { 238 solveTestCase(); 239 } 240 return 0; 241 } 242 ``` 243 244 ### [E. Cost Equilibrium](https://codeforces.com/contest/1513/problem/E) 245 246 * Problem Setter: [7dan](/profile/7dan "Expert 7dan") 247 * Editorialist: [kalpitk](/profile/kalpitk "Master kalpitk") 248 249 **Tutorial** 250 251 Tutorial is loading... 252 253 **Implementation in C++** 254 255 ``` 256 #include "bits/stdc++.h" 257 #define ll long long 258 #define MOD 1000000007 259 ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;} 260 261 using namespace std; 262 263 #define int long long 264 265 #define MAX 100005 266 267 vector<int> f(MAX); 268 vector<int> inv(MAX); 269 270 void init() { 271 f[0] = 1; 272 for(int i=1;i<MAX;i++) f[i] = (f[i-1]*i)%MOD; 273 inv[MAX-1] = power(f[MAX-1], MOD-2, MOD); 274 for(int i=MAX-2;i>=0;i--) inv[i] = (inv[i+1]*(i+1)) % MOD; 275 276 for(int i=0;i<MAX;i++) assert(inv[i]==power(f[i],MOD-2,MOD)); 277 } 278 279 int ncr(int n, int r) { 280 if(r > n || r < 0) return 0; 281 282 int ans = f[n]; 283 ans *= (inv[r] * inv[n - r]) % MOD; 284 ans %= MOD; 285 286 return ans; 287 } 288 289 int solve(const vector<int> &v) { 290 291 int n = v.size(); 292 int s = 0; 293 for(auto x: v) s += x; 294 295 if(!(s % n == 0)) return 0; 296 297 int src = 0; 298 int snk = 0; 299 300 map<int,int> freqSrc, freqSnk; 301 for(auto x: v) { 302 if(s / n < x) { 303 freqSrc[x]++; 304 src ++; 305 } 306 if(s / n > x) { 307 freqSnk[x]++; 308 snk ++; 309 } 310 } 311 312 if(src == 0 && snk == 0) return 1; 313 314 if(src == 1 || snk == 1) { 315 int ans = f[n]; 316 for(auto x: freqSnk) { 317 ans = (ans * inv[x.second]) % MOD; 318 } 319 for(auto x: freqSrc) { 320 ans = (ans * inv[x.second]) % MOD; 321 } 322 ans *= inv[n - src - snk]; 323 ans %= MOD; 324 return ans; 325 } 326 327 int ans = (2 * f[src] * f[snk]) % MOD; 328 329 // Divide by freq of repeating elements 330 for(auto x: freqSnk) { 331 ans = (ans * inv[x.second]) % MOD; 332 } 333 for(auto x: freqSrc) { 334 ans = (ans * inv[x.second]) % MOD; 335 } 336 337 int tot = src + snk; 338 int left = n - tot; 339 340 // Number of Solution: x_0 + x_1 + x_2 + ... + x_tot = left 341 ans = (ans * ncr(left + tot, tot)) % MOD; 342 return ans; 343 } 344 345 signed main() { 346 347 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 348 349 init(); 350 351 int n; 352 cin>>n; 353 354 vector<int> v(n); 355 for(auto &x: v) cin>>x; 356 357 cout<<solve(v); 358 359 } 360 ``` 361 362 ### [F. Swapping Problem](https://codeforces.com/contest/1513/problem/F) 363 364 * Problem Setter: [7dan](/profile/7dan "Expert 7dan") 365 * Editorialist: [mtnshh](/profile/mtnshh "Master mtnshh") 366 367 **Tutorial** 368 369 Tutorial is loading... 370 371 **Implementation1 in C++** 372 373 ``` 374 #include "bits/stdc++.h" 375 #define ll long long 376 #define MOD 1000000007 377 #define inf 1000000000000000000LL 378 379 using namespace std; 380 381 #define int long long 382 383 signed main() { 384 385 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 386 387 int n; 388 cin>>n; 389 390 vector<int> a(n), b(n); 391 for(auto &x: a) cin>>x; 392 for(auto &x: b) cin>>x; 393 394 map<int,int> segX, segY; 395 396 for(int i=0;i<n;i++) { 397 if(a[i]<=b[i]) { 398 if(!segX.count(a[i])) segX[a[i]] = b[i]; 399 else segX[a[i]] = max(segX[a[i]], b[i]); 400 } 401 else { 402 if(!segY.count(b[i])) segY[b[i]] = a[i]; 403 else segY[b[i]] = max(segY[b[i]], a[i]); 404 } 405 } 406 407 // Construct prefix maxima 408 int mx = -inf; 409 for(auto &x: segX) { 410 mx = max(mx, x.second); 411 x.second = mx; 412 } 413 414 mx = -inf; 415 for(auto &x: segY) { 416 mx = max(mx, x.second); 417 x.second = mx; 418 } 419 420 // Find best swap 421 int mxGain = 0; 422 for(int i=0;i<n;i++) { 423 if(a[i]<=b[i]) { 424 auto it = segY.upper_bound(a[i]); 425 if(it==segY.begin()) continue; 426 427 it--; 428 int overlap = min(it->second, b[i]) - a[i]; 429 mxGain = max(mxGain, 2*overlap); 430 } 431 else { 432 auto it = segX.upper_bound(b[i]); 433 if(it==segX.begin()) continue; 434 435 it--; 436 int overlap = min(it->second, a[i]) - b[i]; 437 mxGain = max(mxGain, 2*overlap); 438 } 439 } 440 441 // Find ans = initial val - mxGain 442 int ans = 0; 443 for(int i=0;i<n;i++) { 444 ans += abs(a[i]-b[i]); 445 } 446 447 ans -= mxGain; 448 cout<<ans; 449 450 } 451 ``` 452 453 **Implementation2 in C++** 454 455 ``` 456 // created by mtnshh 457 458 #include<bits/stdc++.h> 459 #include<algorithm> 460 using namespace std; 461 462 #define ll long long 463 #define ld long double 464 465 #define rep(i,a,b) for(ll i=a;i<b;i++) 466 #define repb(i,a,b) for(ll i=a;i>=b;i--) 467 468 #define pb push_back 469 #define all(A) A.begin(),A.end() 470 #define allr(A) A.rbegin(),A.rend() 471 #define ft first 472 #define sd second 473 474 #define pll pair<ll,ll> 475 #define V vector<ll> 476 #define S set<ll> 477 #define VV vector<V> 478 #define Vpll vector<pll> 479 480 #define endl "\n" 481 482 const ll logN = 20; 483 const ll M = 1000000007; 484 const ll INF = 1e18; 485 #define PI 3.14159265 486 487 const ll N = 100005; 488 489 int main(){ 490 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 491 ll n; 492 cin >> n; 493 494 ll A[n], B[n]; 495 496 rep(i,0,n) cin >> A[i]; 497 rep(i,0,n) cin >> B[i]; 498 499 Vpll x1, x2, y1, y2; 500 501 ll ans = 0; 502 503 rep(i,0,n){ 504 505 ans += abs(A[i]-B[i]); 506 507 if(A[i]<B[i]){ 508 x1.pb({A[i], B[i]}); 509 x2.pb({B[i], A[i]}); 510 } 511 else{ 512 y1.pb({A[i], B[i]}); 513 y2.pb({B[i], A[i]}); 514 } 515 } 516 517 ll fin = ans; 518 519 // 520 521 set<ll> s1; 522 523 sort(all(x1)); 524 sort(all(y2)); 525 526 ll cur1 = 0; 527 528 for(auto i: x1){ 529 530 while(cur1 < y2.size() and y2[cur1].ft <= i.ft){ 531 s1.insert(y2[cur1].sd); 532 cur1++; 533 } 534 535 if(s1.size() > 0){ 536 ll last = *s1.rbegin(); 537 fin = min(fin, ans - 2 * (min(i.sd, last) - i.ft)); 538 } 539 540 } 541 542 set<ll> s2; 543 544 sort(all(x1)); 545 sort(all(y2)); 546 547 ll cur2 = 0; 548 549 for(auto i: y2){ 550 551 while(cur2 < x1.size() and x1[cur2].ft <= i.ft){ 552 s2.insert(x1[cur2].sd); 553 cur2++; 554 } 555 556 if(s2.size() > 0){ 557 ll last = *s2.rbegin(); 558 fin = min(fin, ans - 2 * (min(last, i.sd) - i.ft)); 559 } 560 561 } 562 563 cout << fin << endl; 564 565 return 0; 566 } 567 ```