## 11654 - Arithmetic Subsequence

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### 11654 - Arithmetic Subsequence

Hi!
I solved this problem, but my runtime is very large(1.040 sec). I'm interesting in your solutions, what method do you use and what is the complexity of your algo? My algo is - O(n^3 logN).

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

### Re: 11654 - Arithmetic Subsequence

my run time complexity is N^3. its a pretty straight forward DP problem.

Chimed
New poster
Posts: 12
Joined: Mon Oct 20, 2008 10:37 am

### Re: 11654 - Arithmetic Subsequence

Igor9669 wrote:Hi!
I solved this problem, but my runtime is very large(1.040 sec). I'm interesting in your solutions, what method do you use and what is the complexity of your algo? My algo is - O(n^3 logN).
Same as yours got 0.364sec.

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11654 - Arithmetic Subsequence

Chimed wrote:Same as yours got 0.364sec.
Do you use stl in your solution?
Last edited by Igor9669 on Thu Aug 27, 2009 7:16 pm, edited 1 time in total.

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11654 - Arithmetic Subsequence

crip121 wrote:my run time complexity is N^3. its a pretty straight forward DP problem.
Could you explain it?

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

### Re: 11654 - Arithmetic Subsequence

Let a[j] = Number of arithmetic subset using number 1 to j and last two number is i'th and j'th.
O(N^3)

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: Hi14

What is this ?
Try to catch fish rather than asking for some fishes.