ErenZ's blog

By ErenZ, history, 4 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";
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By ErenZ, history, 4 months ago, In English

I was trying to the this question and during that, I used the following code.

void solve() {

    read(n); read(x);
    map<int,int>mp;
    for(int i = 0; i< n; i++){
        int a; cin>>a;
        if(mp.find(a) != mp.end()){
            int b = mp[a]+1;
            cout<<b<<" "<<i+1<<endl;
            return;
        }
        else{
            mp[x-a] = i;
        }
    }
    cout<<"IMPOSSIBLE"<<endl;


}

this did not give any tle error but when i used the following code

void solve() {

    read(n); read(x);
    unordered_map<int,int>mp;
    for(int i = 0; i< n; i++){
        int a; cin>>a;
        if(mp.find(a) != mp.end()){
            int b = mp[a]+1;
            cout<<b<<" "<<i+1<<endl;
            return;
        }
        else{
            mp[x-a] = i;
        }
    }
    cout<<"IMPOSSIBLE"<<endl;


}

it was giving tle in the test cases 23 and 24. now I know that both of them are the same except for the use of data structure, but the map should be slower than unordered_map but the opposite is true, why is this happening can anyone explain?

code of unordered_map

code for map

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it