StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POEfficient way to find the number of all such triplets (from a given set of numbers) whose numbers are in A.P.?
text
Body
copied!<blockquote> <p><strong>Possible Duplicate:</strong><br> <a href="https://stackoverflow.com/questions/13240330/fastest-algorithm-count-number-of-3-length-ap-in-array">fastest algorithm count number of 3 length AP in array</a> </p> </blockquote> <p>I've been working on the following problem taken from CodeChef's Nov12 challenge. I tried it using the basic formula for checking whether three numbers a, b, c are in A.P., they are if c-b=b-a i.e. 2b=a+c. Here is the problem:</p> <p>First line of the input contains an integer N (3 ≤ N ≤ 100000). Then the following line contains N space separated integers A1, A2, …, AN and they have values between 1 and 30000 (inclusive).</p> <p>Output the number of ways to choose a triplet such that they are three consecutive terms of an arithmetic progression. Example</p> <p>Input:</p> <p>10</p> <p>3 5 3 6 3 4 10 4 5 2</p> <p>Output: 9</p> <p>Explanation: </p> <p>The followings are all 9 ways to choose a triplet</p> <p>1 : (i, j, k) = (1, 3, 5), (Ai, Aj, Ak) = (3, 3, 3)</p> <p>2 : (i, j, k) = (1, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)</p> <p>3 : (i, j, k) = (1, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)</p> <p>4 : (i, j, k) = (3, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)</p> <p>5 : (i, j, k) = (3, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)</p> <p>6 : (i, j, k) = (4, 6, 10), (Ai, Aj, Ak) = (6, 4, 2)</p> <p>7 : (i, j, k) = (4, 8, 10), (Ai, Aj, Ak) = (6, 4, 2)</p> <p>8 : (i, j, k) = (5, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)</p> <p>The code I used is</p> <pre><code>#include<stdio.h> int scan() { int p=0; char c; c=getchar_unlocked(); while(c<'0' || c>'9') c=getchar_unlocked(); while(c>='0' && c<='9'){ p=(p<<3)+(p<<1)+c-'0'; c=getchar_unlocked(); } return(p); } int main() { int N, i, j, k, count=0; N=scan(); int a[N]; for(i=0;i<N;i++) a[i]=scan(); for(i=0;i<N-2;i++) for(j=i+1;j<N-1;j++) for(k=j+1;k<N;k++) if(a[k]+a[i]==2*a[j]) ++count; printf("%d\n", count); return 0; } </code></pre> <p>As you can see the constraints on variables, it is clear that we need fast and efficient algo. For the sake of safety I even used faster I/O but still the program runs out of time. It is clear that the algorithm is not that efficient, as I am using three nested loops. One other way that come to reduce the number of some k's is to break the k' loop as soon as a match is found, then I would have added a continue; below ++count and that is working but again NOT that efficient as the problem requires.</p> <p>Please tell me some fast algo to do this, or if I might learn some mathematical theorem here to find AP triplets quicker.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload