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

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

11654 - Arithmetic Subsequence

Post by Igor9669 » Wed Aug 26, 2009 6:43 pm

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

Post by crip121 » Thu Aug 27, 2009 1:38 pm

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

Post by Chimed » Thu Aug 27, 2009 4:44 pm

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

Post by Igor9669 » Thu Aug 27, 2009 7:12 pm

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

Post by Igor9669 » Thu Aug 27, 2009 7:15 pm

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

Post by Khongor_SMCS » Fri Aug 28, 2009 11:42 am

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

Post by arifcsecu » Sat Oct 17, 2009 3:37 pm

Try to catch fish rather than asking for some fishes.

Post Reply

Return to “Volume 116 (11600-11699)”