Author |
Topic: Numeric Sequences (Read 3798 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Re: Numeric Sequences
« Reply #25 on: Dec 3rd, 2003, 10:45pm » |
 Quote  Modify
|
on Dec 3rd, 2003, 10:55am, TenaliRaman wrote:| I had an algo on (2) but it was O(n) and that scared me and made me think that it is wrong but your last hint has put faith in me so i am putting it here. |
|
TenaliRaman Bravo  !
This kind of a greedy algorithm (that chooses the local maximums/minimums) gets it !
Quote:| You are incorrect here, printing takes O(n). |
|
You're right ! (Sorry, I didn't pay enough attention  ).
P.S. I'm thinking of a "follower", but still unable to find (an appropriate) one - if someone can come up with an idea...
|
|
 IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #26 on: Jan 7th, 2004, 1:38am » |
Quote Modify
|
After quite a long time (as you can see) I have a "follower":
You are given a sequence of numbers A = a1, a2, a3, ... an.
3) Devise an algorithm to find a sub-sequence S of A such that:
- the sum of elements in the sub-sequence is minimal.
- a1 and an are in the sub-sequence.
- the "distance" between any two consecutive elements in the sub-sequence is [le] 2.
Explaination: we are looking for a sub-sequence ai1, ai2, ... aik such that i1 = 1, ik = n and [forall]1[le]j<k (ij+1 - ij) [le] 2.
|
|
IP Logged |
|
|
|
DH
Newbie
Gender: 
Posts: 19
|
|
Re: Numeric Sequences
« Reply #27 on: Jan 16th, 2004, 7:16am » |
Quote Modify
|
on Jan 7th, 2004, 1:38am, Dudidu wrote:After quite a long time (as you can see) I have a "follower":
You are given a sequence of numbers A = a1, a2, a3, ... an.
3) Devise an algorithm to find a sub-sequence S of A such that:
- the sum of elements in the sub-sequence is minimal.
- a1 and an are in the sub-sequence.
- the "distance" between any two consecutive elements in the sub-sequence is [le] 2.
Explaination: we are looking for a sub-sequence ai1, ai2, ... aik such that i1 = 1, ik = n and [forall]1[le]j<k (ij+1 - ij) [le] 2. |
|
After a long time I finally have some spare time.
::
Assuming we have a solution for A1 A2 .... AN-2 and also for A1 A2 ... AN-1 we can compute the solution to our problem in O(1) time so the solution can be computed ( "from scratch" )in O(N) time using dynamic programming.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #28 on: Jan 18th, 2004, 12:42am » |
Quote Modify
|
on Jan 16th, 2004, 7:16am, DH wrote:| Assuming we have a solution for ... and also for ... we can compute the solution ... using dynamic programming. |
|
DH welcome again,
Your answer is in the right direction !
But can you please state what is/are the "base solution/s" and how do you calculate the next step (in the dynamic programming) ?
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Numeric Sequences
« Reply #29 on: Jan 18th, 2004, 2:39am » |
Quote Modify
|
on Jan 18th, 2004, 12:42am, Dudidu wrote:
DH welcome again,
Your answer is in the right direction !
But can you please state what is/are the "base solution/s" and how do you calculate the next step (in the dynamic programming) ? |
|
::
n -> number of numbers in the sequence
v -> the numbers
min[0]=v[0];
min[1]=v[0]+v[1];
link[1]=0;
for (i=2;i<n;i++)
{
if (min[i-1]<min[i-2])
{
min[i]=min[i-1]+v[i];
link[i]=i-1;
}
else
{
min[i]=min[i-2]+v[i];
link[i]=i-2;
}
}
using the link vector we can compute the solution
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Numeric Sequences
« Reply #30 on: Jan 18th, 2004, 2:47am » |
Quote Modify
|
on Jan 18th, 2004, 2:39am, DH wrote:Well done, DH  !
It's correct.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print