codeforces-scrape

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

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 ![ ](/predownloaded/ea/0a/ea0a29a0ec0a741035e773e371865f0ee2f468ff.png)
    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 ```