Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

so I was solving a standard dp problem but it got TLE using this form of the calc function

code

void solve(){
    string a,b;
    cin >> a >> b;
    vector<vector<int>>dp(N,vector<int>(N,-1));
    int n = sz(a), m = sz(b);
    function<int(int,int)>calc=[&](int i,int j)->int{
        if(i==n&&j==m)
            return 0;
        if(i>n||j>m)
            return INT_MAX;
        if(~dp[i][j])
            return dp[i][j];
        int op1 = calc(i,j+1)+1;
        int op2 = calc(i+1,j)+1;
        int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
        return dp[i][j] = min({op1,op2,op3});
    };
    cout << calc(0,0);
}

and it passed by defining the same function exactly outside the solve function like this.

code

vector<vector<int>>dp(N,vector<int>(N,-1));
int n,m;
string a,b;
int calc(int i,int j){
    if(i==n&&j==m)
        return 0;
    if(i>n||j>m)
        return INT_MAX;
    if(~dp[i][j])
        return dp[i][j];
    int op1 = calc(i,j+1)+1;
    int op2 = calc(i+1,j)+1;
    int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
    return dp[i][j] = min({op1,op2,op3});
}
void solve() {
    cin >> a >> b;
    n = sz(a), m = sz(b);
    cout << calc(0,0);
}

So I really don't understand the issue here

Full text and comments »

i3mr125's blog