712.md (11390B)
1 Source: https://codeforces.com/blog/entry/47050 2 3 Hi everyone, here are the solutions to the contest problems. 4 5 [712A — Memory and Crow](//codeforces.com/problemset/problem/712/A) 6 7 Note that *a*[*i*] + *a*[*i* + 1] = *b*[*i*]. Use the initial condition *b*[*n*] = *a*[*n*] and we can figure out the entire array *b*. 8 9 Time Complexity: *O*(*n*) 10 11 **Code** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int arr[100000]; 19 int ans[100000]; 20 int main() 21 { 22 int n; 23 cin >> n; 24 for(int i=0; i < n; i++){ 25 cin >> arr[i]; 26 27 } 28 29 for(int i = n-1; i >=0; i--){ 30 if(i==n-1) ans[i] = arr[i]; 31 else ans[i] = arr[i] + arr[i+1]; 32 } 33 for(int i=0; i < n; i++){ 34 cout << ans[i] << " "; 35 } 36 cout << endl; 37 return 0; 38 } 39 ``` 40 41 [712B — Memory and Trident](//codeforces.com/problemset/problem/712/B) 42 43 First, if *S* has odd length, there is no possible string because letters must come in opposite pairs. Now, let's denote the ending coordinate after following *S* as (*x*, *y*). Since *S* has even length, |*x*| has the same parity as |*y*|. Suppose they are both even. Then clearly, we can make *x* = 0 in exactly  moves, and same for *y*. If instead they are both odd, then we can change exactly one x-character into a y-character. With the correct choices of these characters, now our string has |*x*| and |*y*| with even parity, thus reducing to the problem above. Therefore, the answer is (|*x*| + |*y*|) / 2. 44 45 Time Complexity: *O*(|*S*|) 46 47 **Code** 48 49 ``` 50 #include <string> 51 #include <iostream> 52 #include <stdlib.h> 53 using namespace std; 54 55 int main() 56 { 57 string str; 58 cin >> str; 59 if(str.length()%2==1){ 60 cout << -1 << endl; 61 return 0; 62 } 63 64 int x=0,y=0; 65 for(int i=0; i < str.length(); i++){ 66 if(str[i]=='U')y++; 67 if(str[i]=='D')y--; 68 if(str[i]=='L')x--; 69 if(str[i]=='R')x++; 70 } 71 cout << (abs(x)+abs(y))/2 << endl; 72 } 73 ``` 74 75 [712C — Memory and De-Evolution](//codeforces.com/problemset/problem/712/C) 76 77 Let's reverse the process: start with an equilateral triangle with side length *y*, and lets get to an equilateral triangle with side length *x*. In each step, we can act greedily while obeying the triangle inequality. This will give us our desired answer. 78 79 Time Complexity: *O*(*log* *x*) 80 81 **Code** 82 83 ``` 84 #include <bits/stdc++.h> 85 86 using namespace std; 87 88 int main() 89 { 90 int x,y; 91 cin >> x >> y; 92 93 int besta=y,bestb=y,bestc=y; 94 95 int turns = 0; 96 while(true){ 97 //check the current 98 if(besta>=x && bestb>=x && bestc>=x){ 99 cout << turns << endl; 100 break; 101 } 102 turns++; 103 if(turns%3==1){ 104 //update a 105 besta = bestb+bestc-1; 106 } 107 if(turns%3==2){ 108 //update b 109 bestb = besta+bestc-1; 110 } 111 if(turns%3==0){ 112 //update c 113 bestc = besta+bestb-1; 114 } 115 } 116 return 0; 117 } 118 ``` 119 120 [712D — Memory and Scores](//codeforces.com/problemset/problem/712/D) 121 122 One approach to this problem is by first implementing naive DP in *O*((*kt*)2). The state for this is (*diff*, *turn*), and transitions for (*diff*, *turn*) is the sum (*diff* - 2*k*, *turn* - 1) + 2(*diff* - 2*k* + 1, *turn* - 1) + 3(*diff* - 2*k* + 2, *turn* - 1) + ... + (2*k* + 1)(*diff*, *turn* - 1) + 2*k*(*diff* + 1, *turn* - 1) + ... + *diff*( + 2*k*, *turn* - 1). 123 124 Now, if we use prefix sums of all differences in (turn-1), along with a sliding window technique across the differences, we can cut a factor of *k*, to achieve desired complexity *O*(*kt*2). 125 126 However, there is a much nicer solution in *O*(*kt* *log* *kt*) using generating functions(thanks to [minimario](/profile/minimario "Candidate Master minimario")). We can compute the coefficients of , and the coefficient to *x**i* corresponds to the number of ways we can form the difference *i*. To compute these coefficients, we can use the binomial theorem. 127 128 Time Complexity: *O*(*kt*2) 129 130 **Code** 131 132 ``` 133 #include <bits\stdc++.h> 134 using namespace std; 135 136 int MOD = 1000000007; 137 long long dp[2][1000000]; 138 int lowest; 139 140 int h(int v){ 141 return v - lowest; 142 } 143 int main() 144 { 145 int a,b,k,t; 146 cin >> a >> b >> k >> t; 147 int lowb = a-b; 148 int highb = a-b; 149 150 lowest = lowb - 2*k*(t); 151 dp[0][h(lowb)] = 1l; 152 //solve for ti = 0 153 int curr = 1; 154 for(int p = lowb-2*k; p<= lowb; p++){ 155 dp[1][h(p)] = curr; 156 curr++; 157 } 158 curr--; 159 for(int p = lowb+1; p<= lowb+2*k; p++){ 160 curr--; 161 dp[1][h(p)] = curr; 162 } 163 lowb -=2*k; 164 highb+=2*k; 165 for(int ti = 1; ti <= t-1; ti++){ 166 int o = ti%2; 167 vector<long long> pref; 168 pref.push_back(dp[o][h(lowb)]); 169 long long su = dp[o][h(lowb)]; 170 for(int p = lowb+1; p <= highb; p++){ 171 su = (su+dp[o][h(p)])%MOD; 172 pref.push_back(su); 173 } 174 int pe = 2*k; 175 int il = 0; 176 int ir = 0; 177 int l = lowb; 178 int r = lowb; 179 int np = lowb-2*k; 180 long long sum = 0; 181 //get the prefix first 182 183 while(ir<=2*k){ 184 //evaluate current 185 sum = (sum + pref[ir])%MOD; 186 dp[!o][h(np)] = sum; 187 //update for the next thing 188 ir++; 189 r++; 190 np++; 191 } 192 pe = 0; 193 ir--; 194 r--; 195 np--; 196 while(pe<2*k){ 197 pe++; 198 ir++; 199 r++; 200 np++; 201 //evaluate 202 sum = (sum + pref[ir])%MOD; 203 sum = (sum - 2*pref[pe-1])%MOD; 204 sum = (sum+MOD)%MOD; 205 dp[!o][h(np)] = sum; 206 } 207 208 //slide into those dm's 209 while(r<highb){ 210 //update 211 pe++; 212 r++; 213 l++; 214 ir++; 215 il++; 216 np++; 217 218 long long sum1 = pref[pe-1] - ( (il==1) ? 0 : pref[(il-1)-1]); 219 long long sum2 = pref[ir] - pref[pe-1]; 220 sum = (sum - sum1 + MOD)%MOD; 221 sum = (sum + sum2)%MOD; 222 dp[!o][h(np)] = sum; 223 } 224 //finally, suffix 225 while(l<highb){ 226 l++; 227 il++; 228 pe++; 229 np++; 230 //subtract [l-1,pe-1] 231 long long sum1 = pref[min(pe-1,ir)] - ((il==1) ? 0 : pref[il-1-1]); 232 sum = (sum - sum1 + MOD)%MOD; 233 if(pe>ir){ 234 235 } 236 else{ 237 long long sum2 = pref[ir]-pref[pe-1]; 238 sum = (sum + sum2)%MOD; 239 } 240 dp[!o][h(np)] = sum; 241 } 242 243 lowb-=2*k; 244 highb+=2*k; 245 } 246 long long ans = 0; 247 int o = t%2; 248 for(int p = 1; p <= highb; p++){ 249 ans = (ans+dp[o][h(p)])%MOD; 250 } 251 cout << ans << endl; 252 } 253 ``` 254 255 Time Complexity: *O*(*kt* *log* *kt*) 256 257 **Code** 258 259 ``` 260 #include <bits/stdc++.h> 261 using namespace std; 262 263 typedef long long ll; 264 typedef pair<int, int> pii; 265 typedef vector<int> vi; 266 267 #define f first 268 #define s second 269 #define pb push_back 270 #define mp make_pair 271 272 #define FOR(i, a, b) for (int i=a; i<b; i++) 273 #define F0R(i, a) FOR(i, 0, a) 274 275 const int MAX = 1000005; 276 const int MOD = 1000000007; 277 278 int f[MAX]; 279 int fi[MAX]; 280 281 int pos(int a) { return ((ll)a%MOD+MOD)%MOD; } 282 int add(int a, int b) { return ((ll)a+(ll)b)%MOD; } 283 int sub(int a, int b) { return pos(a-b); } 284 int mult(int a, int b) { return (ll)pos(a)*b%MOD; } 285 int sq(int a) { return (ll)a*a%MOD; } 286 287 int expo(int a, int b) { 288 if (b == 0) { return 1; } 289 if (b%2) { return mult(a, sq(expo(a, b/2))); } 290 else { return sq(expo(a, b/2)); } 291 } 292 int inv(int a) { return expo(a, MOD-2); } 293 294 int c(int n, int k) { 295 return mult(f[n], mult(fi[k], fi[n-k])); 296 } 297 298 int poly1[MAX]; 299 int pref2[MAX]; 300 int main() { 301 f[0] = fi[0] = 1; 302 FOR(i, 1, MAX) { f[i] = mult(f[i-1], i); fi[i] = inv(f[i]); } 303 int a, b, k, t; 304 cin >> a >> b >> k >> t; 305 if(b-a > 2*k*t){ 306 cout << 0 << endl; 307 return 0; 308 } 309 F0R(i, 2*t+1) { poly1[(2*k+1)*i] = ((i%2==0)?1:-1)*c(2*t, i); } 310 F0R(i, MAX) { pref2[i] = c(2*t-1+i+1, 2*t); } 311 int lb = 2*k*t+b-a+1; 312 int ub = 4*k*t; 313 int ans = 0; 314 F0R(i, 2*t+1) { 315 int l = lb-(2*k+1)*i; 316 int u = ub-(2*k+1)*i; 317 if (u < 0) { break; } 318 if (l < 0) { ans = add(ans, mult(poly1[(2*k+1)*i], pref2[u])); } 319 else { ans = add(ans, mult(poly1[(2*k+1)*i], sub(pref2[u], pref2[l-1]))); } 320 } 321 cout << ans << endl; 322 } 323 ``` 324 325 [712E — Memory and Casinos](//codeforces.com/problemset/problem/712/E) 326 327 Lets think about two segments of casinos [*i*, *j*] and [*j* + 1, *n*]. Let *L*([*a*, *b*]) denote the probability we dominate on [*a*, *b*], and let *R*([*a*, *b*]) denote the probability we start on *b* and end by moving right of *b*. Let 328 329 *l*1 = *L*([*i*, *j*]), 330 331 *l*2 = *L*([*j* + 1, *n*]), 332 333 *r*1 = *R*([*i*, *j*]), 334 335 *r*2 = *R*([*j* + 1, *n*]). 336 337 You can use a geometric series to figure out both *L*([*i*, *n*]) and *R*([*i*, *n*]) using only *l*1,*l*2,*r*1, and *r*2. To derive these series, think about the probability we cross over from *j* to *j* + 1 once, twice, three times, and so on. The actual formulas are, 338 339  340 341  342 343 Now we can build a segment tree on the casinos, and use the above to merge segments. 344 345 Time Complexity: *O*(*N* + *QlogN*) 346 347 **Code** 348 349 ``` 350 #include <bits/stdc++.h> 351 using namespace std; 352 353 int n; 354 double pr[100000]; 355 pair<double,double> seg[400000]; 356 bool ze(double d){ 357 return (abs(d) <= 0.0000000001); 358 } 359 pair<double,double> merge(pair<double,double> a, pair<double,double> b){ 360 if(ze(a.first+1) && ze(a.second+1)) return b; 361 if(ze(b.first+1) && ze(b.second+1)) return a; 362 double l1 = a.first; 363 double r1 = a.second; 364 double l2 = b.first; 365 double r2 = b.second; 366 if(ze(((l2-1)*r1+1))) return make_pair(0,0); 367 double le = l1*l2/((l2-1)*r1+1); 368 double ri = r2+(r1*l2*(-r2+1))/(-r1*(-l2+1)+1); 369 return make_pair(le,ri); 370 } 371 void build(int no, int b, int e){ 372 if(b==e){ 373 seg[no] = make_pair(pr[b],pr[b]); 374 return; 375 } 376 int mid = (b+e)/2; 377 build(2*no,b,mid); 378 build(2*no+1,mid+1,e); 379 seg[no] = merge(seg[2*no],seg[2*no+1]); 380 } 381 void upd(int no, int b, int e, int i, double val){ 382 if(i<b || i>e) return; 383 if(b==e){ 384 seg[no] = make_pair(val,val); 385 return; 386 } 387 int mid = (b+e)/2; 388 upd(2*no,b,mid,i,val); 389 upd(2*no+1,mid+1,e,i,val); 390 seg[no] = merge(seg[2*no],seg[2*no+1]); 391 } 392 pair<double,double> query(int no, int b, int e, int l, int r){ 393 if(b>r || e<l) return make_pair(-1,-1); 394 if(l<=b && e<=r) return seg[no]; 395 int mid = (b+e)/2; 396 return merge(query(2*no,b,mid,l,r),query(2*no+1,mid+1,e,l,r)); 397 } 398 int main(){ 399 int q; 400 scanf("%d %d", &n, &q); 401 for(int i=0; i < n; i++){ 402 int a,b; 403 scanf("%d %d", &a, &b); 404 pr[i] = (double)a / (double)b; 405 } 406 407 build(1,0,n-1); 408 for(int que = 0; que < q; que++){ 409 int ty; 410 int a; 411 int b; 412 scanf("%d %d %d", &ty, &a, &b); 413 if(ty==1){ 414 int c; 415 scanf("%d", &c); 416 upd(1,0,n-1,a-1, (double)b / (double)c); 417 } 418 else{ 419 printf("%.20f\n", query(1,0,n-1,a-1,b-1).first); 420 } 421 } 422 423 return 0; 424 } 425 ```