Expert.
Put your skills to the test.

Problem summary

Two text shells initially contain correct prefixes of lengths L and R of a target of N distinct characters. Each keystroke goes to the left shell with probability P and to the right otherwise; its destination is observed. A character appends and Backspace deletes the last character if any. Never press Backspace when neither shell has a character that must eventually be deleted, and never type a character that is certainly wrong in both shells. Find the minimum expected additional keystrokes to finish both copies.

Constraints

0≤L,R≤N≤20000000; 0.1≤P≤0.9.

Worked example

Original statement sample.

0.3 2 0 1

16.7142857142857

Solution analysis

1. Put the longer correct prefix on the left: if L<R, swap lengths and replace P by 1-P. Write p=P and q=1-p. First advance the lagging right shell from R to L, then advance both equal prefixes from L to N.
2. Let C(i,t) be the repair-inclusive expected cost of adding a correct character to a lagging prefix of length i, when a keystroke reaches that shell with probability t. A failed attempt damages the leading shell. Repairing it can erase correct characters in the lagging shell, which must also be restored. The result is C(i,t)=2/t+2(1-t)i/t.
3. For a derivation put u=1-t and H(0)=0. The expected lost-prefix repair contribution satisfies H(i)=t*C(i-1,t)+t*H(i-1). After a failed character attempt, repairing the other shell costs F(i)=1/u+H(i). Geometric retries give C(i,t)=1/t+(u/t)*F(i). Induction gives the formula above, including wasted Backspaces sent to empty shells.
4. At equal length i, one correct keystroke advances one shell. Making both lengths i+1 then costs E(i)=1+p*C(i,q)+q*C(i,p). At unequal lengths advance the lagging prefix and repair erroneous suffixes before progressing further. Such suffixes must be deleted before their shell can progress; postponing repair cannot create an extra useful character.
5. Sum C(i,q) over R≤i<L and E(i) over L≤i<N. Both are linear in i. With M=N-L and D=L-R, arithmetic-series identities give M*(1+2p/q+2q/p)+M*(N+L-1)*(p²/q+q²/p)+2D/q+D*(L+R-1)*p/q.
6. For the sample, normalization gives p=0.7,L=1,R=0. Catching up costs C(0,0.3)=6.6666666666667. Finishing from equal length 1 costs E(1)=10.0476190476190. The sum is 16.7142857142857. Already completed shells give zero.

Why it works

The repair recurrence conditions on observed destinations and counts every erroneous character and erased correct prefix. Geometric retries give the cost to advance a lagging prefix. Equal-prefix states need one useful character followed by that lagging state. Summing successive states and evaluating the arithmetic progressions gives the stated expectation.

Watch out. Swap probabilities when swapping lengths. Backspaces reaching empty shells still count. Convert to long double before products. The answer is an expectation, not the cost of one particular sequence.

An independently written complete program with standard headers.

#include<algorithm>
#include<iomanip>
#include<iostream>
using namespace std;
int main(){
    long double probability;
    int length;
    int left;
    int right;
    cin>>probability>>length>>left>>right;
    if(left<right){
        swap(left,right);
        probability=1-probability;
    }
    long double p=probability;
    long double q=1-p;
    long double remaining=length-left;
    long double difference=left-right;
    // Costs of advancing equally long prefixes.
    long double answer=remaining*(1+2*p/q+2*q/p);
    answer+=remaining*(length+static_cast<long double>(left)-1)*(p*p/q+q*q/p);
    // First bring the shorter prefix up to the longer one.
    answer+=difference*2/q;
    answer+=difference*(left+static_cast<long double>(right)-1)*p/q;
    cout<<fixed<<setprecision(13)<<answer<<'\n';
}