Arithmetic Progressions

Problem code: COUNTARI

All Submissions

All submissions for this problem are available.

Given N integers A₁, A₂, …. A_N, Dexter wants to know how many ways he can choose three numbers such that they are three consecutive terms of an arithmetic progression.

Meaning that, how many triplets (i, j, k) are there such that 1 ≤ i < j < k ≤ N and A_j - A_i = A_k - A_j.

So the triplets (2, 5, 8), (10, 8, 6), (3, 3, 3) are valid as they are three consecutive terms of an arithmetic
progression. But the triplets (2, 5, 7), (10, 6, 8) are not.

Input

First line of the input contains an integer N (3 ≤ N ≤ 100000). Then the following line contains N space separated integers A₁, A₂, …, A_N and they have values between 1 and 30000 (inclusive).

Output

Output the number of ways to choose a triplet such that they are three consecutive terms of an arithmetic progression.

Example

Input:
10
3 5 3 6 3 4 10 4 5 2

Output:
9

Explanation

The followings are all 9 ways to choose a triplet

1 : (i, j, k) = (1, 3, 5), (A_i, A_j, A_k) = (3, 3, 3)
2 : (i, j, k) = (1, 6, 9), (A_i, A_j, A_k) = (3, 4, 5)
3 : (i, j, k) = (1, 8, 9), (A_i, A_j, A_k) = (3, 4, 5)
4 : (i, j, k) = (3, 6, 9), (A_i, A_j, A_k) = (3, 4, 5)
5 : (i, j, k) = (3, 8, 9), (A_i, A_j, A_k) = (3, 4, 5)
6 : (i, j, k) = (4, 6, 10), (A_i, A_j, A_k) = (6, 4, 2)
7 : (i, j, k) = (4, 8, 10), (A_i, A_j, A_k) = (6, 4, 2)
8 : (i, j, k) = (5, 6, 9), (A_i, A_j, A_k) = (3, 4, 5)
9 : (i, j, k) = (5, 8, 9), (A_i, A_j, A_k) = (3, 4, 5)

Author:	rustinpiece
Tester:	laycurse
Editorial	http://discuss.codechef.com/problems/COUNTARI
Date Added:	25-10-2012
Time Limit:	3 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL

Submit

Comments

Login or Register to post a comment.

there should be (Ai, Aj, Ak)

n0_id @ 1 Nov 2012 06:57 PM

there should be (Ai, Aj, Ak) in the third line.

I see the language options

bcurcio @ 1 Nov 2012 09:41 PM

I see the language options empty

can we get any rough estimate

dpraveen @ 2 Nov 2012 12:32 AM

can we get any rough estimate about how fast is Cube ?? . Could you please give your estimates in no of operations per second ??

@n0_id No, it should be (i,

hiroto_adm @ 2 Nov 2012 12:43 AM

@n0_id No, it should be (i, j, k).

It turns out the judge cases

hiroto_adm @ 2 Nov 2012 12:45 AM

It turns out the judge cases are a bit weak. And we had modified them. So the submit were permitted temporary. Now everyone can submit. And all submissions will be rejudged. Sorry for the inconvenience.

@dpraveen You can find the

hiroto_adm @ 2 Nov 2012 01:52 AM

@dpraveen You can find the information about Cube here http://www.spoj.pl/clusters/

Why is Python missing from

ninetynine @ 2 Nov 2012 11:05 AM

Why is Python missing from languages?

what about the number of test

sachinkadian @ 2 Nov 2012 11:14 AM

what about the number of test cases??

Small problem..big

abhinav321000 @ 2 Nov 2012 04:37 PM

Small problem..big solution...

@admins: why is the language

cyberax @ 3 Nov 2012 05:34 AM

@admins: why is the language list limited in such a way ?

No Python :-( , why?

Gaurav Rai @ 3 Nov 2012 09:53 AM

No Python :-( , why?

I think tests are still weak

mmaxio @ 3 Nov 2012 10:28 AM

I think tests are still weak and my solution shouldn't be AC.

why isn't scala in supported

fcuhcakki @ 3 Nov 2012 09:04 PM

why isn't scala in supported languages for this problem? Isn't scala supported at all in codechef?

can we use dynamic allocation

code_maniac14 @ 3 Nov 2012 09:25 PM

can we use dynamic allocation of memory in codechef?! i'm getting compilation error on doing so. The code works right on my compiler.

Getting runTime(other)

varun.singh @ 3 Nov 2012 11:43 PM

Getting runTime(other) error?Can somebody let me know the reason? I am using c# as language.

why are the cases for i,j,k

kunalgaurav18 @ 4 Nov 2012 03:29 AM

why are the cases for i,j,k {1,6,2}, {1,8,2} and many more such cases not taken here?? the total output for the given sample input is coming 25.

@kunalgaurav18 Because of the

anton_lunyov @ 4 Nov 2012 04:09 AM

@kunalgaurav18 Because of the condition i < j < k. Well, for me this condition ruins very beautiful solution. Currently to handle this condition I have very bad solution that pass the TL which were very surprisingly for me.

hey python not available or

akshayrb @ 4 Nov 2012 11:47 AM

hey python not available or what :?

I am having runtime errors!

deepai_dutta @ 4 Nov 2012 12:31 PM

I am having runtime errors!

i am having runtime error

pradeep_laxmi @ 4 Nov 2012 05:19 PM

i am having runtime error ,but when i execute it in my system i am not finding any such errors (i tried with many inputs)..

I too get runtime error.

noorflex @ 5 Nov 2012 07:14 PM

I too get runtime error.

@admin provide some strong

wadhwa94 @ 6 Nov 2012 03:27 AM

@admin provide some strong test case

working for thr given test

wadhwa94 @ 6 Nov 2012 04:15 AM

working for thr given test case but getting wrong answer?? some tricky case??

Why Python is not supported

vikrant1433 @ 6 Nov 2012 10:15 AM

Why Python is not supported here ?

What does time given in

saikrishna173 @ 6 Nov 2012 11:16 PM

What does time given in succesfull submission refer to? My code is running in 9seconds for worst case but still getting time limit exceeded.While best code runs in 10 seconds. Can anyone please explain what actual time they refer to when they say time limit 3 seconds

@saikrishna173 10 seconds

tornike4 @ 6 Nov 2012 11:29 PM

@saikrishna173 10 seconds mean sum of all time for all test cases . not for one test.

@anton_lunyov: I would be

mugurelionut @ 7 Nov 2012 05:38 PM

@anton_lunyov: I would be interested in knowing a smart solution to this problem, even for the case when the triplets don't need to be sorted according to their position in the sequence. Maybe you could post it as a comment to the problem's editorial after the end of the contest ? (at least the main ideas if the solution is too difficult to explain). My solution to the contest problem is also not something that I'm too proud of (it's filled with all sorts of optimizations, but the theoretical time complexity is not good :) )

Any generic suggestions from

gauravkiitk @ 9 Nov 2012 11:17 AM

Any generic suggestions from anybody to avoid run time error ?? Because when i run on my PC its alwyas working fine but after uploading here hell lot of problems..Same amount of time which i gave to write a code is spent in trying to run the code here..Always get run time error....

@admin:- is there only one

gauravkiitk @ 9 Nov 2012 11:23 AM

@admin:- is there only one test cases?? As in input no where mentioned..number of test cases...let me know asap

run time error is probably

harshv1991 @ 9 Nov 2012 03:47 PM

run time error is probably comming because of high memory allocation as only 50000 bytes memory is allowed.

@harshrv1991 The 50000 bytes

darthsitius @ 10 Nov 2012 12:10 AM

@harshrv1991 The 50000 bytes is the limit for the size of the source file uploaded, not the amount of memory that can be allocated.

@darth&harsh: My source file

gauravkiitk @ 10 Nov 2012 05:49 PM

@darth&harsh: My source file is just 2.76Kb

what should be output for

jaikamal @ 14 Nov 2012 12:39 PM

what should be output for input : 12 3 6 0 55 0 666 288 1500 4833 2306 3430 0

SUCCESSFUL SUBMISSIONS

Fetching successful submissions

CodeChef is a non-commercial competitive programming community

In order to report copyright violations of any kind, send in an email to copyright@codechef.com

CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Site Navigation