Codeforces Round #370 Editorial
Difference between en2 and en3, changed 2 character(s)
Hi everyone, here are the solutions to the contest problems.↵

[712A — Memory and Crow](http://codeforces.net/problemset/problem/712/A)↵

Note that $b[i]+b[i+1] = a[i]$. Use the initial condition $b[n]=a[n]$ and we can figure out the entire array $a$.↵

Time Complexity: $O(n)$↵

<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int arr[100000];↵
int ans[100000];↵
int main()↵
{↵
    int n;↵
    cin >> n;↵
    for(int i=0; i < n; i++){↵
        cin >> arr[i];↵

    }↵

    for(int i = n-1; i >=0; i--){↵
        if(i==n-1) ans[i] = arr[i];↵
        else ans[i] = arr[i] + arr[i+1];↵
    }↵
    for(int i=0; i < n; i++){↵
        cout << ans[i] << " ";↵
    }↵
    cout << endl;↵
    return 0;↵
}↵

~~~~~↵


</spoiler>↵

[712B &mdash; Memory and Trident](http://codeforces.net/problemset/problem/712/B)↵

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 $\frac{|x|}{2}$ 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$.↵

Time Complexity: $O(|S|)$↵

<spoiler summary="Code">↵

~~~~~↵
#include <string>↵
#include <iostream>↵
#include <stdlib.h>↵
using namespace std;↵


int main()↵
{↵
    string str;↵
    cin >> str;↵
    if(str.length()%2==1){↵
        cout << -1 << endl;↵
        return 0;↵
    }↵

    int x=0,y=0;↵
    for(int i=0; i < str.length(); i++){↵
        if(str[i]=='U')y++;↵
        if(str[i]=='D')y--;↵
        if(str[i]=='L')x--;↵
        if(str[i]=='R')x++;↵
    }↵
    cout << (abs(x)+abs(y))/2 << endl;↵
}↵

~~~~~↵


</spoiler>↵

[712C &mdash; Memory and De-Evolution](http://codeforces.net/problemset/problem/712/C)↵

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.↵

Time Complexity: $O(log$ $x)$↵

<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int main()↵
{↵
    int x,y;↵
    cin >> x >> y;↵

    int besta=y,bestb=y,bestc=y;↵

    int turns = 0;↵
    while(true){↵
        //check the current↵
        if(besta>=x && bestb>=x && bestc>=x){↵
            cout << turns << endl;↵
            break;↵
        }↵
        turns++;↵
        if(turns%3==1){↵
            //update a↵
            besta = bestb+bestc-1;↵
        }↵
        if(turns%3==2){↵
            //update b↵
            bestb = besta+bestc-1;↵
        }↵
        if(turns%3==0){↵
            //update c↵
            bestc = besta+bestb-1;↵
        }↵
    }↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

[712D &mdash; Memory and Scores](http://codeforces.net/problemset/problem/712/D)↵

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-2k,turn-1) + 2 (diff-2k+1,turn-1) + 3(diff-2k+2,turn-1) + \dots + (2k+1)(diff,turn-1) + 2k(diff+1,turn-1) + \dots$↵
 $+ diff(+2k,turn-1)$.↵

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(k t^2)$.↵

However, there is a much nicer solution in $O(kt$ $log$ $kt)$ using generating functions. We can compute the coefficients of $(\frac{(1+x+x^2 + \dots + x^{2k})}{x^k})^{2t}$, 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.↵

Time Complexity: $O(k t^2)$↵

<spoiler summary="Code">↵

~~~~~↵

#include <bits\stdc++.h>↵
using namespace std;↵

int MOD = 1000000007;↵
long long dp[2][1000000];↵
int lowest;↵

int h(int v){↵
    return v - lowest;↵
}↵
int main()↵
{↵
    int a,b,k,t;↵
    cin >> a >> b >> k >> t;↵
    int lowb = a-b;↵
    int highb = a-b;↵

    lowest = lowb - 2*k*(t);↵
    dp[0][h(lowb)] = 1l;↵
    //solve for ti = 0↵
    int curr = 1;↵
    for(int p = lowb-2*k; p<= lowb; p++){↵
        dp[1][h(p)] = curr;↵
        curr++;↵
    }↵
    curr--;↵
    for(int p = lowb+1; p<= lowb+2*k; p++){↵
        curr--;↵
        dp[1][h(p)] = curr;↵
    }↵
    lowb -=2*k;↵
    highb+=2*k;↵
    for(int ti = 1; ti <= t-1; ti++){↵
        int o = ti%2;↵
        vector<long long> pref;↵
        pref.push_back(dp[o][h(lowb)]);↵
        long long su = dp[o][h(lowb)];↵
        for(int p = lowb+1; p <= highb; p++){↵
            su = (su+dp[o][h(p)])%MOD;↵
            pref.push_back(su);↵
        }↵
        int pe = 2*k;↵
        int il = 0;↵
        int ir = 0;↵
        int l = lowb;↵
        int r = lowb;↵
        int np = lowb-2*k;↵
        long long sum = 0;↵
        //get the prefix first↵

        while(ir<=2*k){↵
            //evaluate current↵
            sum = (sum + pref[ir])%MOD;↵
            dp[!o][h(np)] = sum;↵
            //update for the next thing↵
            ir++;↵
            r++;↵
            np++;↵
        }↵
        pe = 0;↵
        ir--;↵
        r--;↵
        np--;↵
        while(pe<2*k){↵
            pe++;↵
            ir++;↵
            r++;↵
            np++;↵
            //evaluate↵
            sum = (sum + pref[ir])%MOD;↵
            sum = (sum - 2*pref[pe-1])%MOD;↵
            sum = (sum+MOD)%MOD;↵
            dp[!o][h(np)] = sum;↵
        }↵

        //slide into those dm's↵
        while(r<highb){↵
            //update↵
            pe++;↵
            r++;↵
            l++;↵
            ir++;↵
            il++;↵
            np++;↵

            long long sum1 = pref[pe-1] - ( (il==1) ? 0 : pref[(il-1)-1]);↵
            long long sum2 = pref[ir] - pref[pe-1];↵
            sum = (sum - sum1 + MOD)%MOD;↵
            sum = (sum + sum2)%MOD;↵
            dp[!o][h(np)] = sum;↵
        }↵
        //finally, suffix↵
        while(l<highb){↵
            l++;↵
            il++;↵
            pe++;↵
            np++;↵
            //subtract [l-1,pe-1]↵
            long long sum1 = pref[min(pe-1,ir)] - ((il==1) ? 0 : pref[il-1-1]);↵
            sum = (sum - sum1 + MOD)%MOD;↵
            if(pe>ir){↵

            }↵
            else{↵
                long long sum2 = pref[ir]-pref[pe-1];↵
                sum = (sum + sum2)%MOD;↵
            }↵
            dp[!o][h(np)] = sum;↵
        }↵

        lowb-=2*k;↵
        highb+=2*k;↵
    }↵
    long long ans = 0;↵
    int o = t%2;↵
    for(int p = 1; p <= highb; p++){↵
        ans = (ans+dp[o][h(p)])%MOD;↵
    }↵
    cout << ans << endl;↵
}↵

~~~~~↵


</spoiler>↵

Time Complexity: $O(kt$ $log$ $kt)$↵

<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

typedef long long ll;↵
typedef pair<int, int> pii;↵
typedef vector<int> vi;↵

#define f first↵
#define s second↵
#define pb push_back↵
#define mp make_pair↵

#define FOR(i, a, b) for (int i=a; i<b; i++)↵
#define F0R(i, a) FOR(i, 0, a)↵

const int MAX = 1000005;↵
const int MOD = 1000000007;↵

int f[MAX];↵
int fi[MAX];↵

int pos(int a) { return ((ll)a%MOD+MOD)%MOD; }↵
int add(int a, int b) { return ((ll)a+(ll)b)%MOD; }↵
int sub(int a, int b) { return pos(a-b); }↵
int mult(int a, int b) { return (ll)pos(a)*b%MOD; }↵
int sq(int a) { return (ll)a*a%MOD; }↵

int expo(int a, int b) {↵
    if (b == 0) { return 1; }↵
    if (b%2) { return mult(a, sq(expo(a, b/2))); }↵
    else { return sq(expo(a, b/2)); }↵
}↵
int inv(int a) { return expo(a, MOD-2); }↵

int c(int n, int k) {↵
    return mult(f[n], mult(fi[k], fi[n-k]));↵
}↵

int poly1[MAX];↵
int pref2[MAX];↵
int main() {↵
    f[0] = fi[0] = 1;↵
    FOR(i, 1, MAX) { f[i] = mult(f[i-1], i); fi[i] = inv(f[i]); }↵
    int a, b, k, t;↵
    cin >> a >> b >> k >> t;↵
    if(b-a > 2*k*t){↵
     cout << 0 << endl;↵
     return 0;↵
    }↵
    F0R(i, 2*t+1) { poly1[(2*k+1)*i] = ((i%2==0)?1:-1)*c(2*t, i); }↵
    F0R(i, MAX) { pref2[i] = c(2*t-1+i+1, 2*t); }↵
    int lb = 2*k*t+b-a+1;↵
    int ub = 4*k*t;↵
    int ans = 0;↵
    F0R(i, 2*t+1) {↵
        int l = lb-(2*k+1)*i;↵
        int u = ub-(2*k+1)*i;↵
        if (u < 0) { break; }↵
        if (l < 0) { ans = add(ans, mult(poly1[(2*k+1)*i], pref2[u])); }↵
        else { ans = add(ans, mult(poly1[(2*k+1)*i], sub(pref2[u], pref2[l-1]))); }↵
    }↵
    cout << ans << endl;↵
}↵
~~~~~↵


</spoiler>↵

[712E &mdash; Memory and Casinos](http://codeforces.net/problemset/problem/712/E)↵

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 ↵

$l_1=L([i,j])$, ↵

$l_2=L([j+1,n])$,↵

$r_1=R([i,j])$,↵

$r_2=R([j+1,n])$.↵

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,↵

$L([i,n]) = \dfrac{l_1 l_2}{1+r_1(l_2-1)}$↵

$R([i,n]) = r_2 + \dfrac{r_1 l_2 (1-r_2)}{1 - r_1 (1-l_2)}$↵

Now we can build a segment tree on the casinos, and use the above to merge segments.↵

Time Complexity: $O(N + QlogN)$↵

<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵


int n;↵
double pr[100000];↵
pair<double,double> seg[400000];↵
bool ze(double d){↵
return (abs(d) <= 0.0000000001);↵
}↵
pair<double,double> merge(pair<double,double> a, pair<double,double> b){↵
if(ze(a.first+1) && ze(a.second+1)) return b;↵
if(ze(b.first+1) && ze(b.second+1)) return a;↵
double l1 = a.first;↵
double r1 = a.second;↵
double l2 = b.first;↵
double r2 = b.second;↵
if(ze(((l2-1)*r1+1))) return make_pair(0,0);↵
double le = l1*l2/((l2-1)*r1+1);↵
double ri = r2+(r1*l2*(-r2+1))/(-r1*(-l2+1)+1);↵
return make_pair(le,ri);↵
}↵
void build(int no, int b, int e){↵
if(b==e){↵
seg[no] = make_pair(pr[b],pr[b]);↵
return;↵
}↵
int mid = (b+e)/2;↵
build(2*no,b,mid);↵
build(2*no+1,mid+1,e);↵
seg[no] = merge(seg[2*no],seg[2*no+1]);↵
}↵
void upd(int no, int b, int e, int i, double val){↵
if(i<b || i>e) return;↵
if(b==e){↵
seg[no] = make_pair(val,val);↵
return;↵
}↵
int mid = (b+e)/2;↵
upd(2*no,b,mid,i,val);↵
upd(2*no+1,mid+1,e,i,val);↵
seg[no] = merge(seg[2*no],seg[2*no+1]);↵
}↵
pair<double,double> query(int no, int b, int e, int l, int r){↵
if(b>r || e<l) return make_pair(-1,-1);↵
if(l<=b && e<=r) return seg[no];↵
int mid = (b+e)/2;↵
return merge(query(2*no,b,mid,l,r),query(2*no+1,mid+1,e,l,r));↵
}↵
int main(){↵
    int q;↵
scanf("%d %d", &n, &q);↵
for(int i=0; i < n; i++){↵
int a,b;↵
scanf("%d %d", &a, &b);↵
pr[i] = (double)a / (double)b;↵
}↵

build(1,0,n-1);↵
for(int que = 0; que < q; que++){↵
int ty;↵
int a;↵
int b;↵
scanf("%d %d %d", &ty, &a, &b);↵
if(ty==1){↵
int c;↵
scanf("%d", &c);↵
upd(1,0,n-1,a-1, (double)b / (double)c);↵
}↵
else{↵
    printf("%.20f\n", query(1,0,n-1,a-1,b-1).first);↵
}↵
}↵

return 0;↵
}↵


~~~~~↵


</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English send_nodes 2016-09-12 20:09:38 2 Tiny change: 're array $a$.\n\nTime' -> 're array $b$.\n\nTime'
en6 English send_nodes 2016-09-12 20:08:52 6 Tiny change: 'ote that $b[i]+b[i+1] = a[i]$. Use ' -> 'ote that $a[i]+a[i+1] = b[i]$. Use '
en5 English send_nodes 2016-09-11 19:42:28 1 Tiny change: '016-09-11]. We can c' -> '016-09-11]). We can c'
en4 English send_nodes 2016-09-11 19:42:00 38 Tiny change: ' functions. We can c' -> ' functions(thanks to [user:minimario]. We can c'
en3 English send_nodes 2016-09-11 00:34:55 2 (published)
en2 English send_nodes 2016-09-11 00:30:40 11305 (saved to drafts)
en1 English send_nodes 2016-09-10 23:31:27 178 Initial revision (published)