Ouch. I think I was right to begin with and it is a matroid. I should
have been greedy right-to-left rather than left-to-right. This is
because you can only decrement. If we were incrementing instead, then
left-to-right would work fine.
So work right to left and for each item either
a) decrement d times if the item to the right is d > 0 smaller than
the current one or
b) delete the item
whichever is cheaper.
This makes the algorithm very simple and O(n) if you us a doubly-
linked list (for constant time delete).
Any thoughts? Am I missing something again?
On Aug 28, 12:19 pm, Gene <gene.ress...@gmail.com> wrote:
> My proposed solution was not correct. You need a DP because the
> problem is not matroid as I thought.
>
> But for this problem 14 seems correct to me. I can't see how you can
> get 8. You need to decrement 14, 15, 16 and 13 to 11. This is a
> total of 14 decrements. What am I missing?
>
> On Aug 28, 5:41 am, gaurav singhal <singhal08gau...@gmail.com> wrote:
>
>
>
> > @ Gene :
>
> > Output for
>
> > int a[] = { 14, 15, 16, 13, 11, 18 };
>
> > is coming out to be 14
>
> > whereas minimum cost will be : 8- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
