@pacific..
the approach needs a little bit of tuning...
for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur approach, u
will pick 9, 8, 7, 6 etc...
minimum jumps in reality is from 9 to 1 to 2.
On Jan 14, 8:19 pm, pacific pacific <pacific4...@gmail.com> wrote:
> At each location if the value is k ,
> find the largest value in the next k elements and jump there.
>
> This greedy approach works in 0(n^2) and i believe it works. If not can
> someone give me a counter example ?
>
>
>
>
>
>
>
> On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu <avi.du...@gmail.com> wrote:
> > @jammy Even I felt the same, but the greedy 'algo' u suggest is actually
> > IMHO not a greedy approach. You just take each arr[i] and jump *without
> > deciding a locally optimal policy* . SO, if u were to *see* arr[i] and
> > *decide* on the optimal policy I feel one would follow d same steps as in a
> > DP solution. Its only just that the implementation would be O(n^2). Just to
> > add, this is the greedy approach I feel:
>
> > greedy_min_steps[n]
> > for i = 0; i < n; i++:
> > for (j = 0; j < input[i]; j++)
> > greedy_min_steps[ i + j ] = min(greedy_min_step[ i + j ],
> > greedy_min_steps[ i ] + 1)
>
> > this is the greedy approach I build and I see this being exactly similar to
> > my DP approach. There are instances of greedy approach based algorithms
> > which have *optimized* DP counter parts. I feel this problem is one of them.
> > More ideas ?
>
> > Programmers should realize their critical importance and responsibility in
> > a world gone digital. They are in many ways similar to the priests and monks
> > of Europe's Dark Ages; they are the only ones with the training and insight
> > to read and interpret the "scripture" of this age.
>
> > On Sat, Jan 15, 2011 at 2:14 AM, Jammy <xujiayiy...@gmail.com> wrote:
>
> >> @Avi Greedy approach doesn't work since you can't ensure the choice is
> >> locally optimum. Consider 3,9,2,1,8,3. Using greedy alg. would give
> >> you 3,1,8,3 while otherwise DP would give you 3,9,3.
>
> >> On Jan 14, 6:11 am, Avi Dullu <avi.du...@gmail.com> wrote:
> >> > I guess u got confused with the comment I wrote, I have added 2 print
> >> > statements and now I guess it should be clear to you as to why the code
> >> is
> >> > O(n). The comment means that each element of the min_steps_dp will be
> >> > ACCESSED only ONCE over the execution of the entire program. Hence the
> >> outer
> >> > loop still remains O(n). The next_vacat variable if u notice is always
> >> > incremental, never reset to a previous value.
>
> >> > #include<stdio.h>
> >> > #include<stdlib.h>
>
> >> > #define MAX 0x7fffffff
>
> >> > inline int min(int a, int b) {
> >> > return a >= b ? b : a;
>
> >> > }
>
> >> > int find_min_steps(int const * const input, const int n) {
> >> > int min_steps_dp[n], i, temp, next_vacant;
> >> > for (i = 0; i < n; min_steps_dp[i++] = MAX);
>
> >> > min_steps_dp[0] = 0;
> >> > next_vacant = 1; // Is the index in the array whose min_steps needs to
> >> be
> >> > updated
> >> > // in the next iteration.
> >> > for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
> >> > temp = i + input[i];
> >> > if (temp >= n) {
> >> > min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] +
> >> 1);
> >> > temp = n - 1;
> >> > } else {
> >> > printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i]
> >> +
> >> > 1);
> >> > min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
> >> > }
> >> > if (temp > next_vacant) {
> >> > printf("i: %d \n", i);
> >> > for (; next_vacant < temp; next_vacant++) {
> >> > printf("next_vacant: %d \n", next_vacant);
> >> > min_steps_dp[next_vacant]
> >> > = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
> >> > }
> >> > }
> >> > }
> >> > for (i=0;i<n;printf("%d ",min_steps_dp[i++]));printf("\n");
> >> > return min_steps_dp[n-1];
>
> >> > }
>
> >> > int main() {
> >> > int n, *input, i;
> >> > scanf("%d",&n);
> >> > if ((input = (int *)malloc(n * sizeof(int))) == NULL) {
> >> > return -1;
> >> > }
> >> > for (i = 0;i < n; scanf("%d",&input[i++]));
> >> > printf("Minimum steps: %d\n",find_min_steps(input, n));
> >> > return 0;
>
> >> > }
>
> >> > Programmers should realize their critical importance and responsibility
> >> in a
> >> > world gone digital. They are in many ways similar to the priests and
> >> monks
> >> > of Europe's Dark Ages; they are the only ones with the training and
> >> insight
> >> > to read and interpret the "scripture" of this age.
>
> >> > On Fri, Jan 14, 2011 at 1:49 PM, Decipher <ankurseth...@gmail.com>
> >> wrote:
> >> > > I don't think the inner loop is executing only once . Kindly check it
> >> for
> >> > > this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner
> >> loop
> >> > > you will find that for same values of i(Outer index) inner loop is
> >> called.
> >> > > Its an O(n2) solution .
>
> >> > > --
> >> > > You received this message because you are subscribed to the Google
> >> Groups
> >> > > "Algorithm Geeks" group.
> >> > > To post to this group, send email to algogeeks@googlegroups.com.
> >> > > To unsubscribe from this group, send email to
> >> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> >> > > .com>
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252Bunsubscribe@googleg
> >> roups.com>
>
> >> > > .
> >> > > For more options, visit this group at
> >> > >http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> >> .com>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
