HackerRank Geometry – Isosceles Triangles

Challenge: Isosceles Triangles

Scor cont: 250.0 / 250

Submission status: Accepted

Submission score: 1.0

Submission ID: 464816213

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/isosceles-triangles/problem

Cerinta

[Sevenkplus](http://sevenkplus.com/) has a regular polygon. Each vertex of the polygon has a color, either white or black. Sevenkplus wants to count the number of isosceles triangles whose vertices are vertices of the regular polygon and have the same color.  

**Input Format**   
The first line contains an integer T. T testcases follow.   
For each test case, there is only one line, which consists of a 01-string with length >= 3. Number of vertices `n` of the regular polygon equals length of the string. The string represents color of vertices in clockwise order. `0` represents white and `1` represents black. 

**Output Format**  
For each test case, output one line in the format `Case #t: ans`, where `t` is the case number (starting from 1), and `ans` is the answer. 

**Constraints**  
Sum of all n in the input <= 10^6.  

**Sample Input**

	5
	001
	0001
	10001
	111010
	1101010

**Sample Output**

	Case 1: 0
	Case 2: 1
	Case 3: 1
	Case 4: 2
	Case 5: 3

**Explanation**

In case 5, indices of vertices of the three monochromatic isosceles triangles are (0,3,5), (1,3,5) and (2,4,6) (assuming indices start from 0). 

**Timelimits**  
Timelimits for this challenge is given [here](https://www.hackerrank.com/environment)

Cod sursa

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

using cd = complex<double>;
const double PI = acos(-1.0);

static void fft(vector<cd>& a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i + j];
                cd v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        for (cd& x : a) x /= n;
    }
}

static vector<long long> convolution01(const vector<int>& a, const vector<int>& b) {
    int need = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;

    vector<cd> fa(n), fb(n);
    for (int i = 0; i < (int)a.size(); i++) fa[i] = cd(a[i], 0);
    for (int i = 0; i < (int)b.size(); i++) fb[i] = cd(b[i], 0);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);

    vector<long long> res(need);
    for (int i = 0; i < need; i++) res[i] = llround(fa[i].real());
    return res;
}

static long long apexCount(const vector<int>& col) {
    int n = (int)col.size();
    vector<long long> conv = convolution01(col, col); // linear by index sum

    vector<long long> pairCnt(n, 0);

    auto diagCount = [&](int s) -> long long {
        if (n & 1) {
            // inverse of 2 modulo odd n
            int inv2 = (n + 1) / 2;
            int u = (int)((1LL * s * inv2) % n);
            return col[u];
        } else {
            if (s & 1) return 0;
            int u1 = (s / 2) % n;
            int u2 = (u1 + n / 2) % n;
            return col[u1] + col[u2];
        }
    };

    for (int s = 0; s < n; s++) {
        long long ordered = conv[s];
        if (s + n < (int)conv.size()) ordered += conv[s + n];
        long long diag = diagCount(s);
        pairCnt[s] = (ordered - diag) / 2;
    }

    long long apex = 0;
    for (int i = 0; i < n; i++) {
        if (!col[i]) continue;
        int s = (2LL * i) % n;
        apex += pairCnt[s];
    }
    return apex;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        string s;
        cin >> s;
        int n = (int)s.size();

        vector<int> black(n), white(n);
        for (int i = 0; i < n; i++) {
            black[i] = (s[i] == '1');
            white[i] = 1 - black[i];
        }

        long long apex = apexCount(black) + apexCount(white);

        long long equi = 0;
        if (n % 3 == 0) {
            int step = n / 3;
            for (int i = 0; i < step; i++) {
                if (s[i] == s[i + step] && s[i] == s[i + 2 * step]) equi++;
            }
        }

        long long ans = apex - 2 * equi;
        cout << "Case " << tc << ": " << ans << '\n';
    }
    return 0;
}