codeforces-scrape

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

1689.md (12889B)


      1 Source: https://codeforces.com/blog/entry/103471
      2 
      3 # [1689A - Lex String](/contest/1689/problem/A "Codeforces Round 798 (Div. 2)")
      4 
      5 Author: [wxhtzdy](/profile/wxhtzdy "Grandmaster wxhtzdy")
      6 
      7 **Hint**
      8 
      9 Greedily take the smallest character in both strings. What's the exception to this?
     10 
     11 **Solution**
     12 
     13 We can't take the smallest character in both strings when we've already took $k$ elements from the string we chose. Denote $A$ as the number of characters we've took from string $a$ in the last few consecutive moves and denote $B$ the same for $b$. If $A=k$, then we have to take the smallest character in string $b$ instead of possibly $a$. If $B=k$, then we have to take the smallest character in string $a$ instead of possibly $b$.
     14 
     15 Remember to reset $A$ to $0$ when you take a character from $b$. Similarly, reset $B$ to $0$ when you take a character from $a$.
     16 
     17 **C++ Code**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21  
     22 using namespace std;
     23  
     24 int main()
     25 {
     26     ios_base::sync_with_stdio(false);
     27     cin.tie(0),cout.tie(0);
     28  
     29     int t; cin>>t;
     30     while (t--)
     31     {
     32         int n,m,k; cin>>n>>m>>k;
     33         string a,b,c; cin>>a>>b;
     34         sort(a.begin(),a.end(),greater<char>());
     35         sort(b.begin(),b.end(),greater<char>());
     36  
     37         int ak=0,bk=0;
     38         while (!a.empty() && !b.empty())
     39         {
     40             bool gde=b.back()<a.back();
     41             if (gde && bk==k) gde=0;
     42             if (!gde && ak==k) gde=1;
     43  
     44             if (gde) c.push_back(b.back()),bk++,ak=0,b.pop_back();
     45             else c.push_back(a.back()),ak++,bk=0,a.pop_back();
     46         }
     47  
     48         cout<<c<<"\n";
     49     }
     50 }
     51 ```
     52 
     53 # [1689B - Mystic Permutation](/contest/1689/problem/B "Codeforces Round 798 (Div. 2)")
     54 
     55 Author: [n0sk1ll](/profile/n0sk1ll "Candidate Master n0sk1ll")
     56 
     57 **Hint 1**
     58 
     59 When is it impossible to find such permutation?
     60 
     61 **Hint 2**
     62 
     63 It is impossible only for $n=1$. In every other case, iterate over each position in order from $1$ to $n$ and take the smallest available number. What's the exception to this?
     64 
     65 **Solution**
     66 
     67 The exception is the last two elements. We can always take the smallest available number for each $q_i$ satisfying $i \lt n-1$. To do this we maintain an array of bools of already taken numbers, and then iterate over it to find the smallest available number satisfying $p_i\neq q_i$ which is also not checked in the array, and then check it (we took it).
     68 
     69 Now consider $(p_{n-1},p_{n})$ and we want $(q_{n-1},q_{n})$ to be lexicographically minimal while satisfying $p_{n-1}\neq q_{n-1}$ and $p_{n}\neq q_{n}$. Let $a$ and $b$ be the last two unused numbers in the array of bools with $a \lt b$. We try to take $(q_{n-1},q_{n}) = (a,b)$. If $a=p_{n-1}$ or $b=p_{n}$, then we take $(q_{n-1},q_{n}) = (b,a)$. If $(a,b)$ isn't valid, then $(b,a)$ is. The proof is left as an exercise to the reader.
     70 
     71 This solution runs in $O(n^2)$ and can be optimized to $O(n \ log \ n)$.
     72 
     73 **C++ Code (Main solution)**
     74 
     75 ```
     76 #include <bits/stdc++.h>
     77  
     78 using namespace std;
     79  
     80 bool took[1005];
     81 int p[1005];
     82  
     83 int main()
     84 {
     85     ios_base::sync_with_stdio(false);
     86     cin.tie(0),cout.tie(0);
     87  
     88     int t; cin>>t;
     89     while (t--)
     90     {
     91         int n; cin>>n;
     92         for (int i=1;i<=n;i++) cin>>p[i];
     93         for (int i=1;i<=n;i++) took[i]=0;
     94         
     95         if (n==1)
     96         {
     97             cout<<"-1\n";
     98             continue;
     99         }
    100  
    101         for (int i=1;i<=n-2;i++)
    102         {
    103             int k=1;
    104             while (took[k] || k==p[i]) ++k;
    105             cout<<k<<" "; took[k]=1;
    106         }
    107  
    108         int a=-1,b=-1;
    109         for (int i=1;i<=n;i++) if (!took[i])
    110         {
    111             if (a==-1) a=i;
    112             else b=i;
    113         }
    114  
    115         if (a!=p[n-1] && b!=p[n]) cout<<a<<" "<<b<<"\n";
    116         else cout<<b<<" "<<a<<"\n";
    117     }
    118 }
    119 ```
    120 
    121 **C++ Code (O(n) solution)**
    122 
    123 ```
    124 #include <bits/stdc++.h>
    125 
    126 using namespace std;
    127 
    128 int t,n,A[1010],B[1010];
    129 
    130 int main()
    131 {
    132     scanf("%d",&t);
    133     while(t--)
    134     {
    135         scanf("%d",&n);
    136         for(int i=1; i<=n; i++)
    137         {
    138             scanf("%d",&A[i]);
    139             B[i] = i;
    140         }
    141         if(n==1)
    142         {
    143             printf("-1\n");
    144             continue;
    145         }
    146         for(int i=1; i<n; i++)
    147         {
    148             if(A[i]==B[i]) swap(B[i],B[i+1]);
    149         }
    150         if(A[n]==B[n]) swap(B[n-1],B[n]);
    151         for(int i=1; i<=n; i++) printf("%d ",B[i]);
    152         printf("\n");
    153     }
    154     return 0;
    155 }
    156 ```
    157 
    158 [Riblji_Keksic](/profile/Riblji_Keksic "Master Riblji_Keksic") found the O(n) solution.
    159 
    160 # [1689C - Infected Tree](/contest/1689/problem/C "Codeforces Round 798 (Div. 2)")
    161 
    162 Author: [n0sk1ll](/profile/n0sk1ll "Candidate Master n0sk1ll")
    163 
    164 **Hint 1**
    165 
    166 We always delete a vertex directly connected to an infected one.
    167 
    168 **Hint 2**
    169 
    170 Use dp.
    171 
    172 **Solution**
    173 
    174 Let $u_1,u_2,...,u_k$ be the sequence of removed vertices such that the infection cannot spread anymore. If vertex $u_i$ was never directly connected to an infected vertex, then we could have deleted its parent instead of $u_i$ and we would have got a better solution. Hence, we may assume we always delete a vertex directly connected to an infected one.
    175 
    176 Now, we may use some dynamic programming ideas. Let $dp_i$ be the maximum number of vertices we can save in the subtree of vertex $i$ if that vertex is infected and we use operations only in the subtree. We can assume the second as the tree is binary and we have two choices — save the subtree of one child by deleting it and infect the other, or the other way around. In each case, the infection will be "active" in at most one subtree of some vertex.
    177 
    178 If $c_1$ and $c_2$ are the children of vertex $i$, the transition is
    179 
    180 $dp_i = max(dp_{c_1}+s_2-1,dp_{c_2}+s_1-1)$
    181 
    182 where $s_i$ denotes the number of vertices in the subtree of $i$.
    183 
    184 The answer to the problem is $dp_1$. Complexity is $O(n)$.
    185 
    186 **C++ Code**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190  
    191 using namespace std;
    192  
    193 vector<vector<int>> g(300005);
    194 int ch[300005],dp[300005];
    195  
    196 void dfs(int p, int q)
    197 {
    198     ch[p]=1,dp[p]=0; int s=0;
    199     for (auto it : g[p]) if (it!=q)
    200     {
    201         dfs(it,p); s+=dp[it];
    202         ch[p]+=ch[it];
    203     }
    204     for (auto it : g[p]) if (it!=q)
    205     {
    206         dp[p]=max(dp[p],s-dp[it]+ch[it]-1);
    207     }
    208 }
    209  
    210 int main()
    211 {
    212     ios_base::sync_with_stdio(false);
    213     cin.tie(0),cout.tie(0);
    214  
    215     int t; cin>>t;
    216     while (t--)
    217     {
    218         int n; cin>>n;
    219         for (int i=1;i<=n;i++) g[i].clear();
    220         for (int i=1;i<n;i++)
    221         {
    222             int u,v; cin>>u>>v;
    223             g[u].push_back(v);
    224             g[v].push_back(u);
    225         }
    226  
    227         dfs(1,0);
    228         cout<<dp[1]<<"\n";
    229     }
    230 }
    231 ```
    232 
    233 # [1689D - Lena and Matrix](/contest/1689/problem/D "Codeforces Round 798 (Div. 2)")
    234 
    235 Author: [n0sk1ll](/profile/n0sk1ll "Candidate Master n0sk1ll")
    236 
    237 **Hint**
    238 
    239 There are not a lot of useful black squares.
    240 
    241 **Solution**
    242 
    243 Consider this algorithm: iterate over all squares in the matrix and find the most distant black square.
    244 
    245 Let's find out how to do that efficiently. In fact, only 4 (not necessarily distinct) black squares will be useful: one square which minimizes $i-j$, one square which maximizes $i-j$, one square which minimizes $i+j$ and one square which maximizes $i+j$, where $(i,j)$ denotes the black cell's coordinates. In other words, we would like to find the most distant "border".
    246 
    247 ![ ](/predownloaded/44/ac/44acf171e3d144a3277e2238a3fdebb537dc9aa9.png)
    248 
    249 Let's look at the example above. The cell we choose to recolour to yellow creates four regions (the top-left rectangle, the top-right rectangle, the bottom-left rectangle and the bottom-right rectangle, which are created by two lines parallel with coordinate axes passing through our yellow point). The most distant border will be fully contained inside one region, hence we should find the distance from our yellow cell to any cell on that border, and that is the maximum possible distance.
    250 
    251 The complexity is $O(n\cdot m)$.
    252 
    253 **C++ Code**
    254 
    255 ```
    256 #include <bits/stdc++.h>
    257  
    258 using namespace std;
    259  
    260 char tab[1003][1003];
    261 pair<int,int> a={-1,-1},b={-1,-1},c={-1,-1},d={-1,-1};
    262  
    263 int main()
    264 {
    265     ios_base::sync_with_stdio(false);
    266     cin.tie(0),cout.tie(0);
    267  
    268     int t; cin>>t;
    269     while (t--)
    270     {
    271         a={-1,-1},b={-1,-1},c={-1,-1},d={-1,-1};
    272         
    273         int n,m; cin>>n>>m;
    274         for (int i=0;i<n;i++) cin>>tab[i];
    275  
    276         vector<pair<int,int>> interesting;
    277  
    278         for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (tab[i][j]=='B')
    279         {
    280             if (a.first==-1 || i+j>a.first+a.second) a={i,j};
    281             if (b.first==-1 || i+j<b.first+b.second) b={i,j};
    282             if (c.first==-1 || i-j>c.first-c.second) c={i,j};
    283             if (d.first==-1 || i-j<d.first-d.second) d={i,j};
    284         }
    285  
    286         interesting.push_back(a);
    287         interesting.push_back(b);
    288         interesting.push_back(c);
    289         interesting.push_back(d);
    290  
    291         int ans=1e9; pair<int,int> opt;
    292         for (int i=0;i<n;i++) for (int j=0;j<m;j++)
    293         {
    294             int dist=0;
    295             for (auto it : interesting) dist=max(dist,abs(i-it.first)+abs(j-it.second));
    296             if (dist<ans) ans=dist,opt={i,j};
    297         }
    298  
    299         cout<<opt.first+1<<" "<<opt.second+1<<"\n";
    300     }
    301 }
    302 ```
    303 
    304 # [1689E - ANDfinity](/contest/1689/problem/E "Codeforces Round 798 (Div. 2)")
    305 
    306 Author: [wxhtzdy](/profile/wxhtzdy "Grandmaster wxhtzdy")
    307 
    308 **Stupid Hint**
    309 
    310 Increase every $0$ by $1$ initially.
    311 
    312 **Hint 1**
    313 
    314 Check if the answer is $0$: check whether the graph is already connected.
    315 
    316 **Hint 2**
    317 
    318 Check if the answer is $1$.
    319 
    320 **Hint 3**
    321 
    322 If the answer is not $0$ or $1$, then it is $2$.
    323 
    324 **Solution**
    325 
    326 Firslty, let's understand how to check whether the graph induced by some array $b$ is connected in $O(n \ log \ max \ b_i)$. We create a graph over bits. Let's take all elements $b_i$ and add an edge between their adjacent bits (all bits of a single $b_i$ will be connected). To quickly access the lowest bit we will use $b_i \ \& \ -b_i$ in code. Now we just check whether the graph over bits is connected.
    327 
    328 We check whether the graph for initial array $a$ is connected. If it is, the answer is 0.
    329 
    330 Then, we wonder if the answer is $1$. Check if at least one of the graphs for arrays $a_1,...,a_{i-1},a_i-1,a_{i+1},...,a_n$ for every $1\leq i \leq n$ is connected. Do the same for arrays $a_1,...,a_{i-1},a_i+1,a_{i+1},...,a_n$. If none of the graphs is connected, the answer is $2$ and otherwise $1$.
    331 
    332 Now let's see how the answer will be at most $2$. Let $i_1,i_2,...,i_k$ be the sequence of indices denoting that $a_{i_j}$ has the highest lowest bit (the highest value of $a_i \ \& \ -a_i$). if $k=1$ then we can just decrease $a_{i_1}$ by $1$ and connect everything. If $k\geq 2$ and we do the same we might disconnect that number from other numbers having the highest lowest bit, thus an additional operation of adding $1$ to $a_{i_2}$ is needed to keep everything connected. The answer is $2$ in this case.
    333 
    334 Complexity of this solution is $O(n^2 \ log \ max \ a_i)$.
    335 
    336 **C++ Code**
    337 
    338 ```
    339 #include <bits/stdc++.h>
    340  
    341 using namespace std;
    342  
    343 int a[2005];
    344  
    345 vector<vector<int>> g(32);
    346 bool vis[32];
    347  
    348 void dfs(int p)
    349 {
    350     if (vis[p]) return; vis[p]=1;
    351     for (auto it : g[p]) dfs(it);
    352 }
    353  
    354 bool connected(int n)
    355 {
    356     int m=0;
    357     for (int i=0;i<n;i++) if (a[i]==0) return false;
    358     for (int i=0;i<n;i++) m|=a[i];
    359     for (int i=0;i<31;i++) g[i].clear();
    360     for (int i=0;i<n;i++)
    361     {
    362         int last=-1;
    363         for (int j=0;j<31;j++)
    364             if (a[i]&(1<<j)){
    365                 if (last!=-1) g[last].push_back(j),g[j].push_back(last);
    366                 last=j;
    367             }
    368     }
    369  
    370     for (int j=0;j<31;j++) vis[j]=0;
    371     for (int j=0;j<31;j++) if ((1<<j)&m)
    372     {
    373         dfs(j); break;
    374     }
    375     for (int j=0;j<31;j++) if (((1<<j)&m) && !vis[j]) return false;
    376     return true;
    377 }
    378  
    379 int main()
    380 {
    381     ios_base::sync_with_stdio(false);
    382     cin.tie(0),cout.tie(0);
    383  
    384     int t; cin>>t;
    385     while (t--){
    386  
    387  
    388     int n; cin>>n;
    389     for (int i=0;i<n;i++) cin>>a[i];
    390  
    391     int ans=0;
    392     for (int i=0;i<n;i++) if (a[i]==0) ans++,a[i]++;
    393  
    394     int m=0;
    395     for (int i=0;i<n;i++) m=max(m,(a[i]&(-a[i])));
    396  
    397     if (connected(n))
    398     {
    399         cout<<ans<<"\n";
    400         for (int i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
    401         goto kraj;
    402     }
    403  
    404     for (int i=0;i<n;i++)
    405     {
    406         a[i]--;
    407         if (connected(n))
    408         {
    409             cout<<ans+1<<"\n";
    410             for (int i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
    411             goto kraj;
    412         }
    413         a[i]++;
    414     }
    415     
    416     for (int i=0;i<n;i++)
    417     {
    418         a[i]++;
    419         if (connected(n))
    420         {
    421             cout<<ans+1<<"\n";
    422             for (int i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
    423             goto kraj;
    424         }
    425         a[i]--;
    426     }
    427  
    428     for (int i=0;i<n;i++) if ((a[i]&-a[i])==m)
    429     {
    430         a[i]--;
    431         break;
    432     }
    433     for (int i=0;i<n;i++) if ((a[i]&-a[i])==m)
    434     {
    435         a[i]++;
    436         break;
    437     }
    438  
    439     cout<<ans+2<<"\n";
    440     for (int i=0;i<n;i++) cout<<a[i]<<" ";
    441     cout<<"\n";
    442     
    443     kraj:;
    444     }
    445 }
    446 ```