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

Автор manijuana, история, 4 года назад, По-английски

I'm facing a very weird problem and I don't quite understand it. The problem is of finding the number of distinct integers in an array of numbers specifically This CSES problem. Note that the limit of N is 2e5 Hence O(N) and O(NlogN) both solutions should pass. However the funny part is that my O(N) solution gets TLE in one of the subtasks and O(NlogN) gets AC. I'm really confused and would appreciate if someone could tell me what is going on. Thanks in advance.

My O(NlogN) solution: Inserting elements in a set int main(){ ll n; cin>>n;
set s;
ll x;
for(ll i=0;i<n;i++) {cin>>x; s.insert(vec[i]);}
cout<<s.size()<<endl;
return 0;
}

My O(N) solution: Insterting elements in an unordered_map
int main(){
ll n;
cin>>n;
ll cnt=0;
ll x;
unordered_map <ll,ll> umap;
for(ll i=0;i<n;i++) {
cin>>x;
if(!umap[x]){
umap[x]++;
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}

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

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

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

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

Read this blog

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I read it, made my own custom hash function and got an AC using unordered_map. Thanks a lot. This was a really informative blog post.

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Try to pass n into constructor of umap:

unordered_map <ll,ll> umap(n);

This will preallocate buckets and might solve the issue.

Edit1: If not, read the blog mentioned by Olerinskiy.

Edit2: Read the blog anyway :)

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The second solution is not O(N), because searching an element in an unordered_map can sometimes cost you O(N) (worst case). Although, on average searching an element takes O(1), there can be test cases where it fails and that might be the case in this problem...