Number_72's blog

By Number_72, history, 18 months ago, In English

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.

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

»
18 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

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

    Thank you so much! I tried but still got TLE but still very interesting anyways, will definitely use the custom_hash from now on.

»
18 months ago, # |
  Vote: I like it +7 Vote: I do not like it

The problem is that unordered_map is slow. 2e8*3 operations on umap cannot finish in 4 seconds.

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

    Thank you so much, is there anyway that I can optimise this brute force solution by changing the data structure?