Challenge: Count Triangles
Scor cont: 140.0 / 200
Submission status: Terminated due to timeout
Submission score: 0.7
Submission ID: 464904921
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/count-triangles/problem
Cerinta
You are given a regular N-gon with vertices at (cos(2πi / N), sin(2πi / N)), ∀ i ∈ [0,N-1]. Some of these vertices are blocked and all others are unblocked. We consider triangles with vertices at the vertices of N-gon and with at least one vertex at unblocked point. Can you find how many *pairs* of such triangles have equal area?
**Input Format**
The first line of input contains single integer T - number of testcases. 2T lines follow.
Each testcase has two lines.
The first line of testcase contains a single integer N - the number of vertices in N-gon. The second line contains string S with length N. If S[j] equals '1' it means that the vertex (cos(2πj / N), sin(2πj / N)) is unblocked, and if S[j] equals '0' it means that the vertex (cos(2πj / N), sin(2πj / N)) is blocked.
**Output Format**
For each testcase output single line with an answer.
**Constraints**
1 <= T <= 100
3 <= N <= 10<sup>4</sup>
There will be no more than 50 blocked vertices in each of the testcase.
**Sample Input**
1
4
1111
**Sample Output**
6
**Explanation**
The testcase given is a square and there are 4 triangles that have the same area. So, the number of pairs are 4C2 = 6.Cod sursa
#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using u32 = uint32_t;
using i64 = long long;
using u128 = unsigned __int128;
using i128 = __int128;
u64 mpow(u64 a,u64 e,u64 m){u64 r=1;a%=m;while(e){if(e&1)r=(u128)r*a%m;a=(u128)a*a%m;e>>=1;}return r;}
bool isp(u64 n){
if(n<2)return 0;if(n<4)return 1;if(n%2==0||n%3==0)return 0;
u64 d=n-1;int s=0;while(!(d&1)){d>>=1;s++;}
for(u64 a:{2,3,5,7,11,13,17,19,23,29,31,37}){
if(a>=n)continue;u64 x=mpow(a,d,n);if(x==1||x==n-1)continue;
bool c=1;for(int r=1;r<s;r++){x=(u128)x*x%n;if(x==n-1){c=0;break;}}
if(c)return 0;
}return 1;
}
u64 findp(u64 m,u64 lo){u64 k=(lo+m-1)/m;while(!isp(k*m+1))k++;return k*m+1;}
u64 proot(u64 p){
u64 phi=p-1,n=phi;vector<u64>fs;
for(u64 i=2;i*i<=n;i++){if(n%i==0){fs.push_back(i);while(n%i==0)n/=i;}}
if(n>1)fs.push_back(n);
for(u64 g=2;;g++){bool ok=1;for(u64 f:fs)if(mpow(g,phi/f,p)==1){ok=0;break;}if(ok)return g;}
}
static const int MAX_TRI = 8'400'000;
static u32 K[MAX_TRI], K2[MAX_TRI]; // primary key h1
static u32 P[MAX_TRI], P2[MAX_TRI]; // payload: (h2<<2)|mtype
static u64 S1[10001], S2[10001];
static u64 V1[10001], V2[10001];
struct TestBad {
vector<pair<u64,int>> bad; // (combined key, bad count)
};
static inline void radix_sort_u32_pair(u32* k, u32* p, u32* kbuf, u32* pbuf, int n){
static int cnt[65536];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++) cnt[k[i] & 0xFFFF]++;
int sum=0;
for(int i=0;i<65536;i++){int c=cnt[i]; cnt[i]=sum; sum+=c;}
for(int i=0;i<n;i++){
int b = k[i] & 0xFFFF;
int pos = cnt[b]++;
kbuf[pos]=k[i]; pbuf[pos]=p[i];
}
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++) cnt[kbuf[i] >> 16]++;
sum=0;
for(int i=0;i<65536;i++){int c=cnt[i]; cnt[i]=sum; sum+=c;}
for(int i=0;i<n;i++){
int b = kbuf[i] >> 16;
int pos = cnt[b]++;
k[pos]=kbuf[i]; p[pos]=pbuf[i];
}
}
static inline void print128(i128 x){
if(x==0){ putchar('0'); return; }
if(x<0){ putchar('-'); x=-x; }
char buf[50]; int n=0;
while(x>0){ buf[n++] = char('0' + (int)(x%10)); x/=10; }
while(n--) putchar(buf[n]);
}
int main(){
int T; if(scanf("%d",&T)!=1) return 0;
struct TC{ int N; char S[10001]; };
vector<TC> tc(T);
for(int i=0;i<T;i++) if(scanf("%d%s",&tc[i].N,tc[i].S)!=2) return 0;
map<int, vector<int>> byN;
for(int i=0;i<T;i++) byN[tc[i].N].push_back(i);
vector<i128> ans(T);
for(auto &itN : byN){
int N = itN.first;
auto &ids = itN.second;
u64 m = 2ULL * N;
u64 p1 = findp(m, 500000000ULL);
u64 p2 = findp(m, p1 + m);
auto buildS = [&](u64 p, u64* S){
u64 g=proot(p), w=mpow(g,(p-1)/m,p), wi=mpow(w,p-2,p);
u64 wp=1, wn=1;
for(int k=0;k<=N;k++){
S[k]=(wp + p - wn) % p;
if(k<N){ wp=(u128)wp*w%p; wn=(u128)wn*wi%p; }
}
};
buildS(p1,S1);
buildS(p2,S2);
for(int k=1;k<N;k++){
int dk=2*k;
V1[k] = (dk<=N)? S1[dk] : (p1 - S1[dk-N]) % p1;
V2[k] = (dk<=N)? S2[dk] : (p2 - S2[dk-N]) % p2;
}
vector<TestBad> badByTest(ids.size());
unordered_map<u64, i64> needFull; // key -> full count (filled later), init -1
needFull.reserve((size_t)ids.size()*1000 + 1024);
// precompute blocked key counts per test and union key set
for(size_t ti=0; ti<ids.size(); ++ti){
int idx = ids[ti];
char* S = tc[idx].S;
int blk[51], B=0;
for(int i=0;i<N;i++) if(S[i]=='0') blk[B++]=i;
if(B<3) continue;
vector<u64> tmp; tmp.reserve((size_t)B*(B-1)*(B-2)/6);
for(int i=0;i<B;i++) for(int j=i+1;j<B;j++){
int g1 = blk[j]-blk[i];
for(int k=j+1;k<B;k++){
int g2=blk[k]-blk[j], g3=N-blk[k]+blk[i];
int a=g1,b=g2,c=g3;
if(a>b) swap(a,b); if(b>c) swap(b,c); if(a>b) swap(a,b);
u64 h1 = V1[a] + V1[b]; if(h1>=p1) h1-=p1; h1 += V1[c]; if(h1>=p1) h1-=p1;
u64 h2 = V2[a] + V2[b]; if(h2>=p2) h2-=p2; h2 += V2[c]; if(h2>=p2) h2-=p2;
u64 key = (h1<<30) | h2;
tmp.push_back(key);
}
}
sort(tmp.begin(), tmp.end());
vector<pair<u64,int>> comp;
for(size_t i=0;i<tmp.size();){
size_t j=i+1; while(j<tmp.size() && tmp[j]==tmp[i]) ++j;
comp.push_back({tmp[i], (int)(j-i)});
if(!needFull.count(tmp[i])) needFull.emplace(tmp[i], -1);
i=j;
}
badByTest[ti].bad.swap(comp);
}
vector<u32> needPrimary;
needPrimary.reserve(needFull.size());
for(auto &kv: needFull){ needPrimary.push_back((u32)(kv.first >> 30)); }
sort(needPrimary.begin(), needPrimary.end());
needPrimary.erase(unique(needPrimary.begin(), needPrimary.end()), needPrimary.end());
// generate partitions
int nt=0;
for(int a=1;a<=N/3;a++){
u64 va1=V1[a], va2=V2[a];
int bmax=(N-a)/2;
for(int b=a;b<=bmax;b++){
int c=N-a-b;
int mtype = (a==b && b==c)?0:((a==b || b==c)?1:2);
u64 h1=va1+V1[b]; if(h1>=p1) h1-=p1; h1 += V1[c]; if(h1>=p1) h1-=p1;
u64 h2=va2+V2[b]; if(h2>=p2) h2-=p2; h2 += V2[c]; if(h2>=p2) h2-=p2;
K[nt]=(u32)h1;
P[nt]=(u32)((h2<<2) | (u32)mtype);
++nt;
}
}
radix_sort_u32_pair(K,P,K2,P2,nt);
const i64 mult[3] = {N/3, N, 2LL*N};
i128 bp=0;
size_t qptr=0;
auto needThisPrimary = [&](u32 pri)->bool{
while(qptr < needPrimary.size() && needPrimary[qptr] < pri) ++qptr;
return qptr < needPrimary.size() && needPrimary[qptr] == pri;
};
// scan by primary runs; exact group by secondary inside run
for(int i=0;i<nt;){
u32 pri = K[i];
int j=i+1; while(j<nt && K[j]==pri) ++j;
bool needPri = needThisPrimary(pri);
if(j==i+1){
u32 sec = P[i]>>2;
i64 total = mult[P[i]&3U];
bp += (i128)total*(total-1)/2;
if(needPri){
u64 key = ((u64)pri<<30) | sec;
auto it = needFull.find(key);
if(it != needFull.end()) it->second = total;
}
} else {
// local grouping by secondary (run is usually tiny)
static u32 secs[256];
static i64 sums[256];
int cnt=0;
bool fallback=false;
for(int t=i;t<j;t++){
u32 sec = P[t]>>2;
i64 val = mult[P[t]&3U];
int pos=-1;
for(int z=0; z<cnt; z++){ if(secs[z]==sec){ pos=z; break; } }
if(pos==-1){
if(cnt<256){ secs[cnt]=sec; sums[cnt]=val; cnt++; }
else { fallback=true; break; }
} else sums[pos]+=val;
}
if(!fallback){
for(int z=0; z<cnt; z++){
i64 total=sums[z];
bp += (i128)total*(total-1)/2;
if(needPri){
u64 key=((u64)pri<<30)|secs[z];
auto it=needFull.find(key);
if(it!=needFull.end()) it->second=total;
}
}
} else {
// very rare fallback
unordered_map<u32,i64> mp;
mp.reserve((j-i)*2);
for(int t=i;t<j;t++) mp[P[t]>>2] += mult[P[t]&3U];
for(auto &kv: mp){
i64 total=kv.second;
bp += (i128)total*(total-1)/2;
if(needPri){
u64 key=((u64)pri<<30)|kv.first;
auto it=needFull.find(key);
if(it!=needFull.end()) it->second=total;
}
}
}
}
i=j;
}
// answer per test
for(size_t ti=0; ti<ids.size(); ++ti){
i128 res=bp;
for(auto &bk: badByTest[ti].bad){
u64 k=bk.first; i64 bad=bk.second;
auto itf = needFull.find(k);
i64 full = (itf==needFull.end() || itf->second<0) ? 0 : itf->second;
res -= (i128)bad*(full-bad) + (i128)bad*(bad-1)/2;
}
ans[ids[ti]] = res;
}
}
for(int i=0;i<T;i++){ print128(ans[i]); putchar('\n'); }
return 0;
}
HackerRank Geometry – Count Triangles