For question F. Equalize the Array, if I submit the code using unordered_map as follows, it will get TLE:
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg ni, mi, ti, ki, di, pi;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// ti
cin >> ti;
while (ti--) {
cin >> ni;
unordered_map<gg, gg> um;
for (gg i = 0; i < ni; ++i) {
cin >> mi;
um[mi]++;
}
vector<gg> v;
for (auto& [i, j] : um) {
v.push_back(j);
}
sort(begin(v), end(v));
gg ans = 0, n = v.size();
for (gg i = 0; i < n; ++i) {
if (i > 0 and v[i] == v[i - 1]) {
continue;
}
ans = max(ans, v[i] * (n - i));
}
cout << ni - ans << "\n";
}
return 0;
}
However, if I submit the code using map as follows, it will be accepted:
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg ni, mi, ti, ki, di, pi;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// ti
cin >> ti;
while (ti--) {
cin >> ni;
map<gg, gg> um;
for (gg i = 0; i < ni; ++i) {
cin >> mi;
um[mi]++;
}
vector<gg> v;
for (auto& [i, j] : um) {
v.push_back(j);
}
sort(begin(v), end(v));
gg ans = 0, n = v.size();
for (gg i = 0; i < n; ++i) {
if (i > 0 and v[i] == v[i - 1]) {
continue;
}
ans = max(ans, v[i] * (n - i));
}
cout << ni - ans << "\n";
}
return 0;
}
As you can see, there is only one difference between these two codes: one uses unordered_map, and another uses map. But the result is different. Why?
unordered map worst case complexity is more!!
https://codeforces.me/blog/entry/62393
thanks
unordered map worst case complexity is $$$O(n*n)$$$ whereas for map it's $$$O(logn)$$$. This is because unordered map is based on hashing where multiple numbers can be hashed to same value forming large chains giving worse case search complexity $$$O(n)$$$.