Adnanboi's blog

Some help with DP optimization
By Adnanboi, history, 2 years ago, In English

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!

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

Comments Comments (10)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try passing your vector arguments to functions as references (i.e. like vector<vector<int>> &grid)

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

    Tried, still not enough, it did speed it up tho but not enough..

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

      Pass dp as references as well... You might need to read some C++ book/tutorial before trying to do some programming.

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

        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.

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

          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.

          → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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".

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

      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.net/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.

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

        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!

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

          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.net/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.

          → Reply