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];
}
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.
unordered_map
? Trymap
instead.map
also TLEs. Also, my understanding is thatunordered_map
should be faster thanmap
in situations where ordering is not required? Is that incorrect?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.
I didn't catch that, thank you! I forgot that the size of my map was O(n^2) and not O(n).
Fixed it now. Thanks a lot!
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.
Also, not sure why my post is getting downvoted. Am I not supposed to ask questions like these on the CF blog?
Auto comment: topic has been updated by geckods (previous revision, new revision, compare).