Need Help in resolving TLE in DP with memo and iterative.

№	Пользователь	Рейтинг
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

№	Пользователь	Вклад
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

Why do some solutions containing dp with memoization result in TLE but the same iterative version always passes? I have had this doubt for quite a while.

For example this problem : https://mirror.codeforces.com/contest/628/problem/D

DP+Memo->TLE


#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+10;
const ll mod = 1e9+7;


int m,d;
string a,b;
int dp[2001][2][2001];

int solve(int pos,int f1,int rem,string x){
	if(pos==(int)a.length()){
		if((rem%m)==0)
			return 1;
		return 0;
	}
	if(dp[pos][f1][rem]!=-1)
		return dp[pos][f1][rem];
	int ulmt;
	if(f1)
		ulmt=9;
	else
		ulmt=(x[pos]-'0');
	int ans=0;
	for(int i=0;i<=ulmt;++i){
		int nf1,nrem,nis;
		if(f1==0 and i==ulmt)
			nf1=0;
		else if(f1==0 and i<ulmt)
			nf1=1;
		else
			nf1=1;

		nrem=(10*rem+i)%m;
		if(pos%2==1 and i==d){
			ans+=solve(pos+1,nf1,nrem,x);
			if(ans>=mod)
				ans-=mod;
			break;
		}
		else if(pos%2==0 and i!=d){
			ans+=solve(pos+1,nf1,nrem,x);
			if(ans>=mod)
				ans-=mod;
		}	
	}
	return dp[pos][f1][rem] = ans;
}

int main(){
	fast;
	cin >> m >> d >> a >> b;
	memset(dp,-1,sizeof(dp));
	int a1 = solve(0,0,0,b);
	memset(dp,-1,sizeof(dp));
	int a2 = solve(0,0,0,a);
	bool ok=true;
	int rem=0;
	for(int i=0;i<(int)a.length();++i){
		if(i%2==1 and (a[i]-'0')!=d){
			ok=false;
		}
		if(i%2==0 and (a[i]-'0')==d){
			ok=false;
		}
		rem=(10*rem+(a[i]-'0'))%m;
	}
	int ans;
	if(ok and rem==0)
		ans=(a1-a2+1+mod)%mod;
	else
		ans=(a1-a2+mod)%mod;
	cout<<ans<<"\n";
	
}

Checking the editorial they have done the same thing just iterative.

So my questions are this :

->What should be a good practice to write dp memoized or iterative?

->Can every memoized dp problem be converted to iterative ?

->What exactly goes wrong with memoized versions getting TLE'd ?

->How to resolve such TLE's ?

Thanks!

Комментарии (7)

Показать архивные | Написать комментарий?

parveen1981

4 года назад, # |

← Rev. 2 →

state of your dp is kind of $$$O(n^2)$$$ and for each state you are running a loop which is $$$O(n)$$$ and hence total time complexity would be $$$O(n^3)$$$ which will result in TLE. Editorial solution is $$$O(n^2)$$$. So you might optimize your recursive dp or it might not be possible to do so in recursive. Also using recursive/iterative depends on the problem and the observations you have made.

→ Ответить

Nachiket

You're passing string x by value, it creates a copy everytime

4 года назад, # ^ |

this is definitely it.

Codeforcer

Wow I thought it was ok to just pass strings and arrays like that..that definitely worked and also ended up a bit faster then the iterative version lol...thanks to you!

Lakshi4h

it's ok to pass arrays. it just sends the pointer

Also I read somewhere that the order in which matrices are multiplied matters a lot when accessing memory, so how to decide which dimensions to put first in dp ?

Usually, smaller dimensions should be kept first. Ref

Блог пользователя Codeforcer