rum3r's blog

By rum3r, history, 5 weeks ago, In English

Can anyone tell me why I am getting TLE with this Top Down Recursive (Rectangle Cutting CSES) and also Runtime Error. Thought I have memoized the results. Is the time complexity still more than O(a^2*b + a*b^2). I know you may ask why top down. I am just trying to explore possible ways. Code--

int solve(vector<vector<int>> dp, int l, int b){
	if(l == b){
		return 0;
	}
	if(l==0 || b==0){
		return 0;
	}
	if(dp[l][b] != inf){
		return dp[l][b];
	}
	for(int k=1; k<l; ++k){
		dp[l][b] = min(dp[l][b], 1+solve(dp, k, b)+solve(dp, l-k, b));
	}
	for(int k=1; k<b; ++k){
		dp[l][b] = min(dp[l][b], 1+solve(dp, l, k)+solve(dp, l, b-k));
	}
	return dp[l][b];
}

PROBLEM [](https://cses.fi/problemset/task/1744/)

ANY HELP WOULD BE APPRECIATED!! PEACE!!

 
 
 
 
  • 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

Either pass DP array by reference or declare it globally. Every single time you call solve() a new copy of DP array is created resulting in tle.

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

First of all you should pass dp as reference, but even then I think you will end up with a TLE. $$$O(500^3)$$$ along with the overhead complexity of calling functions might not fit into time limit. When the time limit is tight you should always opt for bottom up rather than top down.

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

    Thanks! I know that bottom up approach is good for dp but I was just exploring. How to implement it using top down. Even though complexity is same as bottom up. But it was still getting TLE. You cleared my doubt:)

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

    Yes, Bro it gets TLE in two tc's