codeforces-scrape

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

768.md (16709B)


      1 Source: https://codeforces.com/blog/entry/50550
      2 
      3 ## [768A. Oath of the Night's Watch](//codeforces.com/contest/768/problem/A)
      4 
      5 Set and Editorial by: [vntshh](/profile/vntshh "Expert vntshh")
      6 
      7 You just have to find the number of elements greater than the minimum number occurring in the array and less than the maximum number occurring in the array. This can be done in *O*(*n*) by traversing the array once and finding the minimum and maximum of the array, and then in another traversal, find the good numbers.
      8 
      9 **Complexity**: *O*(*n*)
     10 
     11 **Code**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16 int a[100005];
     17 int main()
     18 {
     19 	int n,c1=0,c2=0,mx=0,mn=1000000007;
     20 	cin>>n;
     21 	for(int i=0;i<n;i++) 
     22 	{
     23 		cin>>a[i];
     24 		mx=max(mx,a[i]),mn=min(mn,a[i]);
     25 	}
     26 	for(int i=0;i<n;i++)
     27 	{
     28 		if(a[i]==mx) c1++;
     29 		if(a[i]==mn) c2++;
     30 	}
     31 	if(mx==mn) cout<<0;
     32 	else cout<<(n-c1-c2); 
     33 	return 0;
     34 }
     35 ```
     36 
     37 ## [768B. Code For 1](//codeforces.com/contest/768/problem/B)
     38 
     39 Set and Editorial by: [killer_bee](/profile/killer_bee "Expert killer_bee")
     40 
     41 It is easy to see that the total number of elements in the final list will be ![](https://espresso.codeforces.com/44197176db49a965fdf3328a8ba950c15c7378e5.png) . The problem can be solved by locating each element in the list and checking whether it is '1' .The *i**th* element can be located in *O*(*logn*) by using Divide and Conquer strategy. Answer is the total number of all such elements which equal '1'.
     42 
     43 **Complexity** : *O*((*r* - *l* + 1) * *logn*)
     44 
     45 **Code**
     46 
     47 ```
     48 #include<bits/stdc++.h>
     49 using namespace std;
     50 long long int cnt(long long int temp) //returns the length of final list 
     51 {
     52   long long int x=1;
     53   while(temp>1)
     54   {
     55     temp/=2;
     56     x*=2;
     57   }
     58   return x;
     59 }
     60 int is_one(long long int pos,long long int target,long long int num)
     61 { 
     62   if(num<2)
     63     return num;
     64   if(pos+1==2*target)
     65   {
     66     return num%2;
     67   }
     68   num/=2;
     69   pos/=2;   
     70   if(target>pos+1)
     71       target-=(pos+1);      
     72   return is_one(pos,target,num);
     73 }
     74 int main()
     75 {
     76   long long int l,r,n,x,ans=0,i;
     77   cin>>n>>l>>r;
     78   x=cnt(n);
     79   x=2*x-1;
     80   for(i=l; i<=r; i++)  ans+=is_one(x,i,n);
     81   cout<<ans<<endl;  
     82   return 0;
     83 }
     84 ```
     85 
     86 ## [768C. Jon Snow and his Favourite Number](//codeforces.com/contest/768/problem/C)
     87 
     88 Set and Editorial by: [vntshh](/profile/vntshh "Expert vntshh")
     89 
     90 The range of strengths of any ranger at any point of time can be [0,1023]. This allows us to maintain a frequency array of the strengths of the rangers. Now, the updation of the array can be done in the following way: Make a copy of the frequency array. If the number of rangers having strength less than a strength *y* is even, and there are *freq*[*y*] rangers having strength y, ceil(*freq*[*y*] / 2) rangers will be updated and will have strengths *y*^*x*, and the remaining will retain the same strength. If the number of rangers having strength less than a strength *y* is odd,and there are *freq*[*y*] rangers having strength y, floor(*freq*[*y*] / 2) rangers will be updated and will have strengths *y*^*x*, and remaining will have the same strength. This operation has to be done *k* times, thus the overall complexity is *O*(1024 * *k*).
     91 
     92 **Complexity**: *O*(*k* * 210)
     93 
     94 **Code**
     95 
     96 ```
     97 #include<bits/stdc++.h>
     98 #define rep(i,start,lim) for(int i=start;i<lim;i++)
     99 using namespace std;
    100 #define N 100005
    101 int freq[1100],tmp[1024];
    102 int main()
    103 {
    104 	int n,k,maxm=0,minm=INT_MAX,p,x;
    105 	cin>>n>>k>>x;
    106 	rep(i,0,n) cin>>p,freq[p]++;
    107 	rep(i,0,k)
    108 	{
    109 		rep(j,0,1024) tmp[j]=freq[j];
    110 		int par=0;
    111 		rep(j,0,1024)
    112 		{
    113 			if(freq[j]>0)
    114 			{
    115 				int curr = (j^x),change = (freq[j]/2);
    116 				if(par==0) change+=(freq[j]&1);
    117 				tmp[j]-=change;
    118 				tmp[curr]+=change;
    119 				par^=(freq[j]&1);
    120 			}
    121 		}
    122 		rep(j,0,1024) freq[j]=tmp[j]; 
    123 	}
    124 	rep(i,0,1024) if(freq[i]>0) minm=min(minm,i),maxm=max(maxm,i);
    125 	cout<<maxm<<" "<<minm;
    126 	return 0;
    127 }
    128 ```
    129 
    130 ## [768D. Jon and Orbs](//codeforces.com/contest/768/problem/D)
    131 
    132 Set and Editorial by: [arnabsamanta](/profile/arnabsamanta "Expert arnabsamanta")
    133 
    134 This problem can be solve using inclusion-exclusion principle but precision errors need to be handled. Therefore, we use the following dynamic programming approach to solve this problem.
    135 
    136 On *n* - *th* day there are two possibilities,   
    137 Case-1 : Jon doesn't find a new orb then the probability of it is ![](https://espresso.codeforces.com/d30ed19719af8812cda01ebb43022b21281f9751.png).   
    138 Case-2 : Jon does find a new orb then the probability of it is ![](https://espresso.codeforces.com/32b740011d59b979598b5c1fa8c30958f6e90fa7.png).
    139 
    140 Therefore, ![](https://espresso.codeforces.com/c05910615cd3baece85084e077c5640f3daa31ae.png)   
    141 We need to find the minimum *n* such that ![](https://espresso.codeforces.com/5850482f7586818bee2c1ba0fa05439a5ade4f7c.png)   
    142 where,   
    143 *n* = number of days Jon waited.   
    144 *x* = number of distinct orbs Jon have till now.   
    145 *dp*[*n*][*x*] = probability of Jon having *x* distinct orbs in *n* days.   
    146 *k* = Total number of distinct orbs possible.
    147 
    148 **Code**
    149 
    150 ```
    151 #include <bits/stdc++.h>
    152 using namespace std;
    153 
    154 const int N = 1004;
    155 const double eps = 1e-7;
    156 double dp[N];
    157 int ans[N];
    158 
    159 int main(){
    160 	int k, q, d = 1;
    161 	cin >> k >> q;
    162 	dp[0] = 1;
    163 	for(int n = 1; d <= 1000; ++n){
    164 		for(int x = k; x > 0; --x){
    165 			dp[x] = (x * dp[x] + (k - x + 1) * dp[x - 1]) / k;
    166 		}
    167 		while(d <= 1000 && 2000 * dp[k] >= (d - eps)){
    168 			ans[d] = n;
    169 			d++;
    170 		}
    171 		dp[0] = 0;
    172 	}
    173 	while(q--){
    174 		int x;
    175 		cin >> x;
    176 		cout << ans[x] << "\n";
    177 	}
    178 }
    179 ```
    180 
    181 **PS:The ε was added so that the any solution considering the probability in the given range ![](https://espresso.codeforces.com/be050362f1c68c7d2d6f27bc964e5405e33bf506.png) passes the system tests.**
    182 
    183 ## [768E. Game of Stones](//codeforces.com/contest/768/problem/E)
    184 
    185 Set and Editorial by: [AakashHanda](/profile/AakashHanda "Expert AakashHanda")
    186 
    187 This problem can be solved using *DP with Bitmasks* to calculate the grundy value of piles. Let us have a 2-dimensional dp table, *dp*[*i*][*j*], where the first dimension is for number of stones in the pile and second dimension is for bitmask. The bitmask has *k*-th bit set if we are allowed to remove *k* + 1 stones from the pile.
    188 
    189 Now, to calculate *dp*[*i*][*j*] we need to iterate over all possible moves allowed and find the *mex*.
    190 
    191 **Code**
    192 
    193 ```
    194 dp[0][0] = 0;
    195 
    196 for(i=1 ; i<N ; ++i){
    197     for(j=0 ; j<(1<<N)-1 ; ++j){
    198         vector<bool> found(N, false);
    199 
    200         for(k=0 ; k<i ; ++k){
    201             if(((j>>k)&1) != 1)
    202                 continue;
    203             found[dp[i-k-1][j^(1<<k)]] = true;
    204         }
    205 
    206         for(k=0 ; k<N ; ++k){
    207             if(!found[k]){
    208                 dp[i][j] = k;
    209                 break;
    210             }
    211         }
    212     }
    213 }
    214 ```
    215 
    216 Finally for the game, we use the grundy values stored in *dp*[*i*][2*i* - 1] for a pile of size *i*. We take the xor of grundy values of all piles sizes. If it is 0, then Jon wins, otherwise Sam wins.
    217 
    218 The complexity of this solution is ![](https://espresso.codeforces.com/e5fab53156da4aa9a653e880fc47ad0c1aa5ca40.png). This will not be accepted. We can use the following optimizations for this problem:
    219 
    220 1. Use a top-down approach to calculate the values of *dp*[*i*][2*i* - 1], hence calculating only those values that are required.
    221 2. Since we can only remove at most i stones from a pile, as stated above, we need to store values from *j* in range [0, 2*i* - 1].
    222 
    223 So we can rewrite the above code to incorporate these change. Hence, the final solution is as follows
    224 
    225 **Code**
    226 
    227 ```
    228 #include<bits/stdc++.h>
    229 using namespace std;
    230 
    231 typedef long long ll;
    232 
    233 map<pair<int, ll>, int> grundy;
    234 map<pair<int, ll>, bool> mp;
    235 
    236 int retgrundy(int ps, ll bm, int prev = 63){
    237     for(int i=ps ; i<prev ; ++i){
    238         if(((bm>>i)&1LL) == 1LL)
    239             bm ^= (1LL<<i);
    240     }
    241     if(mp[{ps, bm}])
    242         return grundy[{ps, bm}];
    243     vector<bool> marked(63, false);
    244     for(int k=0 ; k<ps ; ++k){
    245         if(((bm>>k)&1LL) == 0)
    246             continue;
    247         marked[retgrundy(ps-k-1LL, (bm^(1LL<<k)), ps)] = true;
    248     }
    249     int ret;
    250     for(int i=0 ; i<63 ; ++i){
    251         if(marked[i])
    252             continue;
    253         grundy[{ps, bm}] = i;
    254         ret = i;
    255         break;
    256     }
    257     mp[{ps, bm}] = true;
    258     return ret;
    259 }
    260 
    261 int main(){
    262     int n, in, x=0;
    263     scanf("%d", &n);
    264 
    265     grundy[{0, 0}] = 0;
    266     mp[{0, 0}] = true;
    267     vector<int> gr(70, 0);
    268 
    269     for(int i=0 ; i<=60 ; ++i)
    270         gr[i] = retgrundy(i, (1LL<<i)-1LL);
    271 
    272     while(n--){
    273         scanf("%d", &in);
    274         x ^= gr[in];
    275     }
    276 
    277     if(x == 0)
    278         printf("YES");
    279     else
    280         printf("NO");
    281 
    282 }
    283 ```
    284 
    285 **Bonus: Try to find and prove the *O*(1) formula for grundy values**
    286 
    287 ## [768F. Barrels and boxes](//codeforces.com/contest/768/problem/F)
    288 
    289 Set and Editorial by: [arnabsamanta](/profile/arnabsamanta "Expert arnabsamanta"), [apoorv_kulsh](/profile/apoorv_kulsh "Candidate Master apoorv_kulsh")
    290 
    291 Every arrangement of stacks can expressed in the form of linear arrangement. In this linear arrangement, every contiguous segment of wine barrels are separated by food boxes. For the arrangement to be liked by Jon each of the *f* + 1 partitions created by *f* food boxes must contain either 0 or greater than *h* wine barrels.
    292 
    293 Let *u* out of *f* + 1 partitions have non-zero wine barrels then the remaining *r* + 1 - *u* partitions must have 0 wine barrels..
    294 
    295 Total number of arrangements with exactly u stacks of wine barrels are ![](https://espresso.codeforces.com/cf1e4d8c185b765571c714b7ecc68767d6d78920.png)   
    296 ![](https://espresso.codeforces.com/03c378cba2f9cb78ba671b9a607e9159edf31eb4.png) is the number of ways of choosing *u* partitions out of *f* + 1 partitions.   
    297 *X* is the number of ways to place *w* wine barrels in these *u* partitions which is equal to the coefficient of *x**w* in {*x**h* + 1·(1 + *x* + ...)}*u*. Finally we sum it up for all *u* from 1 to *f* + 1.
    298 
    299 So the time complexity becomes *O*(*w*) with pre-processing of factorials.
    300 
    301 ***w* = 0 was the corner case for which the answer was 1.   
    302 We did not anticipate it will cause so much trouble. Not placing it in the pretests was a rookie mistake.**
    303 
    304 **Code**
    305 
    306 ```
    307 #include <bits/stdc++.h>
    308 using namespace std;
    309 
    310 const int N = 212345;
    311 const int mod = 1000000007;
    312 int fac[N], ifac[N], inv[N];
    313 
    314 void prep(){
    315     fac[0] = ifac[0] = inv[1] = 1;
    316     for(int i = 1; i < N; ++i)
    317         fac[i] = 1LL * i * fac[i - 1] % mod;
    318     for(int i = 2; i < N; ++i) 
    319         inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
    320     for(int i = 1; i < N; ++i) 
    321         ifac[i] = 1LL * inv[i] * ifac[i - 1] % mod;
    322 }
    323 
    324 int C(int n, int r){
    325     if(r < 0 || n < r) return 0;
    326     return 1LL * fac[n] * ifac[n - r] % mod * ifac[r] % mod; 
    327 }
    328 
    329 int num(int r, int b, int k){
    330     if(b == 0) return 1;
    331     int ans = 0;
    332     for(int u = 1; u <= r + 1 && (k == 0 || u <= (b - 1) / k); ++u){
    333         ans += 1LL * C(r + 1,u) * C(b - k * u - 1, u - 1) % mod;
    334         ans %= mod;
    335     }
    336     return ans;
    337 }
    338 
    339 int pwr(int b, int p){
    340     int r = 1;
    341     while(p){
    342         if(p & 1) r = 1LL * r * b % mod;
    343         b = 1LL * b * b % mod;
    344         p >>= 1;
    345     }
    346     return r;
    347 }
    348 
    349 int finv(int x){
    350     return pwr(x, mod - 2);
    351 }
    352 
    353 int main(){
    354     prep();
    355     int f, w, h;
    356     cin >> f >> w >> h;
    357     int sn = num(f, w, h);
    358     int sd = C(f + w, w);
    359     cout << 1LL * sn * finv(sd) % mod << "\n";
    360 }
    361 ```
    362 
    363 ## [768G. The Winds of Winter](//codeforces.com/contest/768/problem/G)
    364 
    365 Set and Editorial by: [apoorv_kulsh](/profile/apoorv_kulsh "Candidate Master apoorv_kulsh")
    366 
    367 We are given a tree. We remove one node from this tree to form a forest. Strength of forest is defined as the size of largest tree in forest. We need to minimize the strength by changing the parent of atmost one node to some other node such that number of components remain same.
    368 
    369 To find the minimum value of strength we do a binary search on strength. It is possible to attain Strength *S* if   
    370 1. There is less than one component with size greater than *S*.   
    371 2. There exists a node in maximum component with subtree size *Y* such that,   
    372   *M* - *Y* ≤ *S*  (Here *M* is size of maximum component and m is size of minimum component)   
    373   *m* + *Y* ≤ *S*.   
    374 Then we can change the parent of this node to some node in smallest component.
    375 
    376 The problem now is to store Subtree_size of all nodes in the maximum component and perform binary search on them. We can use Stl Map for this.   
    377 Let *X* be the node which is removed and *X**size* be its subtree size There are two cases now -:   
    378 1. When max size tree is child of *X*.   
    379 2. When max size tree is the tree which remains when we remove subtree of *X* from original tree.(We refer to this as outer tree of *X*).
    380 
    381 In the second case the subtree sizes of nodes on path from root to *X* will change when *X* is removed. Infact their subtree size will decrease exactly by *X**size*. While performing binary search on these nodes there will be an offset of *X**size*. So we store them seperately. Now we need to maintain 3 Maps,   
    382 where   
    383 *map**children* : Stores the Subtree_size of all nodes present in heaviest child of *X*.   
    384 *map**parent* : Stores the Subtree_size of all nodes on the path from root to *X*.   
    385 *map**outer* : Stores the Subtree_size of all nodes in outer tree which are not on path from root to *X*.
    386 
    387 Go through this blog post before reading further [(http://codeforces.com/blog/entry/44351)](//codeforces.com/blog/entry/44351).   
    388    
    389 Maintaining the Maps   
    390 *map**children* and *map**parent* are initialised to empty while *map**outer* contains Subtree_size of all nodes in the tree.  
    391    
    392 *map**parent* : This can be easily maintained by inserting the Subtree_size of node in map when we enter a node in dfs and remove it when we exit it.   
    393 *map**children* : *map**children* can be maintained by using the dsu on tree trick mentioned in blogpost.   
    394 *map**outer* : When we insert a node's subtree_size in *map**childern* or *map**parent* we can remove the same from *map**outer* and similarly when we insert a node's Subtree_size in *map**childern* or *map**parent* we can remove the same from *map**outer*.
    395 
    396 Refer to HLD style implementation in blogpost for easiest way of maintaining *map**outer*.   
    397 Refer to code below for exact point of insertions and deletions into above mentioned 3 maps.
    398 
    399 **Code**
    400 
    401 ```
    402 #include <bits/stdc++.h>
    403 using namespace std;
    404 
    405 const int N = 100005;
    406 vector<int> adj[N];
    407 int sz[N], ans[N];
    408 int n, root;
    409 bool big[N];
    410 map<int,int> mp, mpo, par;
    411 
    412 void getsz(int s){
    413     sz[s] = 1;
    414     ans[s] = n - 1;
    415     for(auto it : adj[s]){
    416         getsz(it);
    417         sz[s] += sz[it];
    418     }
    419     mpo[sz[s]]++;
    420 }
    421 
    422 void bs(map<int, int> &mp1, int l, int r, int mi, int s, int off){
    423     if(mi == n - 1) return;
    424     int ma = r;
    425     while(r - l > 1){
    426         int mid = (r + l) / 2;
    427         auto it = mp1.lower_bound(ma - mid + off);
    428         if(it == mp1.end()) 
    429             l = mid;
    430         else if(mi + it->first <= mid + off) 
    431             r = mid;
    432         else 
    433             l = mid;
    434     }
    435     ans[s] = min(ans[s], r);
    436 }
    437 
    438 void add(int s){
    439     mp[sz[s]]++;
    440     if(mpo[sz[s]] == 1)
    441         mpo.erase(sz[s]);
    442     else
    443         mpo[sz[s]]--;
    444     for(auto it:adj[s])
    445         if(!big[it]) add(it);
    446 }
    447 
    448 void rem(int s){
    449     mpo[sz[s]]++;
    450     if(mp[sz[s]] == 1)
    451         mp.erase(sz[s]);
    452     else
    453         mp[sz[s]]--;
    454     for(auto it:adj[s])
    455         if(!big[it]) rem(it);
    456 }
    457 
    458 void dfs(int s, bool isbig){
    459     par[sz[s]]++;
    460     if(mpo[sz[s]] == 1)
    461         mpo.erase(sz[s]);
    462     else
    463         mpo[sz[s]]--;
    464     int ma = -1, sma = -1, mac = -1, mi = n - 1;
    465     for(auto it:adj[s]){
    466         if(sz[it]>ma){
    467             sma = ma;
    468             ma = sz[it];
    469             mac = it;
    470         }
    471         else if(sz[it]==ma)
    472             sma = ma;
    473         else
    474             sma = max(sma,sz[it]);
    475         mi = min(mi,sz[it]);
    476     }
    477     if(s != root)
    478         mi = min(mi,n-sz[s]);
    479     for(auto it:adj[s]){
    480         if(it!=mac)
    481             dfs(it,0);
    482     }
    483     if(mac != -1){
    484         big[mac]=true;
    485         dfs(mac,1);
    486     }
    487     if(ma >= n - sz[s]){
    488         sma = max(sma, n - sz[s]);
    489         bs(mp, sma - 1, ma, mi, s, 0);
    490     }
    491     mpo[sz[s]]++;
    492     add(s);
    493     if(par[sz[s]] == 1)
    494         par.erase(sz[s]);
    495     else
    496         par[sz[s]]--;
    497     if(n-sz[s] > ma){
    498         sma = ma;
    499         bs(mpo, sma - 1, n - sz[s], mi, s, 0);
    500         bs(par, sma - 1, n - sz[s], mi, s, sz[s]);
    501     }
    502     if(mac != -1)
    503         big[mac] = false;
    504     if(!isbig) rem(s);
    505 }
    506 
    507 int main(){
    508     int i, u, v;
    509     scanf("%d", &n);
    510     for(i = 0; i < n; ++i){
    511         scanf("%d%d", &u ,&v);
    512         if(u == 0) root = v - 1;
    513         else
    514             adj[u - 1].push_back(v - 1);
    515     }
    516     getsz(root);
    517     dfs(root, 1);
    518     for(i = 0; i < n; ++i)
    519         printf("%d\n", ans[i]);
    520 }
    521 ```
    522 
    523 **Complexity *O*(*NlogN*2)**