G - Fine Triplets / Time Limit: 3 sec / Memory Lim...

We can solve this problem by “counting” each valid arithmetic progression in $S$. Recall that a triple $(A,B,C)$ (with $A<B<C$) is a fine triplet if and only if

$$B - A = C - B \quad \Longleftrightarrow \quad A + C = 2B.$$

One neat idea is to “fix” the middle element $B$ (which must lie in $S$) and then count how many pairs $(A,C)$ (with $A,C\in S$) satisfy

$$A + C = 2B.$$

Notice that if $(A,C)$ is a solution (with $A\ne C$) then automatically one of $A$ or $C$ is less than $B$ and the other is greater than $B$ (since if both were on one side the sum would be either too small or too large).

A standard observation is that if we define an indicator function

$$f(x)=\begin{cases}1 &\text{if }x\in S,\\0&\text{otherwise},\end{cases}$$

then for any integer $k$ the convolution

$$(f*f)(k)=\sum_{x+y=k} f(x)f(y)$$

counts the number of pairs $(x,y)$ with $x,y\in S$ and $x+y=k$.

Now, note that when $B\in S$ we have:

• One of the terms in the sum is when $x=y=B$ (since $B+B=2B$); however, $(B,B)$ is not allowed because we require the three numbers to be distinct (and $A<B<C$).
• All other pairs come in symmetric pairs: if $(A,C)$ is a solution with $A\neq C$ then both $(A,C)$ and $(C,A)$ appear in the sum.

Thus, if $B\in S$ then

$$(f*f)(2B)=1+2\cdot(\#\text{ of valid pairs }(A,C)\text{ with } A+C=2B).$$

In other words, the number of valid pairs (which give a fine triplet with middle $B$) is

$$\frac{(f*f)(2B)-1}{2}.$$

Thus the final answer is:

$$\text{ans}=\sum_{B\in S} \frac{(f*f)(2B)-1}{2}.$$

The challenge is to compute the convolution $f*f$ quickly. Since all $S_i$ are positive integers $\le 10^6$ and $N\le 10^6$, we can define an array of length (say) $m=10^6+1$ where

$$f(x)=1 \text{ if } x\in S,\quad 0 \text{ otherwise.}$$

Then the convolution $f*f$ can be computed via Fast Fourier Transform (FFT) in $O(m\log m)$ time. (The resulting convolution will have length up to roughly $2\cdot10^6$.)

The code below implements the FFT (using the standard iterative method) and then computes the convolution. Finally, for each $B\in S$ we add

$$\frac{\text{round}((f*f)(2B))-1}{2}$$

to the answer. (We use llround to convert from the floating‐point result of the FFT back to an integer.)

Below is the full optimized C++ code:

---

cpp
#include <bits/stdc++.h>
using namespace std;
 
typedef complex<double> cd;
 
// Iterative FFT implementation.
void fft(vector<cd> & a, bool invert) {
    int n = 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 * M_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], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if(invert) {
        for (int i = 0; i < n; i++)
            a[i] /= n;
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N;
    cin >> N;
    vector<int> S(N);
    int maxVal = 0;
    for (int i = 0; i < N; i++){
        cin >> S[i];
        if(S[i] > maxVal)
            maxVal = S[i];
    }
    // Our f(x) array will be of size m = maxVal + 1.
    int m = maxVal + 1;
 
    // Build the indicator function f.
    vector<cd> poly(m, 0);
    for (int x : S) {
        poly[x] = 1;
    }
 
    // We need to compute the convolution f*f.
    // The required size is at least (2*m - 1).
    int n = 1;
    while(n < 2 * m - 1)
        n <<= 1;
    poly.resize(n);
 
    // Perform FFT on poly.
    fft(poly, false);
    for (int i = 0; i < n; i++){
        poly[i] *= poly[i];
    }
    fft(poly, true);
 
    // Now poly[k] (rounded) is equal to (f*f)(k).
    // For each B in S, the number of fine triplets with B as the middle is ((poly[2*B] - 1) / 2).
    long long ans = 0;
    for (int b : S) {
        int idx = 2 * b;
        if(idx < (int)poly.size()){
            long long convVal = (long long)llround(poly[idx].real());
            // Subtract the self-pair (b,b)
            convVal -= 1;
            convVal /= 2;
            if(convVal > 0)
                ans += convVal;
        }
    }
 
    cout << ans << "\n";
    return 0;
}

---

Explanation

1. Input Reading and Setup:

   • We read $N$ and the set $S$.
   • We determine the maximum value in $S$ (denoted as maxVal) and set the size $m = \texttt{maxVal}+1$.
   • We create an array poly (of type vector<cd>) such that poly[x] = 1 if $x \in S$ and 0 otherwise.

2. FFT Setup:

   • We resize the polynomial to length n, the next power of 2 at least $2*m - 1$.
   • We perform FFT on poly, square each value (this corresponds to convolution in the frequency domain) and then perform the inverse FFT to obtain the convolution $f*f$.

3. Counting the Fine Triplets:

   • For every $B\in S$ we consider index $2B$ in the convolution array. Since the pair $(B,B)$ is always present (and must be removed), we subtract 1 and then divide by 2.
   • We sum these counts for all $B\in S$ and print the answer.

This code is optimized to run under the given constraints and should pass all test cases.

Happy coding!