Can anyone tell me, how can i use a DP array when most of the questions on codechef require 10^5 space and almost every intermediate DP question on codechef requires a 2D array(for tabular method).The size of the array will be a[10^5][10^5]=a[10^10].That much of memory is not allowed to allocate in codechef.
Please explain with example like 0/1 knapsack problem (bcz in tabular method it requires 2D array).
if you’re thinking of a 2D DP array of size 10^10, surely the way you are approaching the problem isn’t correct. Always see the constraints to find out what the time and memory complexity can be. You can be sure, the problem setter hasn’t made a mistake generating the constraints.
1 Like
A 2-D array approach, of that big size will time out even if codechef allows you to declare them. Knapsack has a 1-D table approach as well. As @sudip_95 said, if you need that much memory then your approach isnt correct/optimum.