2020.md (16568B)
1 Source: https://codeforces.com/blog/entry/134516 2 3 # [A. Find Min Operations](https://codeforces.com/contest/2020/problem/A) 4 5 By [nishkarsh](/profile/nishkarsh "Grandmaster nishkarsh") 6 7 **Hint 1** 8 9 How many operations will have $x = 0$. 10 11 **Hint 2** 12 13 Try $k = 2$. 14 15 **Solution for k = 2** 16 17 Answer will be the number of ones in binary representation of $n$. 18 19 **Solution** 20 21 If $k$ is 1, we can only subtract 1 in each operation, and our answer will be $n$. 22 23 Now, first, it can be seen that we have to apply at least $n$ mod $k$ operations of subtracting $k^0$ (as all the other operations will not change the value of $n$ mod $k$). Now, once $n$ is divisible by $k$, solving the problem for $n$ is equivalent to solving the problem for $\frac{n}{k}$ as subtracting $k^0$ will be useless because if we apply the $k^0$ subtraction operation, then $n$ mod $k$ becomes $k-1$, and we have to apply $k-1$ more operations to make $n$ divisible by $k$ (as the final result, i.e., 0 is divisible by $k$). Instead of doing these $k$ operations of subtracting $k^0$, a single operation subtracting $k^1$ will do the job. 24 25 So, our final answer becomes the sum of the digits of $n$ in base $k$. 26 27 The complexity of the solution is $O(\log_{k}{n})$ per testcase. 28 29 **Code** 30 31 ``` 32 #include <bits/stdc++.h> 33 using namespace std; 34 35 int find_min_oper(int n, int k){ 36 if(k == 1) return n; 37 int ans = 0; 38 while(n){ 39 ans += n%k; 40 n /= k; 41 } 42 return ans; 43 } 44 45 int main() 46 { 47 int t; 48 cin >> t; 49 while(t--){ 50 int n,k; 51 cin >> n >> k; 52 cout << find_min_oper(n,k) << "\n"; 53 } 54 return 0; 55 } 56 ``` 57 58 # [B. Brightness Begins](https://codeforces.com/contest/2020/problem/B) 59 60 By [nishkarsh](/profile/nishkarsh "Grandmaster nishkarsh") 61 62 **Hint 1** 63 64 The final state of $i$th bulb (on or off) is independent of $n$. 65 66 **Hint 2** 67 68 The final state of the $i$th bulb tells us about the parity of number of divisors of $i$. 69 70 **Solution** 71 72 For any bulb $i$, its final state depends on the parity of the number of divisors of $i$. If $i$ has an even number of divisors, then bulb $i$ will be on; else it will be off. This translates to, if $i$ is not a perfect square, bulb $i$ will be on; else it will be off. So now the problem is to find the $k$th number which is not a perfect square. This can be done by binary searching the value of $n$ such that $n- \lfloor \sqrt{n} \rfloor = k$ or the direct formula $n$ = $\lfloor k + \sqrt{k} + 0.5 \rfloor$. 73 74 For the proof of the second formula you can refer [this book](http://gimnazija-izdijankoveckoga-kc.skole.hr/upload/gimnazija-izdijankoveckoga-%20kc/multistatic/748/Problem-Solving_Strategies_Engel.pdf) page 141 E18 75 76 **Code 1** 77 78 ``` 79 #include <bits/stdc++.h> 80 using namespace std; 81 int main(){ 82 int t; 83 cin >> t; 84 while(t--){ 85 long long k, l = 1, r = 2e18; 86 cin >> k; 87 while(r-l > 1){ 88 long long mid = (l+r)>>1; 89 long long n = mid - int(sqrtl(mid)); 90 if(n >= k) r = mid; 91 else l = mid; 92 } 93 cout << r << "\n"; 94 } 95 return 0; 96 } 97 ``` 98 99 **Code 2** 100 101 ``` 102 #include <bits/stdc++.h> 103 using namespace std; 104 int main(){ 105 int t; 106 cin >> t; 107 while(t--){ 108 long long k; 109 cin >> k; 110 cout << k + int(sqrtl(k) + 0.5) << "\n"; 111 } 112 return 0; 113 } 114 ``` 115 116 # [C. Bitwise Balancing](https://codeforces.com/contest/2020/problem/C) 117 118 By [P.V.Sekhar](/profile/P.V.Sekhar "Expert P.V.Sekhar") 119 120 **Hint 1** 121 122 Try to find some independent operations/combinations. 123 124 **Hint 2** 125 126 The expression is independent for each digit in binary representation 127 128 **Solution** 129 130 The first observation is that the expression $a$|$b$ - $a$&$c = d$ is bitwise independent. That is, the combination of a tuple of bits of $a, b, and\ c$ corresponding to the same power of 2 will only affect the bit value of $d$ at that power of 2 only. 131 132 This is because: 133 134 1. We are performing subtraction, so extra carry won't be generated to the next power of 2. 135 2. Any tuple of bits of $a$, $b$, and $c$ corresponding to the same power of 2 won't result in -1 for that power of 2. As that would require $a|b$ to be zero and $a$&$c$ to be one. The former condition requires the bit of $a$ to be zero, while the latter requires it to be one, which is contradicting. 136 137 Now, let us consider all 8 cases of bits of a, b, c and the corresponding bit value of d in the following table: 138 139  140 141 So, clearly, for different bits of $b, c,$ and $d$, we can find the value of the corresponding bit in $a$, provided it is not the case when bit values of $b, c,$ and $d$ are 1,0,0 or 0,1,1, which are not possible; so, in that case, the answer is -1. 142 143 **Code** 144 145 ``` 146 #include <bits/stdc++.h> 147 #define ll long long 148 using namespace std; 149 150 void solve() { 151 ll a = 0, b, c, d, pos = 1, bit_b, bit_c, bit_d, mask = 1; 152 cin >> b >> c >> d; 153 for (ll i = 0; i < 62; i++) { 154 if (b&mask) bit_b = 1; 155 else bit_b = 0; 156 if (c&mask) bit_c = 1; 157 else bit_c = 0; 158 if (d&mask) bit_d = 1; 159 else bit_d = 0; 160 if ((bit_b && (!bit_c) && (!bit_d)) || ((!bit_b) && bit_c && bit_d)) { 161 pos = 0; 162 break; 163 } 164 if (bit_b && bit_c) { 165 a += (1ll-bit_d)*mask; 166 } else { 167 a += bit_d*mask; 168 } 169 mask<<=1; 170 } 171 if (pos) { 172 cout << a << "\n"; 173 } else { 174 cout << -1 << "\n"; 175 } 176 } 177 178 int main() { 179 ll t; 180 cin >> t; 181 while (t--) { 182 solve(); 183 } 184 } 185 ``` 186 187 # [D. Connect the Dots](https://codeforces.com/contest/2020/problem/D) 188 189 By [P.V.Sekhar](/profile/P.V.Sekhar "Expert P.V.Sekhar") 190 191 **Hint 1** 192 193 The value of $d$ is very small. 194 195 **Hint 2** 196 197 Try using Disjoint Set Union (DSU). 198 199 **Solution** 200 201 The main idea is to take advantage of the low upper bound of $d_i$ and apply the Disjoint Set Union. 202 203 We will consider $dp[j][w]$, which denotes the number of ranges that contain the $j$ node in connection by the triplets/ranges with $w$ as $d$ and $j$ is not $a\ +\ k\ *\ d$, and $id[j][w]$, which denotes the node that represents an overall connected component of which $j$ node is part of for now. 204 205 The size of both $dp$ and $id$ is $max_j * max_w = (n) * 10 = 10\ n$. 206 207 We will maintain two other arrays, $Start_cnt[j][w]$ and $End_cnt[j][w]$, which store the number of triplets with $j$ as $a_i$ and $a_i+k_i*d_i$, respectively, and with $w$ as $d_i$, to help us maintain the beginning and end of ranges. 208 209 We will now apply Disjoint Set Union. For each $i$th triplet, we assume $a_i$ will be the parent node of the Set created by $a_i$, $a_i$ + $d_i$, ..., $a_i+k_i*d_i$. 210 211 The transitions of $dp$ are as follows: 212 213 1) if $j \ge 10$ (max of $d_i$): for all $w$, $dp[j][w]$ are the same as $dp[j-w][w]$, just with some possible changes. These changes are due to $j$ being the start or the end of some triplet with $d_i$ as $w.$ So, let us start with $dp[j][w]$ as $Start_cnt[j][w] - End_cnt[j][w]$. If $dp[j-w][w]$ is non-zero, then perform a union operation (of DSU) between the $j$ node and $id[j-w][w]$, increment $dp[j][w]$ by $dp[j-w][w]$, and assign $id[j][w]$ as $id[j-w][w]$. This unites the ranges over the $j$ node. 214 215 2) if $j \lt 10$ (max of $d_i$): we do the same as above; rather than doing for all $w,$ we would restrict ourselves with $w$ from $0$ to $j-1$. 216 217 The net time complexity = updation of $dp[j][w]$ value by $Start_cnt$ and $End_cnt$ + union operations due to union of $id[j-w][w]$ with $j$ over all $w$ + incrementing $dp$ values (by $dp[j-w][w]$) + copying $id$ values = $10\ n + 10\ nlogn + 10\ n + 10\ n= 10 nlogn + 30n$ (in worst case) = $O(max_d*n*logn)$. 218 219 **Code** 220 221 ``` 222 #include <bits/stdc++.h> 223 #define ll long long 224 using namespace std; 225 const ll N = 2e5+2; 226 const ll C = 10 + 1; 227 228 vector<ll> par(N), sz(N, 0); 229 vector<vector<ll>> dp(N, vector<ll> (C, 0)), ind(N, vector<ll> (C, 0)), start_cnt(N, vector<ll> (C, 0)), end_cnt(N, vector<ll> (C,0)); 230 231 ll find_par(ll a) { 232 if (par[a] == a) return a; 233 return par[a] = find_par(par[a]); 234 } 235 236 void unite(ll a, ll b){ 237 a = find_par(a), b = find_par(b); 238 if (a == b) return; 239 if (sz[b] > sz[a]) swap(a, b); 240 sz[a] += sz[b]; 241 par[b] = a; 242 } 243 244 void reset(ll n) { 245 for (ll i = 1; i <= n; i++) { 246 par[i] = i; 247 sz[i] = 1; 248 for (ll j = 1; j < C; j++) { 249 dp[i][j] = start_cnt[i][j] = end_cnt[i][j] = 0; 250 ind[i][j] = i; 251 } 252 } 253 } 254 255 void solve() { 256 ll n, m, a, d, k; 257 cin >> n >> m; 258 reset(n); 259 for (ll i = 0; i < m; i++) { 260 cin >> a >> d >> k; 261 start_cnt[a][d]++; 262 end_cnt[a + k * d][d]++; 263 } 264 for (ll i = 1; i <= n; i++) { 265 for (ll j = 1; j < C; j++) { 266 dp[i][j] = start_cnt[i][j] - end_cnt[i][j]; 267 if (i-j < 1) continue; 268 if (dp[i-j][j]) { 269 unite(ind[i-j][j], i); 270 ind[i][j] = ind[i-j][j]; 271 dp[i][j] += dp[i-j][j]; 272 } 273 } 274 } 275 ll ans = 0; 276 for (ll i = 1; i <= n; i++) { 277 if (find_par(i) == i) ans++; 278 } 279 cout << ans << "\n"; 280 } 281 282 int main() { 283 ll t; 284 cin >> t; 285 while (t--) { 286 solve(); 287 } 288 } 289 ``` 290 291 # [E. Expected Power](https://codeforces.com/contest/2020/problem/E) 292 293 By [nishkarsh](/profile/nishkarsh "Grandmaster nishkarsh") 294 295 **Hint 1** 296 297 Try to find the expected value of $f(S)$ rather than $(f(S))^2$. 298 299 **Hint 2** 300 301 Write the binary representation of $f(S)$ and find $(f(S))^2$. 302 303 **Solution** 304 305 Let the binary representation of the $Power$ be $b_{20}b_{19}...b_{0}$. Now $Power^2$ is $\sum_{i=0}^{20} \sum_{j=0}^{20} b_i b_j * 2^{i+j}$. Now if we compute the expected value of $b_ib_j$ for every pair $(i,j)$, then we are done. 306 307 We can achieve this by dynamic programming. For each pair $i,j$, there are only 4 possible values of $b_i,b_j$. For every possible value, we can maintain the probability of reaching it, and we are done. 308 309 The complexity of the solution is $O(n.log(max(a_i))^2)$. 310 311 **Code** 312 313 ``` 314 #include <bits/stdc++.h> 315 using namespace std; 316 int fast_exp(int b, int e, int mod){ 317 int ans = 1; 318 while(e){ 319 if(e&1) ans = (1ll*ans*b) % mod; 320 b = (1ll*b*b) % mod; 321 e >>= 1; 322 } 323 return ans; 324 } 325 const int mod = 1e9+7; 326 const int bits = 11; 327 328 int inv(int n){ 329 return fast_exp(n,mod-2,mod); 330 } 331 332 const int inverse_1e4 = inv(10000); 333 int dp[bits][bits][2][2]; 334 void transition(int a, int p){ 335 p = (1ll*p*inverse_1e4) % mod; 336 int negp = (mod+1-p) % mod; 337 int bin[bits]; 338 for(int i = 0; i < bits; i++){ 339 bin[i] = a&1; 340 a >>= 1; 341 } 342 for(int i = 0; i < bits; i++){ 343 for(int j = 0; j < bits; j++){ 344 int temp[2][2]; 345 346 for(int k : {0,1}) for(int l : {0,1}) temp[k][l] = (1ll*dp[i][j][k][l]*negp + 1ll*dp[i][j][k^bin[i]][l^bin[j]]*p) % mod; 347 348 for(int k : {0,1}) for(int l : {0,1}) dp[i][j][k][l] = temp[k][l]; 349 } 350 } 351 } 352 int main() { 353 int t; 354 cin >> t; 355 while(t--){ 356 int n; 357 cin >> n; 358 int a[n],p[n]; 359 for(int i = 0; i < n; i++) cin >> a[i]; 360 for(int i = 0; i < n; i++) cin >> p[i]; 361 for(int i = 0; i < bits; i++) for(int j = 0; j < bits; j++) dp[i][j][0][0] = 1; 362 for(int i = 0; i < n; i++) transition(a[i],p[i]); 363 int ans = 0; 364 for(int i = 0; i < bits; i++){ 365 for(int j = 0; j < bits; j++){ 366 int pw2 = (1ll<<(i+j)) % mod; 367 ans += (1ll*pw2*dp[i][j][1][1]) % mod; 368 ans %= mod; 369 for(int k : {0,1}) for(int l : {0,1}) dp[i][j][k][l] = 0; 370 } 371 } 372 cout << ans << "\n"; 373 } 374 return 0; 375 } 376 ``` 377 378 # [F. Count Leaves](https://codeforces.com/contest/2020/problem/F) 379 380 By [nishkarsh](/profile/nishkarsh "Grandmaster nishkarsh") 381 382 **Hint 1** 383 384 $f$ satisfies a special property for fixed d. 385 386 **Answer** 387 388 $f$ is multiplicative i.e. $f(x.y)$ = $f(x) * f(y)$ if $x,y$ are coprime, for fixed d. 389 390 **Solution** 391 392 It can be observed that the number of leaves is equal to the number of ways of choosing $d$ integers $a_0,a_1,a_2...a_d$ with $a_d = n$ and $a_i divides a_{i+1}$ for all $(0 \le i \le d-1)$. 393 394 Lets define $g(n) = f(n,d)$ for given $d$. It can be seen that the function $g$ is multiplicative i.e. $g(p*q) = g(p)*g(q)$ if $p$ and $q$ are coprime. 395 396 Now, lets try to calculate $g(n)$ when $n$ is of the form $p^x$ where $p$ is a prime number and $x$ is any non negative integer. From the first observation, we can say that here all the $a_i$ will be a power of $p$. Therefore $a_0,a_1,a_2...a_d$ can be written as $p^{b_0},p^{b_1},p^{b_2}...p^{b_d}$. Now we just have to ensure that $0 \le b_0 \le b_1 \le b_2 ... \le b_d = x$. The number of ways of doing so is $\binom{x+d}{d}$. 397 398 Now, lets make a dp (inspired by the idea of the dp used in [fast prime counting](https://codeforces.com/blog/entry/91632)) where $dp(n,x) = \sum_{i=1, spf(i) \gt = x}^{n} g(i)$. Here $spf(i)$ means smallest prime factor of $i$. 399 400 $ dp(x, p) = \begin{cases} 0 & \text{if } x = 0 \\ 1 & \text{if } p \gt x \\ dp(x, p+1) & \text{if } p \text{ is not prime} \\ \sum\limits_{i=0 \, \text{to} \, p^i \le x} dp\left(\lfloor{\frac{x}{p^i}} \rfloor, p+1\right) f(p^{ik}, d) & \text{otherwise} \end{cases} $ 401 402 Our required answer is $dp(n,2)$. 403 404 The overall complexity of the solution is $O(n^{\frac{2}{3}})$. 405 406 **Code** 407 408 ``` 409 #include <bits/stdc++.h> 410 #define ll long long 411 #define pb push_back 412 #define mp make_pair 413 #define F first 414 #define S second 415 #define pii pair<int,int> 416 #define pll pair<ll,ll> 417 #define pcc pair<char,char> 418 #define vi vector <int> 419 #define vl vector <ll> 420 #define sd(x) scanf("%d",&x) 421 #define slld(x) scanf("%lld",&x) 422 #define pd(x) printf("%d",x) 423 #define plld(x) printf("%lld",x) 424 #define pds(x) printf("%d ",x) 425 #define pllds(x) printf("%lld ",x) 426 #define pdn(x) printf("%d\n",x) 427 #define plldn(x) printf("%lld\n",x) 428 using namespace std; 429 ll powmod(ll base,ll exponent,ll mod){ 430 ll ans=1; 431 if(base<0) base+=mod; 432 while(exponent){ 433 if(exponent&1)ans=(ans*base)%mod; 434 base=(base*base)%mod; 435 exponent/=2; 436 } 437 return ans; 438 } 439 ll gcd(ll a, ll b){ 440 if(b==0) return a; 441 else return gcd(b,a%b); 442 } 443 const int INF = 2e9; 444 const ll INFLL = 4e18; 445 const int small_lim = 1e6+1; 446 const int mod = 1e9+7; 447 const int big_lim = 1e3+1; 448 ll primes_till_i[small_lim]; 449 ll primes_till_bigger_i[big_lim]; 450 vl sieved_primes[small_lim]; 451 vl sieved_primes_big[big_lim]; 452 vi prime; 453 int N,k,d; 454 void sieve(){ 455 vi lpf(small_lim); 456 ll pw; 457 for(int i = 2; i < small_lim; i++){ 458 if(! lpf[i]){ 459 prime.pb(i); 460 lpf[i] = i; 461 } 462 for(int j : prime){ 463 if((j > lpf[i]) || (j*i >= small_lim)) break; 464 lpf[j*i] = j; 465 } 466 } 467 for(int i = 2; i < small_lim; i++){ 468 primes_till_i[i] = primes_till_i[i-1] + (lpf[i] == i); 469 } 470 } 471 ll count_primes(ll n, int ind){ 472 if(ind < 0) return n-1; 473 if(1ll*prime[ind]*prime[ind] > n){ 474 if(n < small_lim) return primes_till_i[n]; 475 if(primes_till_bigger_i[N/n]) return primes_till_bigger_i[N/n]; 476 int l = -1, r = ind; 477 while(r-l > 1){ 478 int mid = (l+r)>>1; 479 if(1ll*prime[mid]*prime[mid] > n) r = mid; 480 else l = mid; 481 } 482 return primes_till_bigger_i[N/n] = count_primes(n,l); 483 } 484 int sz; 485 if(n < small_lim) sz = sieved_primes[n].size(); 486 else sz = sieved_primes_big[N/n].size(); 487 ll ans; 488 if(sz <= ind){ 489 ans = count_primes(n,ind-1); 490 ans -= count_primes(n/prime[ind],ind-1); 491 ans += ind; 492 if(n < small_lim) sieved_primes[n].pb(ans); 493 else sieved_primes_big[N/n].pb(ans); 494 } 495 if(n < small_lim) return sieved_primes[n][ind]; 496 else return sieved_primes_big[N/n][ind]; 497 } 498 ll count_primes(ll n){ 499 if(n < small_lim) return primes_till_i[n]; 500 if(primes_till_bigger_i[N/n]) return primes_till_bigger_i[N/n]; 501 return count_primes(n,prime.size()-1); 502 } 503 504 const int ncrlim = 3.5e6; 505 506 int fact[ncrlim]; 507 int invfact[ncrlim]; 508 509 void init_fact(){ 510 fact[0] = 1; 511 for(int i = 1; i < ncrlim; i++) fact[i] = (1ll*fact[i-1]*i)%mod; 512 invfact[ncrlim-1] = powmod(fact[ncrlim-1], mod-2, mod); 513 for(int i = ncrlim-1; i > 0; i--) invfact[i-1] = (1ll*invfact[i]*i)%mod; 514 } 515 516 int ncr(int n, int r){ 517 if(r > n || r < 0) return 0; 518 int ans = fact[n]; 519 ans = (1ll*ans*invfact[n-r]) % mod; 520 ans = (1ll*ans*invfact[r]) % mod; 521 return ans; 522 } 523 524 ll calculate_dp(ll n, int ind){ 525 if(n == 0) return 0; 526 if(prime[ind] > n) return 1; 527 ll ans = 1,temp; 528 if(1ll*prime[ind]*prime[ind] > n){ 529 temp = ncr(k+d,d); 530 temp *= count_primes(n)-ind; 531 ans+=temp; ans %= mod; 532 return ans; 533 } 534 ans = 0; 535 ll gg = 1; 536 ll mult = d; 537 while(gg <= n){ 538 temp = calculate_dp(n/gg,ind+1); 539 temp *= ncr(mult,d); 540 ans += temp; 541 ans %= mod; 542 mult += k; 543 gg *= prime[ind]; 544 } 545 return ans; 546 } 547 int main(){ 548 sieve(); 549 init_fact(); 550 int t; 551 sd(t); 552 while(t--){ 553 sd(N);sd(k);sd(d); 554 plldn(calculate_dp(N,0)); 555 for(int i = 1; i < big_lim; i++){ 556 primes_till_bigger_i[i] = 0; 557 sieved_primes_big[i].clear(); 558 } 559 } 560 return 0; 561 } 562 ```