-SHIV-'s blog

Please help in measuring the Time complexity of this DP problem

By -SHIV-, history, 5 weeks ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Its O((n+m)*(n)*2)

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 )

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Because on average (across all nodes) the loop is m/n, not just m. So you can ignore that part essentially.

          → Reply