### geckods's blog

By geckods, history, 6 weeks ago, ,

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];
}


• +20

 » 6 weeks ago, # |   +3 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, # |   +3 unordered_map? Try map instead.
•  » » 6 weeks ago, # ^ |   +8 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, # ^ |   +3 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, # ^ |   0 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, # ^ |   +8 Fixed it now. Thanks a lot!
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +8 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, # ^ |   +20 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, # |   0 Auto comment: topic has been updated by geckods (previous revision, new revision, compare).