geckods's blog

By geckods, history, 6 weeks ago, In English,

I wrote the following code for 1163C2 - Power Transmission (Hard Edition). Despite having the same complexity as the editorialist's solution, the submission did not pass test case 10. I believe this is down to constant factor optimization, but I'm not sure exactly how to improve it. Can somebody help out? Thanks in advance.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pdd pair<ll,ll>
#define line pair<pair<ll,ll>,pair<ll,ll>>

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

    // template <class T1, class T2> 
    size_t operator()(const pair<ll, ll> p) const
    { 
        // auto hash1 = hash<T1>{}(p.first); 
        // auto hash2 = hash<T2>{}(p.second); 
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(p.first + FIXED_RANDOM) ^ splitmix64(p.second + FIXED_RANDOM); 
    } 

};

ll gcd(ll a, ll b) 
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

line lineFromPoints(pdd P, pdd Q) 
{ 
    ll a = Q.second - P.second; 
    ll b = P.first - Q.first; 
    ll c = a*(P.first) + b*(P.second);

    if(b==0){

        ll asdgcd=gcd(c,a);

        return {{LLONG_MAX,LLONG_MAX},{c/asdgcd,a/asdgcd}};
    }

    ll slopen=-a;
    ll sloped=b;
    ll interceptn=c;
    ll interceptd=b;

    ll slopegcd = gcd(slopen,sloped);
    ll interceptgcd = gcd(interceptn,interceptd);

    slopen/=slopegcd;
    sloped/=slopegcd;

    interceptn/=interceptgcd;
    interceptd/=interceptgcd;

    return {{slopen,sloped},{interceptn,interceptd}};
} 

int main(){
	
	#ifndef ONLINE_JUDGE
    	freopen("input", "r", stdin);
    	freopen("output", "w", stdout);
    	freopen("error", "w", stderr);
	#endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;

    //for each pair of points, compute slope and intercept. store in set, count set

    unordered_map<pair<ll,ll>,unordered_set<pair<ll,ll>,custom_hash >,custom_hash > mainMap;

    ll arr[n][2];
    for(int i=0;i<n;i++){
        cin>>arr[i][0]>>arr[i][1];
    }

    //compute the line between each pair of points, store in a map with key=slope
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            line myLine = lineFromPoints(make_pair(arr[i][0],arr[i][1]), make_pair(arr[j][0],arr[j][1]));
            mainMap[myLine.first].insert(myLine.second);
        }
    }

    //put number of lines with each slope in a vector 
    vector<ll> myVec;
    for(auto asd = mainMap.begin();asd!=mainMap.end();asd++){
        myVec.push_back((asd->second).size());
    }

    //answer = pairwise product of number of lines with each slope
    ll ans=0;
    for(int i=0;i<myVec.size();i++){
        for(int j=i+1;j<myVec.size();j++){
            ans+=myVec[i]*myVec[j];
        }
    }

    cout<<ans<<endl;

}

UPDATE: In case anybody was wondering, I got the time complexity of the last loop wrong. Works when the last loop is replaced by this.

    ll curr=0;
    ll ans=0;
    for(int i=0;i<myVec.size();i++){
        ans+=curr*myVec[i];
        curr+=myVec[i];
    }
 
 
 
 
  • Vote: I like it
  • +20
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I didn't read your code in detail. But I applied some standard constant factor optimizations to it. They didn't work though. If you analyzed the time complexity correctly, maybe you would want to try changing the Data Structure.

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

unordered_map? Try map instead.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    map also TLEs. Also, my understanding is that unordered_map should be faster than map in situations where ordering is not required? Is that incorrect?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That's just my own suggestion because it's easy to hack it. I didn't notice that you used your own hash.

      Actually your code works in $$$O(n^4)$$$. Look at the last loop.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't catch that, thank you! I forgot that the size of my map was O(n^2) and not O(n).

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Fixed it now. Thanks a lot!

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          Actually, your solution can be constant-optimized a bit. I halved the runtime of your AC-code by simply replacing the map and set with a single vector. See my submission here.

          Of course, if you want to bring it down the runtime further (by further constant optimization), I can. But we shall stop here as I think this already gives the most significant speedup.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        Also, not sure why my post is getting downvoted. Am I not supposed to ask questions like these on the CF blog?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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