geckods's blog

By geckods, history, 4 years ago, In English

I wrote the following code for 1163C2 - Передача энергии (усложнённая версия). 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];
    }

Full text and comments »

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

By geckods, history, 5 years ago, In English

I've been trying to solve Problem A of yesterday's finals. My solution is very similar to Tourist's solution (~33:00). My code is here. It TLEs on test case 12, but I can't seem to figure out why, I'm pretty sure the complexity is NlogN. In all likelihood, it's down to some edge case/infinite loop. If somebody could help me figure out the issue, I'd be very grateful. Thanks in advance.

Full text and comments »

Tags icpc, wf
  • Vote: I like it
  • 0
  • Vote: I do not like it