@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%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.
