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  . 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 . 138 Case-2 : Jon does find a new orb then the probability of it is . 139 140 Therefore,  141 We need to find the minimum *n* such that  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  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 . 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  296  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)**