codeforces-scrape

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

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 ![](https://espresso.codeforces.com/0d4cf95deb5072b2933427213ce509561f91fbb2.png) 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 ![](https://espresso.codeforces.com/3268adcb0654a25f3e7948a953c0aa842b38ec07.png), 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 ![](https://espresso.codeforces.com/3d18c22f4e210c07f56e0bef7c1888041308e7bf.png)
    340 
    341 ![](https://espresso.codeforces.com/a9858c947d815f7f89917e1476296598287b1bdb.png)
    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 ```