2147.md (8565B)
1 Source: https://codeforces.com/blog/entry/146633 2 3 Thanks everybody for participating in the round! 4 5 ### [A. Shortest Increasing Path](https://codeforces.com/contest/2147/problem/A) 6 7 Author: [BernatP](/profile/BernatP "Мастер BernatP") Preparation: [BernatP](/profile/BernatP "Мастер BernatP") 8 9 **Hint1** 10 11 How big can the answer be? 12 13 **Hint2** 14 15 Which coordinates can you reach in $2$ or $3$ moves? 16 17 **Solution** 18 19 Tutorial is loading... 20 21 **Code** 22 23 ``` 24 #include <bits/stdc++.h> 25 #define endl '\n' 26 using namespace std; 27 #define int long long 28 29 signed main(){ 30 ios_base::sync_with_stdio(0); 31 cin.tie(0); 32 int t; 33 cin>>t; 34 while(t--){ 35 int x,y; 36 cin>>x>>y; 37 if(x==y || x==y+1 || y==1)cout<<-1<<endl; 38 else if(x<y)cout<<2<<endl; 39 else cout<<3<<endl; 40 } 41 } 42 ``` 43 44 ### [B. Multiple Construction](https://codeforces.com/contest/2147/problem/B) 45 46 Author: [danx](/profile/danx "Мастер danx") Preparation: [danx](/profile/danx "Мастер danx") 47 48 **Hint1** 49 50 Don't over complicate, there is a simple construction 51 52 **Hint2** 53 54 There is a construction where each number $x$ is placed at distance either $x$ or $2 \cdot x$. 55 56 **Hint3** 57 58 Here is a construction where only the number $n$ is placed at distance $n$. All other numbers are placed at distance $2 \cdot x$. 59 60 **Hint4** 61 62 There is a construction where the first element of the array is always $n$. 63 64 **Solution** 65 66 Tutorial is loading... 67 68 **Code** 69 70 ``` 71 #include <bits/stdc++.h> 72 using namespace std; 73 74 int t, n; 75 76 signed main() { 77 ios::sync_with_stdio(false); cin.tie(nullptr); 78 79 cin >> t; 80 while (t--) { 81 cin >> n; 82 for (int i = n; i >= 1; i--) { 83 cout << i << " "; 84 } 85 cout << n; 86 for (int i = 1; i < n; i++) { 87 cout << " " << i; 88 } 89 cout << "\n"; 90 } 91 } 92 ``` 93 94 ### [C. Rabbits](https://codeforces.com/contest/2147/problem/C) 95 96 Author: [misteg168](/profile/misteg168 "Мастер misteg168") Preparation: [misteg168](/profile/misteg168 "Мастер misteg168") 97 98 **Hint1** 99 100 If we have two consecutive $1$'s, the rabbits on the left and right of this block are independent. We can divide our problem into multiple subproblems. 101 102 **Hint2** 103 104 If one of these subproblems mentioned in hint $1$ contains two consecutive 0's, can we solve this subproblem? 105 106 **Hint3** 107 108 If we don't have consecutive $0$'s in these subproblems mentioned in hint $1$, the pattern looks like $10101 \dots 10101$, in which of these patterns can we place the rabbits? 109 110 **Solution** 111 112 Tutorial is loading... 113 114 **Code** 115 116 ``` 117 #include <bits/stdc++.h> 118 using namespace std; 119 120 void solve() { 121 int n; cin >> n; 122 string s; cin >> s; 123 bool ok = true; 124 bool curr = (s[0] == '1'); 125 int cnt = 0; 126 for (int i = 0; i < n; i++) { 127 if (s[i] == '0') 128 cnt++; 129 if (i == 0) 130 continue; 131 if (s[i] == s[i-1] && s[i] == '0') 132 curr = false; 133 if (s[i] == s[i-1] && s[i] == '1') { 134 if (curr && cnt % 2 == 1) 135 ok = false; 136 curr = true; 137 cnt = 0; 138 } 139 } 140 141 if (curr && cnt % 2 == 1 && s[n-1] == '1') 142 ok = false; 143 144 cout << (ok ? "YES" : "NO") << "\n"; 145 } 146 147 int main() { 148 ios::sync_with_stdio(false); 149 cin.tie(nullptr); 150 151 int T; cin >> T; 152 while (T--) 153 solve(); 154 } 155 ``` 156 157 ### [D. Game on Array](https://codeforces.com/contest/2147/problem/D) 158 159 Author: [BernatP](/profile/BernatP "Мастер BernatP") Preparation: [BernatP](/profile/BernatP "Мастер BernatP") 160 161 **Hint1** 162 163 Solve small cases. 164 165 **Hint2** 166 167 What happens when every value is even? 168 169 **Hint3** 170 171 How can we add exactly one odd number to the solution of hint 2? 172 173 **Solution** 174 175 Tutorial is loading... 176 177 **Code** 178 179 [339616059](/contest/2147/submission/339616059 "Посылка 339616059 от treebutton") 180 181 ### [E. Maximum OR Popcount](https://codeforces.com/contest/2147/problem/E) 182 183 Author: [Pablo-No](/profile/Pablo-No "Мастер Pablo-No") Preparation: [Pablo-No](/profile/Pablo-No "Мастер Pablo-No") 184 185 **Hint1** 186 187 The answer is bounded by $31$. 188 189 **Hint2** 190 191 We will precalculate the minimum operations for each answer. 192 193 **Hint3** 194 195 How will the bitwise or look like if we want to increase the popcount from the original by increasing the number of $1$'s. 196 197 **Hint4** 198 199 We can show that it is better to fill the least significant $0$'s first. 200 201 **Hint5** 202 203 What is the best way to fill a certain bit. 204 205 **Hint6** 206 207 The solution is a greedy algorithm. 208 209 **Solution** 210 211 Tutorial is loading... 212 213 **Code** 214 215 [339616091](/contest/2147/submission/339616091 "Посылка 339616091 от treebutton") 216 217 **Bonus** 218 219 Solve the problem in $\mathcal{O}(n b + t b^2 + q \log (b))$. 220 221 ### [F. Exchange Queries](https://codeforces.com/contest/2147/problem/F) 222 223 Author: [BernatP](/profile/BernatP "Мастер BernatP") Preparation: [misteg168](/profile/misteg168 "Мастер misteg168") 224 225 **Hint1** 226 227 Try to understand what are the SCCs. 228 229 **Hint2** 230 231 They are a line. Given the sizes of the SCC, find a closed formula for the answer. 232 233 **Hint3** 234 235 Think how to maintain the formula using data structures. 236 237 **Solution** 238 239 Tutorial is loading... 240 241 **Code** 242 243 [339616164](/contest/2147/submission/339616164 "Посылка 339616164 от treebutton") 244 245 ### [G. Modular Tetration](https://codeforces.com/contest/2147/problem/G) 246 247 Author: [BernatP](/profile/BernatP "Мастер BernatP") Preparation: [BernatP](/profile/BernatP "Мастер BernatP") 248 249 **About cheaters** 250 251 There was a lot of cheating on this problem, which is why there were many in-contest solves. Cheaters will be banned. We’re sorry if the high solve count during the contest misled anyone, but please understand that this isn’t something the authors, coordinators, or codeforces can control. 252 253 **Hint1** 254 255 What happens when $n$ is big? 256 257 **Hint2** 258 259 $b_n$ is $a^{a^N}$ for some big $N$. 260 261 **Hint3** 262 263 Given $a$ and $m$ find a condition for $a$ to be $m$-tetrative. 264 265 **Hint4** 266 267 The condition is $\forall p|ord_m(a), p|a$. 268 269 **Hint5** 270 271 Fix the number of values of $a$ such that $ord_m(a) = k$ and get a formula. 272 273 **Hint6** 274 275 If $m$ is an odd prime power, the number above for $k|\varphi(m)$ is $\varphi(k)$. 276 277 **Hint7** 278 279 Manipulate the formula until it only depends on the prime divisors of $\varphi(m)$ that are not in $m$. 280 281 **Hint8** 282 283 Factor it to calculate it in $O(\log m)$. 284 285 **Solution** 286 287 Tutorial is loading... 288 289 **Code** 290 291 [339616197](/contest/2147/submission/339616197 "Посылка 339616197 от treebutton") 292 293 ### [H. Maxflow GCD Coloring](https://codeforces.com/contest/2147/problem/H) 294 295 Author: [FelixMP](/profile/FelixMP "Международный мастер FelixMP") Preparation: [FelixMP](/profile/FelixMP "Международный мастер FelixMP") 296 297 **Hint1** 298 299 Think of min-cut instead of max-flow. 300 301 **Hint2** 302 303 Can you think of a sufficient condition so that all the min-cuts between any pair of vertices are divisible by the same number? 304 305 **Hint3** 306 307 In fact, the expected sufficient condition implies that all cuts of the graph (not just min-cuts) are divisible by the same number. 308 309 **Hint4** 310 311 The minimum number of colors is always $1$ or $2$. You can check if the answer is $1$ by brute force. 312 313 **Hint5** 314 315 It is possible to make all cuts even in each induced subgraph using just $2$ colors. 316 317 **Solution** 318 319 Tutorial is loading... 320 321 **Code** 322 323 [339616226](/contest/2147/submission/339616226 "Посылка 339616226 от treebutton") 324 325 ### [I1. Longest Increasing Path (Easy Version)](https://codeforces.com/contest/2147/problem/I1) 326 327 Author: [BernatP](/profile/BernatP "Мастер BernatP") Preparation: [BernatP](/profile/BernatP "Мастер BernatP") 328 329 **Hint1** 330 331 The expected is $n = mlogm - O(m)$ steps using harmonic sum. 332 333 **Hint2** 334 335 Think of a solution in 2D (not needed but good intuition). 336 337 **Hint3** 338 339 Put points as an almost regular polygon and keep doing circles around it jumping with step $1$, then $2$, then $3$... 340 341 **Hint4** 342 343 Think how to project this solution to 1D 344 345 **Solution** 346 347 Tutorial is loading... 348 349 **Code** 350 351 [339616257](/contest/2147/submission/339616257 "Посылка 339616257 от treebutton") 352 353 ### [I2. Longest Increasing Path (Hard Version)](https://codeforces.com/contest/2147/problem/I2) 354 355 Author: [BernatP](/profile/BernatP "Мастер BernatP") Preparation: [BernatP](/profile/BernatP "Мастер BernatP") 356 357 **Hint1** 358 359 There is a $n = 2m-3$ solution that will be useful: given two groups of points in arithmetic progression far enough apart you can add two pivots in the middle to keep jumping from the left to the right group: ..... .. ..... 360 361 **Hint2** 362 363 The goal is to recursively construct a solution using smaller ones. 364 365 **Solution** 366 367 Tutorial is loading... 368 369 **Code** 370 371 [339616281](/contest/2147/submission/339616281 "Посылка 339616281 от treebutton")