By Adnanboi, history, 7 weeks ago,

Hey guys, I've recently been practicing dp and I tried this one problem I really liked, I tried a DP approach on it and it worked but for some reason I still got a TLE, is my memoization a problem? This is my submission btw: 161894502, if someone could please look into my code that'd be great, thank you!

• +6

 » 7 weeks ago, # |   0 Try passing your vector arguments to functions as references (i.e. like vector> &grid)
•  » » 7 weeks ago, # ^ |   0 Tried, still not enough, it did speed it up tho but not enough..
•  » » » 7 weeks ago, # ^ |   0 Pass dp as references as well... You might need to read some C++ book/tutorial before trying to do some programming.
•  » » » » 7 weeks ago, # ^ |   0 Alright, thank you! Do you have any other suggestions? The only one I'm reading right now is the "Competitive Programmers Handbook" as of right now.
•  » » » » » 7 weeks ago, # ^ |   0 No, I really mean C++ book, not competitive programming something. Since you don't know about copying, I guess you don't know many other details in C++ as well. Most of the time, you will suffer from those details while debugging rather than the algorithmic part.
 » 7 weeks ago, # |   0 Can you explain what your trying to do with this code? It doesn't look like DP to me... I will write up some code quickly to see if i can do it.
•  » » 7 weeks ago, # ^ |   0 Basically I'm trying to find the maximum path from row n and column n to row 1 and column 1, if that value is less than 0 then there is no possible solution, same goes for minimum, from row n and column n to row 1 and column 1, trying to find the minimum possible bath, and if the minimum possible path is above 0 then again it's impossible to get 0 at row 1 and column 1, if it is below 0 and the max is above 0 then there MUST be a solution from ranges min<=0<=max, so you output "YES".
•  » » » 7 weeks ago, # ^ |   0 I know that that's the logic, however, the way that you calculate minimum and maximum using recursion is very unreadable and potentially very slow. Do you think you could explain how you do the things you described above? Because it seems like you are repeating many computations. btw this submission that i just wrote gets AC https://codeforces.com/contest/1695/submission/162150217In this code I compute minimum and maximum in O(n*m) time (using DP) then just check if 0 is in range of min and max.
•  » » » » 7 weeks ago, # ^ |   0 Thanks, the code is helpful, I can see what you did but I kinda wanted to solve the problem in a recursive way, so if you could either modify my code to work or send a correct solution that'd be great! Again, thank you so much!
•  » » » » » 6 weeks ago, # ^ |   0 Hello, sorry for taking so long to respond to you. I was busy for a while. Anyways, this is some working code for the recursive method: https://codeforces.com/contest/1695/submission/162247376The only thing that I have changed (and when I say the only thing, I mean THE ONLY THING) with your code is that I changed dp_min and dp_max to global variables so that you don't have to pass them into the functions solve_min() and solve_max(). It now gets AC. Lesson for the day, passing 2d vectors into functions is quite slow and potentially even reduces the time complexity of your code. Because if you think about it, time complexity of passing a 2d vector to a function is O(n*m) (the number of elements in it) and since you will call these functions n*m times, your time complexity becomes O((n*m)^2). I am not sure but I think this is true.
•  » » » » » » 6 weeks ago, # ^ |   0 Thank you a lot man! This really helped me out!