codeforces-scrape

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

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