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!
| # | User | Rating |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Try passing your vector arguments to functions as references (i.e. like
vector<vector<int>> &grid)Tried, still not enough, it did speed it up tho but not enough..
Pass dp as references as well... You might need to read some C++ book/tutorial before trying to do some programming.
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.
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.
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.
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".
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/162150217
In 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.
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!
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/162247376
The 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.