9
Finding number of arithmetic progressions of length 3 in array.
source link: http://codeforces.com/blog/entry/105891
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Finding number of arithmetic progressions of length 3 in array.
Hey, I've been trying to solve the following problem. Given an array of n≤2∗105n≤2∗105 distinct positive integers a1,a2,…,ana1,a2,…,an find the number of triplets (ii, jj, kk) and i<j<ki<j<k such that aj−ai=ak−ajaj−ai=ak−aj (so aiai, ajaj, akak form an arithmetic progression). Additionally, the test cases were made such that the answer is not greater than 106106.
I could only come up with a O(n2)O(n2) solution and have no idea how to go further (maybe some FFT/Convolutions?). Any hints/help would be appreciated, thanks in advance!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK