### Miraacle's blog

By Miraacle, history, 7 weeks ago,

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!

• +11

 » 7 weeks ago, # |   0 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.
•  » » 7 weeks ago, # ^ |   +10 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$).
 » 7 weeks ago, # | ← Rev. 2 →   0 https://codeforces.com/problemset/problem/452/FHash + segment tree
•  » » 7 weeks ago, # ^ |   0 But I guess this problem is different because array elements ai is not a permutation of numbers from 1 to n.
•  » » 7 weeks ago, # ^ |   0 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.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 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
 » 7 weeks ago, # |   +6 You can find this problem on CodeChef. https://www.codechef.com/problems/COUNTARI
•  » » 6 weeks ago, # ^ |   0 Thanks, didn't know about this problem! The problem is that values in that problem are up to $3*10^4$ while mine can be up to $10^5$. Maybe it will fit TL, but I'm wondering whether there is any way to use the fact that answer is not greater than $10^6$.
 » 7 weeks ago, # |   0 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.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 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.
•  » » 6 weeks ago, # ^ |   0 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$.
•  » » » 6 weeks ago, # ^ |   0 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?