suppose:
v : array of guards' request
P(n): our problem: least coin spent until guard n, according to these rules
M(n, x): least coin possibly combined equal to or larger than x until guard
n
then:
P(n) = min(P(n-1)+v[n], M(n-1, v[n]))
M(n, x) = min(M(n-1, x), M(n-1, x-v[n]) + v[n])
On Monda
I can think of an o(n^2) algo for 2n question
Make a heap formed acctoring to two indexes
1.Primary -value
2.Secondary - index
Now for each new incoming value first search in head if exist inc its index
else make a new node
--
You received this message because you are subscribed to the Google Gr
@above
[20, 20, 3, 42]
regards
- Sumit Kumar Pathak
(Sumit/ Pathak/ SKP ...)
*Smile is only good contagious thing.*
*Spread it*!
On Mon, Feb 4, 2013 at 7:40 AM, navneet singh gaur <
navneet.singhg...@gmail.com> wrote:
> I guess it doesn't require a DP, I might have understood your question
1. Given a array,find a first unique integer.
2. Integers are coming as online stream,have to find a kth unique integer
till now.
For 1.
Even we cannot use sorting for solving this as if we sort it than our first
number which is non-repetitive changes.
The best I am able to do is nlogn using a
I guess it doesn't require a DP, I might have understood your question
wrongly but from what I have understood solution is as follows :
S = sum at a particular point
A[N] = array which contains guard's respective demands
i = 0, S=0;
while (i < N)
{
if (A[i] >= S)
{
S += A[i];
}
i++
You have N guards in a line each with a demand of coins.You can skip paying
a guard only if his demand is lesser than what you have totally paid before
reaching him.Find the least number of coins you spend to cross all guards.
I think its a DP problem but cant come up with a formula.Another appro
