codeforces-scrape

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

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 ```