Блог пользователя Raks_splunk

Автор Raks_splunk, история, 5 месяцев назад, По-английски

Was solving Matrix chain multiplication on GFG using memoization and got this weird error.

Code works fine when I use a 2D array to store the states, But Gives TLE when vectors are used. Is there any specific reason for this?

Accepted submission: https://pastebin.com/3ZdC61Vc

TLE submission: https://pastebin.com/VbdFrzDJ

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

It's because you have a recursive function where you are passing the vector into the recursive calls like this:

class Solution{
public:
    long long  mxm(int arr[],int i,int j,vector<vector<long long>>t){
        // snip...
        left=mxm(arr,i,k,t);
        // snip...
        right=mxm(arr,k+1,j,t);
        // more stuff...
    }

If you do it like this, the vector gets passed by value, i.e. copied for every function call (instead of passing the same vector object, it makes a new, identical one), unlike some other programming languages like Java. This can get pretty expensive. Worse yet, since you are using this vector for memoization, this means that the memoization actually has no effect. Lines like t[i][j]=mn; do nothing because they are only saved to the local copy, they are not seen by other calls to the mxm function.

See what happens when you instead declare the function like this, with an ampersand:

long long  mxm(int arr[],int i,int j,vector<vector<long long>> &t)

This makes it so that the vector is passed by reference, which is what you probably actually want.


Also, please consider not using GFG. It's an extremely poor-quality resource. The only thing they do well is the SEO that makes them sit at the top of Google results.

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Oh damn I forgot about passing it by reference. Thanks for pointing it out! Only used GFG Because as you said it, They are the first thing you see when you search for MCM.

    So I tried passing the 2D array without referencing it and declaring it in the main function, and it seem to pass the tests?

    Code: https://pastebin.com/mLEY3Ays

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is the time's differential between two submissions? Is it too distinctive?