Page 1 of 1

11654 - Arithmetic Subsequence

Posted: Wed Aug 26, 2009 6:43 pm
by Igor9669
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).

Re: 11654 - Arithmetic Subsequence

Posted: Thu Aug 27, 2009 1:38 pm
by crip121
my run time complexity is N^3. its a pretty straight forward DP problem.

Re: 11654 - Arithmetic Subsequence

Posted: Thu Aug 27, 2009 4:44 pm
by Chimed
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.

Re: 11654 - Arithmetic Subsequence

Posted: Thu Aug 27, 2009 7:12 pm
by Igor9669
Chimed wrote:Same as yours got 0.364sec.
Do you use stl in your solution?

Re: 11654 - Arithmetic Subsequence

Posted: Thu Aug 27, 2009 7:15 pm
by Igor9669
crip121 wrote:my run time complexity is N^3. its a pretty straight forward DP problem.
Could you explain it?

Re: 11654 - Arithmetic Subsequence

Posted: Fri Aug 28, 2009 11:42 am
by Khongor_SMCS
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)

Re: Hi14

Posted: Sat Oct 17, 2009 3:37 pm
by arifcsecu