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