If you need hint:
I used DP (Dynamic Programming) to solve this and get AC (Accepted). I
stored the matrix as 2-D array and then started with array[R][C]. From
there I can go upward and left. In each element of array put the minimum
possible value to get the array[R][C]. In case, if we get the
The first problem I mentioned is a similar problem. but the second one
seems to be little difficult. where additional path we could go is up.
-
Azhar.
On Thu, Dec 15, 2011 at 10:17 PM, Dheeraj Jain dheerajj...@gmail.comwrote:
http://www.geeksforgeeks.org/archives/14943 is a very similar
Take an array of size Min[N+1][S+1]
where, N is the total no. of unique denominations and S is the total
sum
Let the value array be V[N]; // let it be 1- based indexed for ease of
explanation in the below given code snippet.
Initialize the following:
a) for (i =0; i = N; ++i)
Min[i][0]
http://www.geeksforgeeks.org/archives/14943 is a very similar problem.
On Thu, Dec 15, 2011 at 1:12 PM, WgpShashank shashank7andr...@gmail.comwrote:
@Azhar , also for 1st question u r trying Array DS will suffices. Its
Standard Coin Change Problem , u need to solve subproblem 1st , store it in
Longest path won't work so well because it will return infinity if a
path contains a positive cycle, which doesn't apply here because once
you pick up an apple, it's gone.
On Dec 13, 7:17 am, vikas vikas.rastogi2...@gmail.com wrote:
Graph
take up, right and bottom as nodes connected to current
We need not necessarily pick the apple. We need to suggest a way that could
have maximum apples and path need not be longest. Another person will
follow our path and pick the apples.
we can start from specified (i,j) and have to reach specified (i, n)
traversing either top, right, down(not left).
From (a,b) to (c,n) = What about traversing all columns n = j = a
as we can move up-down-right anytime we want.
On Dec 14, 5:57 pm, Azhar Hussain azhar...@gmail.com wrote:
We need not necessarily pick the apple. We need to suggest a way that could
have maximum apples and path need not be
@Azhar , 1st Try to formulate the recursive relation , then draw recursive
tree , then u willl know why it need DP to solve efficiently , then u can
memozation to solve the same .
Hope it help.
Thanks
Shashank Mani
CSE ,BIT Mesra
http://shashank7s.blogspot.com/
--
You received this
@Azhar , also for 1st question u r trying Array DS will suffices. Its
Standard Coin Change Problem , u need to solve subproblem 1st , store it in
extra array to avoid recalculation , if u are able to produce the sum less
given sum then u can use same approach to reach desired sum . it uses the
Graph
take up, right and bottom as nodes connected to current and do find
max path.
On Dec 13, 3:44 pm, Azhar Hussain azhar...@gmail.com wrote:
We have apples arranged in a mxn matrix. We start from the upper left
corner and have to reach bottom right corner with maximum apples. We can
only
Someone please reply.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/vBP5ZdFV9HEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To
Reply for what?
On Sat, Jul 16, 2011 at 1:07 PM, Nitish Garg nitishgarg1...@gmail.comwrote:
Someone please reply.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
Because here we can not reOrder words, Greedy seems to work fine to me too,
i am not able to come up with an contradictory example..will post if
will get one... or post if any one can.
but here http://mitpress.mit.edu/algorithms/solutions/chap15-solutions.pdfis
the DP solution to the
I just read that had the cost of a line be defined as just the number of
extra spaces and not as the cube of the number of extra spaces, then the
greedy approach I mentioned in the above post, can anybody explain why not
in the first case?
--
You received this message because you are
Use complete search, add memoization and you have a top-down dynamic
programming solution ready.
- lets say we have division positions in an array cuts[]
- start and end will identify the position of current cut (taken from
cuts[] array)
- initialize memo[][] array to INT_MAX, this is the place
About?
--
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
I meant any test cases you think I haven't covered in my solution.
Although I have run this solution and checked answer manually .
--
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.
You may check the exact solution found here:
http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf
--
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
Thanks
--
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
I think your solution will take O(n3) time , as it will require three
loops . 1st for index i , 2nd for first max and 3rd for second max .
Instead we should take :
dp[i] = max(dp[j]) + p[i] , where ji and m[i] - m[j] k . Pls
correct me if something is wrong .
--
You received this message
int solve(int id) {
if(id==n)
return 0;
int d = dp[id];
if(~d) return d;
d = 0;
for(int i=id+1;in;i++) {
if(dis[i]-dis[id]=k) {
d ?= val[id] + solve(i);
}
}
return d;
}
Its O(n^2), and Juver++, is very
Unfortunately, you are wrong.
We need one loop for i and that is all. All other things for searching max
p[j] is solved by segment tree in O(log n).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
I am telling the DP O(n^2) solution, whts wrong in it??
On Wed, Jan 5, 2011 at 10:36 PM, juver++ avpostni...@gmail.com wrote:
Unfortunately, you are wrong.
We need one loop for i and that is all. All other things for searching max
p[j] is solved by segment tree in O(log n).
--
You received
I was replying to the @Decipher post. Not yours. :)
Your algorithm seems to be ok.
--
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
ok :):)
On Wed, Jan 5, 2011 at 10:43 PM, juver++ avpostni...@gmail.com wrote:
I was replying to the @Decipher post. Not yours. :)
Your algorithm seems to be ok.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
Minor fixes:
i loop should be from 0 to id - 1, if you are moving from left to right.
initial value of d should be the val[id] not 0.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Sorry, disregard my first proposition about index i.
--
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
In main just pass
answerIs = max(val[0], solve(0));
On Wed, Jan 5, 2011 at 10:49 PM, juver++ avpostni...@gmail.com wrote:
Sorry, disregard my first proposition about index i.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
In any column, we can place atmost 2 pebbles.
(a) Considering an isolated column, we can place 1 or 2 pebbles.
Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4}
(b) Have an array dp[n][5][5]. Let dp[i][j][k] store the maximum sum
that can be achieved starting from column 'i' to column 'n-1' (columns
Thanks everyone for suggestions and follow my Dynamic Programming -
Series for more questions on DP .
--
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
what about printing these strings onto terminal. can printing of the
string is also similar. I tried to develop the algo but got messed
up.can some one help?
On Aug 8, 2:53 am, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
@ankur: dp[i][j] number of (prefix) strings that have i
Yes its some what similar..!!
On Dec 7, 4:57 am, sharad kumar aryansmit3...@gmail.com wrote:
is this similar to coin exchange problem?
On Mon, Dec 7, 2009 at 5:42 PM, Hitesh manus...@gmail.com wrote:
hi there,
Need help on this..any way or suggestion how to solve this problem..
any
Hi
I have a simmilar Problem , and was wondering if you can elaborate on
the funktion ,
sorry I am a starter and I need a bit more explainations ...
f(P1,P2, P3,...Pn) ,,,
How can I implement it in Java ,...
Thank you
Samuel
On 6 Jan., 08:10, Satish [EMAIL PROTECTED] wrote:
We can
Well, actually that only solves for when the # of players and events
are same, what if there're more players than events?
The recursion you describe has exponential growth rate. f(c) for some
set of P's can't really be cached, because the number of possible c's
is just are huge as exponential.
We can use dynamic programming here to find out the team configuration
with minimum time.
Define a function f(P1,P2, P3,...Pn) that returns the players sequence
(given n players for n rounds, which swimmer swims at which position)
that would return the total minimum time.
Then f() can be
At risk of stating the incredibly obvious, or giving away answer to a
fun interview question.
The naive but correct algorithm that gives the solution will have
tried every combination M of K swimmers in M events. which will give
you K!/(K-M)! arrangements, and the algorithm would then compare
let pr[i] be answer to sub-problem 1..i and there is restaurant built at i.
(maximum expected total profit)
How do we calculate pr[i]? Expected profit from location i + max. pr[j], where
location of j is at least k apart from location i.
pr[i] = p[i] + max(pr[j]), where j is between 1..i-1 and
Hi mukesh,
Let M(S),S=0 be true if its possible to make money S with the given coins
v1,v2,...vk.
Then,
M(S)=M(S-v1) || M(S-v2) || ...|| M(S-vk).
Base Case:
M(vi)=true for 1=i=k.
M(0)=true
Let vl be the smallest of all vi's where 1=i=k.
Then M(1...vl-1)=false.
On 3/3/07, mukesh tiwari [EMAIL
Hi,
Greedy solution will work only when the denomination of coins are such
that they are
multiples of the smallest number present (it should be greater than 1)
In dynamic programming we check all possible combination.
and improve the runtime by storing results in tables/arrays we can
save a lot
I have the same question. It seems the S-G function doesn't work when
there is a draw... ?
Rajiv Mathews 写道：
Is there a way to leverage this solution to handle more than one pile
of matches?
Say there were k piles each containing n_1, n_2, ..., n_k matches,
with the same rules, that is
Yes , it will always fill with 3 .
the best result both player can get for n 4 is always draw.
You can check it for some values on paper .
if you want to have a winner you must change the basic conditions of the
problem.
On 11/28/06, ravi [EMAIL PROTECTED] wrote:
We Define an array Win[]
k...ThanxI have cleared my doubt
I would like to ask here one more question similar to this question.
Suppose a game is played between A and B, consider a number n = 100, at
each time each player adds a divisor of n 100 to n. Find which player
won the game when total = 1953, when the
I fear this problem is NP hard.
43 matches
Mail list logo
