Hello Codeforces, today I was solving this problem:1822G1 - Magic Triples (Easy Version). I wrote a very simple brute force solution. here is my code:
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define inf 2e18
#define endl '\n'
#define int long long
#define F(xxx,yyy,zzz) for (int xxx=yyy;xxx<zzz;xxx++)
int MOD = 1000000007;
int mul(int x, int y){
return ((x % MOD) * (y % MOD)) % MOD;
}
int add(int x, int y){
return ((x%MOD)+(y%MOD))%MOD;
}
int exp(int x, int y){
int ans = 1;
while (y){
if (y % 2) ans = mul(ans, x);
x = mul(x, x);
y /= 2;
}
return ans;
}
int divide(int x, int y){
return mul(x, exp(y, MOD - 2));
}
using namespace std;
void solve(){
int n;
cin >> n;
int a[n+1];
for (int i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+n+1);
unordered_map<int,int> cnt;
for (int i=1;i<=n;i++) cnt[a[i]]++;
unordered_map<int,int> cnt2 = cnt;
int ans = 0;
for (int i=1;i<=n;i++) {
if (cnt[a[i]]) {
for (int b=2;a[i]*b*b<=a[n];b++) {
ans+= cnt[a[i]]*cnt[a[i]*b]*cnt[a[i]*b*b];
}
cnt[a[i]] = 0;
}
}
for (int i=1;i<=n;i++) {
ans+= max(0ll,(cnt2[a[i]])*(cnt2[a[i]]-1)*(cnt2[a[i]]-2));
cnt2[a[i]] = 0;
}
cout << ans << endl;
}
signed main()
{
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tc = 1;
cin >> tc;
while (tc--)solve();
}
I estimated that this algorithm would make at most 2e8 operations in total but it gets TLE on TC 14. N goes upto 2e5 and the elements of A go upto 1e6 so b would iterate upto at most 1e3. So I am a bit confused. I reckon it has something to do with the unordered map but I am not sure. I would be happy if someone pointed out the mistake.
This is because you assumed that
unordered_map
takes $$$1$$$ operation for accessing and inserting any element, which is not true. It depends on collisons that occur during these operations.In worst case it take $$$O(n)$$$ time to delete, insert and access any element.
But you can change the hash function used to decrease the number of collison. You can refer this blog for more details.
Thank you so much! I tried but still got TLE but still very interesting anyways, will definitely use the custom_hash from now on.
The problem is that unordered_map is slow. 2e8*3 operations on umap cannot finish in 4 seconds.
Thank you so much, is there anyway that I can optimise this brute force solution by changing the data structure?
Use an array instead. To clear the array just undo the updates.
Thank you!