Raks_splunk's blog

Vectors give TLE?

By Raks_splunk, history, 3 days ago, In English

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

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

»
2 days ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

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

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

→ Reply