Garavitey's blog

why the map work and vector doesn't? [question]
By Garavitey, history, 12 months ago, In English

I was trying this question

and for some reason that i dont understand my code doesn't work that is following.

int rec(int n, vector<int>&v){
    if(n == 0){
        return 1;
    }
    
    if(v[n] != -1){
        return v[n];
    }
    return v[n] = rec(floor(n/2),v) + rec(floor(n/3),v);
}

void solve() {
    read(n);
    vector<int>v(n+1,-1);
    cout<<rec(n,v)<<endl;
  
}

but the following code which has the same logic works. 

map<ll, ll> mp;
ll calc(ll x) {
    if (x == 0)return 1;
    if (mp.find(x) != mp.end())return mp[x];
    ll res = calc(x / 2) + calc(x / 3);
    return mp[x] = res;
}
void solve() {
    ll n; cin >> n;
    cout << calc(n) << "\n";
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ErenZ (previous revision, new revision, compare).

→ Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

floor(x/2) and x/2 do not always give the same output see this

→ Reply
»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Highest value of n is 1e18.A vector with this size will exceed memory limit. If you use map it will only store required states.In every step n will reduce to either n/2 or n/3 so there will be states of order log2(n) and log3(n) which will be within memory limit

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As stated in the problem statement, the maximum possible value of $$$n$$$ here is $$$10^{18}$$$. The constructor for a vector immediately allocates memory for its storage. Here, the vector will try to allocate space to store $$$f(x)$$$ for all $$$x$$$ from $$$0$$$ to $$$n$$$, even if the vast majority of these spaces are not actually used. Therefore, by creating a vector with size $$$n+1$$$ with the line vector<int>v(n+1,-1);, a 'memory limit exceeded' verdict or a runtime error may be caused.

On the other hand, a map only allocates storage for a particular index when it is used. Since not every value of $$$f(x)$$$ for $$$x$$$ from $$$0$$$ to $$$n$$$ is used, the map only stores the results relevant to computing the final result, which takes much less memory and will work for this problem.

Hope the above explanation helps!

→ Reply