Miraacle's blog

By Miraacle, history, 18 months ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it