codeforces-scrape

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

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")