ErenZ's blog

By ErenZ, history, 5 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

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

»
5 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).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    find fuction causes tle in this case ,instead of (mp.find(a) != mp.end()) use (mp[a]>0) and also change else statement like this mp[x-a]=i+1 , so that after all mp[a] will be 0 if value is not inserted,and it will easily checked in program.

    btw, map uses tree structure to find a element while unordered map search element by visiting every element in it .

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

Complexity for ordered map is always O(log(N)) for accessing values..but in unordered map we cant say anything..at worst case even it can go upto O(N)..so generally i prefer to use ordered map to avoid such TLE's

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for replying, Is there some article that explains how this complexity of the unordered_map works? I thought it was always O(1).

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in ordered map elements are stored in increasing order ..so when you try to access elements you can think similar of binary search so O(log(N)) ..but in unordered map elements are in random order (can even differ from order of insertion) so when accessing elements you can think of linear search so O(N) at worst case...my POV

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks this was very helpful and i learned about hashing

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

me (!)