I have a problem about measuring the Time Complexity of the Problem
according to me, it should be O(n^3), n^2 due to dp and O(N) due to transitions , so in total O(N^3)
Constraints:
2≤N≤2000
1≤M≤2000
1≤K≤2000
int dp[2][2001][2001];
int fun( vector g[],int node,int dis,int cnt){
if( dis == k+1 ){
if( cnt%2 || node != t ) return 0;
return 1;
}
if( dp[cnt][node][dis] != -1 )return dp[cnt][node][dis];
int ans = 0;
for(auto child: g[node]){
int n_cnt = cnt;
if( child == x ) n_cnt^=1;
ans = (ans%M+fun(g,child,dis+1,n_cnt)%M)%M;
}
return dp[cnt][node][dis]=ans;}
It is Atcoder's King Bombee problem! Link: https://atcoder.jp/contests/abc244/tasks/abc244_e
Its O((n+m)*(n)*2)
I understand that dp[2][2001[2001] causes 2*2001*2001
but also there is loop inside which can run upto O(N)
so isn't it should be O( N * 2 * 2001 * 2001 )
Good question, but no. Each edge only counts for two of the nodes. For this to introduce an additional factor of n, every node would need to have every edge. This isn’t the case because across all nodes, the sum of their degrees is bounded by 2*m, instead of just n^2.
So intuitively the bound is something like “for every edge, you look across it 2*2000 times in each direction at worst”.
Thank you for replying,
Can you Please elaborate, I am still in confusion that it should be
2*2001*2001*2001, cnt*node*dis*loop
Because on average (across all nodes) the loop is m/n, not just m. So you can ignore that part essentially.