The greedy will always chose the maximum, so iff a 0 is chosen, that implies
one cannot reach the end of the array.
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 Sun, Jan 16, 2011 at 12:16 PM, SVIX <saivivekh.swaminat...@gmail.com>wrote:
> thinkin abt this again, there may be a slight problem with
> straightforward greedy...
> note that reaching 0 doesn't let u move forward...
>
> On Jan 15, 12:54 pm, Avi Dullu <avi.du...@gmail.com> wrote:
> > @jammy Thanx for the elongated description :)
> >
> > Yes, I feel I probably gave a DP solution wrongly to the Greedy approach.
> > But just to clarify, Greedy does not solve any subproblems, it just makes
> a
> > locally optimal choice and proceedes towards a global optimal strategy.
> And
> > your point that greedy usually takes lesser time than DP also stands
> > correct, but there are a lot of exceptions wherein the choice of local
> > optimal strategy may be of very high order, and thus perform worse than
> DP.
> >
> > Just to rest (and clarify) my argument, the following is the greedy
> approach
> > I feel, *will* fail:
> >
> > for i = 1; i < n; i++
> > next_jump_will_be_from_index = index of max(input[ i ... i + input[i]
> ])
> >
> > i.e. after each jump, greedy strategy is to choose the next jumping point
> as
> > the one which has maximum value
> >
> > 3, 5, 3, 4, 1, 3, 4, 5
> >
> > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
> > whereas DP would take 3, 4 ( 2 steps)
> >
> > and if you notice, the implementation of this greedy (without using fancy
> > RMQ/segment trees) would still be O(n^2) or O(nlogn) (using RMQ/segment
> > trees)
> >
> > 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 Sun, Jan 16, 2011 at 1:39 AM, Jammy <xujiayiy...@gmail.com> wrote:
> > > @svix, I think pacific means takes i+v, But it still won't give the
> > > global optimal
> >
> > > @Avi, I am not an expert on greedy algorithm and some problems may be
> > > solved by using greedy. But as far as I understand, the difference
> > > between DP and Greedy is DP makes use of the solution of the
> > > subproblems while greedy doesn't. DP solves current problem by solving
> > > subproblems first and then making the choice. Greedy solves current
> > > problem by making a choice and solving subproblems. (see CLRS).That's
> > > why greedy gives me this idea that it usually takes less time then
> > > DP.
> >
> > > In your latest post, it appears to me you are using DP instead greedy
> > > because your solution to current problem is built upon the solution of
> > > subproblems.
> >
> > > Please give me your input.
> >
> > > On Jan 15, 12:59 pm, SVIX <saivivekh.swaminat...@gmail.com> wrote:
> > > > actually, there is a way t do this in greedy... instead of taking the
> > > > local maximum value v for an index i, take the local maximum f(v) = i
> > > > + v... this will get you the right answer...more efficient than DP?
> > > > that i'm not sure... but average case will be close to linear....
> >
> > > > On Jan 14, 9:29 pm, SVIX <saivivekh.swaminat...@gmail.com> wrote:
> >
> > > > > @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%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> > > <algogeeks%2Bunsubscribe@googlegroups .com>
> > > > > > >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@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%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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
> >
> > ...
> >
> > read more ยป
>
> --
> 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%2bunsubscr...@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.
