Hey, I've been trying to solve the following problem. Given an array of $$$n \leq 2*10^5$$$ distinct positive integers $$$a_1, a_2, \dots, a_n$$$ find the number of triplets ($$$i$$$, $$$j$$$, $$$k$$$) and $$$i < j < k$$$ such that $$$a_j - a_i = a_k - a_j$$$ (so $$$a_i$$$, $$$a_j$$$, $$$a_k$$$ form an arithmetic progression). Additionally, the test cases were made such that the answer is not greater than $$$10^6$$$.
I could only come up with a $$$O(n^2)$$$ solution and have no idea how to go further (maybe some FFT/Convolutions?). Any hints/help would be appreciated, thanks in advance!
Why would you need FFT/convolutions? An $$$O(nlogn)$$$ solution is easy to think of & implement.
Sort the array first. Then enumerate through all $$$j$$$ s. Therefore the formula is transformed into $$$2\times a_j=a_i+a_k$$$. The left part is determined; the right can be solved using binary search.
How would you solve it with binary search? Also, remember that the order of given integers matters (for $$$1$$$, $$$2$$$, $$$3$$$ answer is $$$1$$$ while for $$$2$$$, $$$3$$$, $$$1$$$ answer is $$$0$$$).
https://codeforces.com/problemset/problem/452/F
Hash + segment tree
It's not the same problem as in my problem you need to find number of different triples, while in the problem you've posted you need to check whether there exists any triple.
I'm sorry I can't help you.:(
When the sequence is arranged, the difficulty of determining the existence is * 2700, and the difficulty of counting may be greater than 3000
You can find this problem on CodeChef. https://www.codechef.com/problems/COUNTARI
Excuse me, but I think this is a variant of 3SUM? If this is true, then there would be no easy way to reduce it to under $$$O(n^2)$$$ time. Can we know the range of the array's elements? It may give a hint on whether FFT works or not.
Yes, the only way to do it in O(nlogn) is using FFT, and that can be optimized a little more with blocks, like than we find the number of primes in the interval.
The input array $$$a_1, a_2, a_3, \dots, a_n$$$ is a permutation of $$$1, 2, \dots, n$$$ so all elements are distinct and $$$1 \leq a_i \leq n$$$.
Now I am thinking if this problem may be some usage of prefix sum + suffix sum + DP, but I am not very sure on how. Can anyone help me on this approach?
There is a general approach using Fourier analysis.
Consider trilinear functional
Let these functions be indicator functions $1_A$, $$$1_B$$$, $$$1_C$$$ for some sets $$$A,B$$$ and $$$C$$$ respectively. Then it's clear how to express the number of arithmetic progressions in $$$A\times B\times C$$$ from $$$AP(1_A,1_B,1_C)$$$.
Then apply Fourier transform to them
Substitute back
and do some algebra
From properties of characters, we know that $$$\mathbf{E}_x e^{kx} = [k=0]$$$ (Iverson bracket notation), hence