@avi
regarding ur statement...
"
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)
"
it depends on what you are greedy about... as i had mentioned earlier,
your algorithm should be greedy on how far the value you choose will
let you jump and not just on the size of the value... i.e, get the
local maximum for (currentIndex + array[currentIndex])
that is,
input: 3, 5, 3, 4, 1, 3, 4, 5
index 0 1 2 3 4 5 6 7
when index = 0, u can choose items at index 1, 2 and 3... go greedy on
f(index) = index + array[index]
so f(1) = 1 + 5 = 6
f(2) = 2 + 3 = 5
f(3) = 3 + 4 = 7
plainly, if u define ur greedy criteria right, u go for index 3...
On Jan 15, 11:15 pm, Avi Dullu <avi.du...@gmail.com> wrote:
> 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
>
> ...
>
> 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
