shanto_bangladesh's blog

TLE with unordered_map
By shanto_bangladesh, history, 3 years ago, In English

In last Div. 4 contest, my solution for problem Problem F received TLE verdict in testcase 18 during the system test. Later on I found that, changing unordered_map to map works fine to achieve Accepted verdict.

Code: 

void solve()
{   
 
int n, k; cin >> n >> k ; 
vi g; 
unordered_map<int, int> m; 
for(int i = 0; i<n; i++)
{
  int a; cin >> a; 
  m[a]++; 
}
 
for(auto &x: m)
{
  if(x.second>=k) 
  {
      g.pb(x.first); 
  }
}
 
if(g.size()==0) { cout << -1 << "\n"; return; }
 
 
Asort(g); 
 
int l = 0, r = -1, cl = g[0]; 
  n = g.size(); 
  for(int i = 1; i<n; i++)
  {
      if(g[i] - g[i-1]>1)
      {
        if(r - l <= g[i-1] - cl)
        {
          r = g[i-1]; 
          l = cl; 
        }
 
        cl = g[i]; 
      }
  }
 
 if(g[n-1] - cl >= r - l )
    {
      r = g[n-1]; l = cl; 
    }
 
    cout << l << " " << r << '\n'; 
 
}

So far I know, when we do not need the elements to be ordered, we should use unordered_map which is the case in this problem. So why std::map works better than std::unordered_map in terms of time complexity?

Thanks for your patience!

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

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

read this blog ,it explains unordered_map complexity and how to improve its used hashing.

→ Reply
»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

F.

Marinush

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Actually, unordered_map gives us an amortized constant time insertion and look-up. Notice that I've highlighted the term 'amortized'. It means that it doesn't always take O(1) to insert and look elements up, it's just that in the vast majority of the cases this is so; that means that there are cases — although very rare — when it doesn't take O(1) to look-up. In such cases, it can actually take upto O(n) to look elements up.

map, on the other hand, gives us a worst case time-complexity of O(log n) in any possible case.

So, what seems to have happened is that you've hit the extremely rare case when unordered_map takes something like O(n).

Hope this answers your query.

:)

→ Reply