1736.md (15432B)
1 Source: https://codeforces.com/blog/entry/107847 2 3 Thank you for participation! We apologize for problem D that turned out to be harder than expected. Still, we hope that you liked most of the problems. 4 5 In case you found C2 tedious to implement or found many cases to deal with, I would recommend you to have a look at the intended solution. I think it is interesting and easy to implement. 6 7 [1736A - Make A Equal to B](/contest/1736/problem/A "Codeforces Round 825 (Div. 2)") 8 9 **Solution** 10 11 It is easy to observe that the second operation needs to be performed **at most** once. Now, we just need to check $2$ cases, one in which the re-arrangement operation is used, and one in which it is not. 12 13 If the re-arrangement operation is to be used, then we just need to make the counts of $0$s and $1$s in $a$ equal to that of $b$. Without loss of generality assume $a$ contains $x$ more $0$s than $b$, then the cost in this case will just be $x + 1$ (extra one for re-arrangement cost). 14 15 If the re-arrangement operation is not to be used, then we just need to make each element of $a$ equal to the corresponding element of $b$. 16 17 Finally, our answer is the smaller cost of these $2$ cases. 18 19 Time complexity is $O(n)$. 20 21 **Code** 22 23 ``` 24 #include <bits/stdc++.h> 25 using namespace std; 26 #define ll long long 27 void solve(){ 28 ll n; cin>>n; 29 ll sum=0,ans=0; 30 vector<ll> a(n),b(n); 31 for(auto &it:a){ 32 cin>>it; 33 sum+=it; 34 } 35 for(auto &it:b){ 36 cin>>it; 37 sum-=it; 38 } 39 for(ll i=0;i<n;i++){ 40 ans+=(a[i]^b[i]); 41 } 42 ans=min(ans,1+abs(sum)); 43 cout<<ans<<"\n"; 44 } 45 int main() 46 { 47 ios_base::sync_with_stdio(false); 48 cin.tie(NULL); 49 ll t; cin>>t; 50 while(t--){ 51 solve(); 52 } 53 } 54 ``` 55 56 [1736B - Playing with GCD](/contest/1736/problem/B "Codeforces Round 825 (Div. 2)") 57 58 **Solution** 59 60 Take $a_0 = a_{n+1} = 1$. 61 62 Now take $b_i=lcm(a_{i-1},a_i)$ for $1 \leq i \leq n+1$. If $b$ gives us $a$ after performing the $\gcd$ operations, then the answer is YES, otherwise the answer is NO. (When answer is NO, we would get a case like $\gcd(b_i, b_{i + 1}) = k \cdot a_i$(where $k \gt 1$ for some $i$). 63 64 Suppose $c$ is some valid array which gives us $a$. So, $c_i$ should be divisible by $b_i$. This means $\gcd(c_i, c_{i+1}) \geq \gcd(b_i, b_{i + 1})$. 65 66 So, if $\gcd(b_i, b_{i + 1}) \gt a_i$ for any $i$, we should also have $\gcd(c_i, c_{i+1}) \gt a_i$. This implies that $c$ is not valid if $b$ is not valid. 67 68 Time complexity is $O(n \cdot \log(bmax))$. 69 70 **Code** 71 72 ``` 73 #include <bits/stdc++.h> 74 using namespace std; 75 #define ll long long 76 ll lcm(ll a,ll b){ 77 ll g=__gcd(a,b); 78 return (a*b/g); 79 } 80 void solve(){ 81 ll n; cin>>n; 82 vector<ll> a(n+2,1); 83 for(ll i=1;i<=n;i++){ 84 cin>>a[i]; 85 } 86 vector<ll> b(n+2,1); 87 for(ll i=1;i<=n+1;i++){ 88 b[i]=lcm(a[i],a[i-1]); 89 } 90 for(ll i=1;i<=n;i++){ 91 if(__gcd(b[i],b[i+1])!=a[i]){ 92 cout<<"NO\n"; 93 return; 94 } 95 } 96 cout<<"YES\n"; 97 } 98 int main() 99 { 100 ios_base::sync_with_stdio(false); 101 cin.tie(NULL); 102 ll t; cin>>t; 103 while(t--){ 104 solve(); 105 } 106 } 107 ``` 108 109 [1736C1 - Good Subarrays (Easy Version)](/contest/1736/problem/C1 "Codeforces Round 825 (Div. 2)") 110 111 **Solution** 112 113 Suppose $l[i]$ represents the leftmost point such that subarray $a[l[i],i]$ is good. 114 115 Notice that the array $l$ is non-decreasing. 116 117 So suppose $dp[i]$ denotes the length of longest good subarray which ends at index $i$. 118 119 Take $dp[0]=0$. 120 121 Now $dp[i]=min(dp[i-1]+1,a[i])$. 122 123 Suppose $a[i] \geq dp[i-1]+1$. Now we claim that $dp[i]=dp[i-1]+1$. We know $a[i-dp[i-1],i-1]$ is \t{good}. Now if we look at array $b=a[i-dp[i-1],i]$, $b_i \geq i $ for $ 1 \leq i \leq dp[i-1]$. For $b$ to be good, last element of $b$(which is $a[i]$) should be greater than or equal $dp[i-1]+1$(which is consistent with our supposition). So $b$ is good. 124 125 We can similarly cover the case when $a[i] \lt dp[i-1]+1$. 126 127 So our answer is $ \sum_{i=1}^{n} dp[i]$. Time complexity is $O(n)$. 128 129 **Code** 130 131 ``` 132 #include <bits/stdc++.h> 133 using namespace std; 134 #define ll long long 135 void solve(){ 136 ll n; cin>>n; 137 vector<ll> dp(n+5,0); 138 ll ans=0; 139 for(ll i=1;i<=n;i++){ 140 ll x; cin>>x; 141 dp[i]=min(dp[i-1]+1,x); 142 ans+=dp[i]; 143 } 144 cout<<ans<<"\n"; 145 } 146 int main() 147 { 148 ios_base::sync_with_stdio(false); 149 cin.tie(NULL); 150 ll t; cin>>t; 151 while(t--){ 152 solve(); 153 } 154 } 155 ``` 156 157 [1736C2 - Good Subarrays (Hard Version)](/contest/1736/problem/C2 "Codeforces Round 825 (Div. 2)") 158 159 **Solution** 160 161 Let us continue the idea of C1. 162 163 Suppose $track[i]$ denotes $\sum_{j=i}^{n} dp[j]$ if $dp[i]=a[i]$. 164 165 We can precalculate array $track$. 166 167 Now suppose $a_p$ is changed to $x$ and $adp[i]$ denotes the length of longest good subarray which ends at index $i$ in the updated array. 168 169 It is easy to see that $adp[i]=dp[i]$ for $ 1 \leq i \lt p$. Now let $q$ be the smallest index greater than $p$ such that $adp[q]=a[q]$(It might be the case that there does not exist any such $q$ which can be handled similarly). So we have $3$ ranges to deal with — $(1,p-1)$, $(p,q-1)$ and $(q,n)$. 170 171 Now $\sum_{i=1}^{p-1} adp[i]$ = $\sum_{i=1}^{p-1} dp[i]$(which can be stored as prefix sum). 172 173 Also $\sum_{i=q}^{n} adp[i]$ = $track[q]$. 174 175 Now we only left with range $(p,q-1)$. An interesting observation is $adp[i]=adp[i-1]+1$ for $p \lt i \lt q$. 176 177 This approach can be implemented neatly in many ways(one way is answer each query offline). 178 179 Time complexity is $O(n \cdot \log(n))$. 180 181 **Code(Offline queries)** 182 183 ``` 184 #include <bits/stdc++.h> 185 using namespace std; 186 #define ll long long 187 #define f first 188 #define s second 189 int main() 190 { 191 ios_base::sync_with_stdio(false); 192 cin.tie(NULL); 193 ll n; cin>>n; 194 vector<ll> track(n+5,0),sum(n+5,0); 195 vector<pair<ll,pair<ll,ll>>> trav; 196 vector<ll> pref(n+5,0),dp(n+5,0); 197 for(ll i=1;i<=n;i++){ 198 ll x; cin>>x; 199 sum[i]=sum[i-1]+i; trav.push_back({x-i,{i,0}}); 200 dp[i]=min(dp[i-1]+1,x); pref[i]=pref[i-1]+dp[i]; 201 } 202 ll q; cin>>q; 203 vector<ll> ans(q+5,0); 204 for(ll i=1;i<=q;i++){ 205 ll p,x; cin>>p>>x; x=min(dp[p-1]+1,x); 206 trav.push_back({x-p,{p,i}}); 207 } 208 set<ll> found; found.insert(n+1); 209 sort(trav.begin(),trav.end()); 210 for(auto it:trav){ 211 if(it.s.s){ 212 ll r=*found.upper_bound(it.s.f); 213 ans[it.s.s]=pref[it.s.f-1]+track[r]+sum[r-it.s.f]+(it.f+it.s.f-1)*(r-it.s.f); 214 } 215 else{ 216 ll r=*found.lower_bound(it.s.f); found.insert(it.s.f); 217 track[it.s.f]=track[r]+sum[r-it.s.f]+(it.f+it.s.f-1)*(r-it.s.f); 218 } 219 } 220 for(ll i=1;i<=q;i++){ 221 cout<<ans[i]<<"\n"; 222 } 223 } 224 ``` 225 226 **Code(Online queries)** 227 228 ``` 229 #include <bits/stdc++.h> 230 #include <ext/pb_ds/tree_policy.hpp> 231 #include <ext/pb_ds/assoc_container.hpp> 232 using namespace __gnu_pbds; 233 using namespace std; 234 #define ll long long 235 const ll INF_MUL=1e13; 236 const ll INF_ADD=1e18; 237 #define pb push_back 238 #define mp make_pair 239 #define nline "\n" 240 #define f first 241 #define s second 242 #define pll pair<ll,ll> 243 #define all(x) x.begin(),x.end() 244 #define vl vector<ll> 245 #define vvl vector<vector<ll>> 246 #define vvvl vector<vector<vector<ll>>> 247 #ifndef ONLINE_JUDGE 248 #define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline; 249 #else 250 #define debug(x); 251 #endif 252 const ll MOD=1e9+7; 253 const ll MAX=100010; 254 ll cal(ll n){ 255 ll now=(n*(n+1))/2; 256 return now; 257 } 258 class ST { 259 public: 260 vector<ll> segs; 261 ll size = 0; 262 ll ID = INF_ADD; 263 264 ST(ll sz) { 265 segs.assign(2 * sz, ID); 266 size = sz; 267 } 268 269 ll comb(ll a, ll b) { 270 return min(a, b); 271 } 272 273 void upd(ll idx, ll val) { 274 segs[idx += size] = val; 275 for(idx /= 2; idx; idx /= 2) segs[idx] = comb(segs[2 * idx], segs[2 * idx + 1]); 276 } 277 278 ll query(ll l, ll r) { 279 ll lans = ID, rans = ID; 280 for(l += size, r += size + 1; l < r; l /= 2, r /= 2) { 281 if(l & 1) lans = comb(lans, segs[l++]); 282 if(r & 1) rans = comb(segs[--r], rans); 283 } 284 return comb(lans, rans); 285 } 286 }; 287 void solve(){ 288 ll n; cin>>n; 289 vector<ll> a(n+5,0),use(n+5,0),pref(n+5,0); 290 for(ll i=1;i<=n;i++){ 291 cin>>a[i]; 292 use[i]=min(use[i-1]+1,a[i]); pref[i]=pref[i-1]+use[i]; 293 } 294 ST segtree(n+5); 295 auto get=[&](ll l,ll r,ll till,ll pos,ll tar){ 296 while(l<=r){ 297 ll mid=(l+r)/2; 298 if(segtree.query(pos,mid)>=tar){ 299 till=mid,l=mid+1; 300 } 301 else{ 302 r=mid-1; 303 } 304 } 305 return till; 306 }; 307 vector<ll> track(n+5,0); 308 for(ll i=n;i>=1;i--){ 309 segtree.upd(i,a[i]-i); ll till=get(i,n,i,i,a[i]-i); 310 track[i]=track[till+1]+cal(a[i]+till-i)-cal(a[i]-1); 311 } 312 ll q; cin>>q; 313 while(q--){ 314 ll p,x; cin>>p>>x; ll target=min(x,use[p-1]+1); 315 ll till=get(p+1,n,p,p+1,target-p); 316 ll ans=pref[p-1]+track[till+1]+cal(target+till-p)-cal(target-1); 317 cout<<ans<<nline; 318 } 319 return; 320 } 321 int main() 322 { 323 ios_base::sync_with_stdio(false); 324 cin.tie(NULL); 325 #ifndef ONLINE_JUDGE 326 freopen("input.txt", "r", stdin); 327 freopen("output.txt", "w", stdout); 328 freopen("error.txt", "w", stderr); 329 #endif 330 ll test_cases=1; 331 //cin>>test_cases; 332 while(test_cases--){ 333 solve(); 334 } 335 cout<<fixed<<setprecision(10); 336 cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 337 } 338 ``` 339 340 [1736D - Equal Binary Subsequences](/contest/1736/problem/D "Codeforces Round 825 (Div. 2)") 341 342 **Solution** 343 344 It is easy to see that a necessary condition for a solution to exist is that the number of $1$ in $s$ should be even. It turns out that this condition is sufficient too. 345 346 Here is one valid construction: 347 348 We make $n$ pairs of the form $(s[2i-1],s[2i])$ for $(1 \leq i \leq n)$. 349 350 Assume we have $x$ pairs in which both elements are different and $n-x$ pairs in which both elements are same. 351 352 \textbf{Claim} — $x$ should be even. 353 354 \textbf{Proof} — Assume that among the $n-x$ pairs in which both elements are same, we have $y$ pairs in which both elements are $1$. So number of $1$ in $s$ is $x+2 \cdot y$. We know that number of $1$ in $s$ is even, so for $x+2 \cdot y$ to be even, $x$ should also be even. 355 356 Now we will select $x$ indices; exactly one index from each of the $x$ pairs in which both elements are distinct. Take the index of $0$ from $i_{th}$ pair if $i$ is odd, else take the index of $1$. Thus our selected characters = ${0,1,0,1, \dots ,0,1}$ 357 358 Now on cyclically shifting the selected characters clockwise once, we can see that elements at selected indices got flipped. 359 360 Since, elements in those $x$ pairs were distinct initially, and we flipped exactly one character from each of those $x$ pairs, both elements of those $x$ pairs are same now. 361 362 Hence, in updated $s$, $s[2i-1]=s[2i]$. 363 364 So, for $s_1$, we can select characters of all odd indices. 365 366 Finally we'll have $s_1 = s_2$. Time complexity is $O(n)$. 367 368 **Code** 369 370 ``` 371 #include <bits/stdc++.h> 372 using namespace std; 373 #define ll long long 374 void solve(){ 375 ll n; cin>>n; 376 string s; cin>>s; 377 ll freq=0; 378 vector<ll> ans; 379 ll need=0; 380 for(ll i=0;i<2*n;i+=2){ 381 if(s[i]!=s[i+1]){ 382 freq++; 383 ans.push_back(i+1); 384 if(s[i]-'0'!=need){ 385 ans.back()++; 386 } 387 need^=1; 388 } 389 } 390 if(freq&1){ 391 cout<<"-1\n"; 392 return; 393 } 394 cout<<ans.size()<<" "; 395 for(auto it:ans){ 396 cout<<it<<" "; 397 } 398 cout<<"\n"; 399 for(ll i=1;i<=2*n;i+=2){ 400 cout<<i<<" \n"[i+1==2*n]; 401 } 402 } 403 int main() 404 { 405 ios_base::sync_with_stdio(false); 406 cin.tie(NULL); 407 ll t; cin>>t; 408 while(t--){ 409 solve(); 410 } 411 } 412 ``` 413 414 [1736E - Swap and Take](/contest/1736/problem/E "Codeforces Round 825 (Div. 2)") 415 416 **Solution** 417 418 As the constraints suggest, we should use dp to solve this problem. 419 420 Let's write the original indices of the array that are added during this process — $p_1, p_2, \ldots, p_n$. None of added numbers are zeroed in an optimal answer. It gives that $p_1 \le p_2 \le \ldots \le p_n$ and the answer is equal to the sum of $a[p_k]$ ($1 \leq k \leq n$). 421 422 To get the optimal answer we'll use $dp[t][last][m]$ = maximum score on $t$-th turn if $p_t = last$ and we have performed $m$ swapping moves (the first dimension can be omitted). Note that **$m \leq i$**. It can be updated by considering the next index but it will take $O(n^4)$. The most straightforward way to improve it to $O(n^3)$ is to use prefix maximums. 423 424 Here are some details. 425 426 We have only two cases: 427 428 1. $p_t=p_{t-1}$ — In this case, our transition is just $dp[t][last][m]=dp[t-1][last][m-1]+a[last]$ 429 2. $p_t \gt p_{t-1}$ — Let us make some observations. First of all, $p_t \ge t$. So number of swaps to bring $p_t$ to index $t$ is fixed. It is $p_t-t$. So $dp[t][last][m]=\max_{j=1}^{last-1} (dp[t-1][j][m-(p_t-t)])+a[last]$. Note that we can find $\max_{j=1}^{last-1} (dp[t-1][j][m-(p_t-t)])$ in $O(1)$. Hint — use prefix maximum. 430 431 Time complexity is $O(n^3)$. 432 433 **Code** 434 435 ``` 436 #include <bits/stdc++.h> 437 using namespace std; 438 const int MAX=505; 439 vector<vector<vector<int>>> dp(MAX,vector<vector<int>>(MAX,vector<int>(MAX,-(int)(1e9)))); 440 int main() 441 { 442 int n; cin>>n; 443 vector<int> a(n+5); 444 for(int i=1;i<=n;i++){ 445 cin>>a[i]; 446 } 447 vector<vector<int>> prefix(n+5,vector<int>(n+5,0)); 448 int ans=0; 449 for(int i=1;i<=n;i++){ 450 for(int j=1;j<=n;j++){ 451 for(int k=0;k<=i;k++){ 452 if(k){ 453 dp[i][j][k]=dp[i-1][j][k-1]+a[j]; 454 } 455 if(j>=i){ 456 int need=j-i; 457 if(need>k){ 458 continue; 459 } 460 dp[i][j][k]=max(dp[i][j][k],prefix[k-need][j-1]+a[j]); 461 } 462 } 463 } 464 for(int j=1;j<=n;j++){ 465 for(int k=0;k<=i;k++){ 466 prefix[k][j]=max(prefix[k][j],dp[i][j][k]); 467 } 468 } 469 for(int j=0;j<=i;j++){ 470 for(int k=1;k<=n;k++){ 471 prefix[j][k]=max(prefix[j][k],prefix[j][k-1]); 472 ans=max(ans,prefix[j][k]); 473 } 474 } 475 } 476 cout<<ans; 477 } 478 ```