Re: [algogeeks] Re: Algo Question
take this example
let the gaurds demand be
5 2 7 2 9
first guard : we have no choice but to give him 5
second guard : we have choice , either skip him and pay 7 to next guard or
pay him and save 7 from third guard .. thus clearly multiple solutions
exist but we have to give optimal one. { hint for dp }
if we know the solution for upto i-th guard, we can extend this solution to
i+1-th guard
solution here represents all the possible amounts that one can spend till
i-th guard, extending that will give us all the possible amounts for i+1 th
guard and we just select the minimum amount. thus optimal substructure is
also there.
using the below code , the output for example is 12 with possible sequence.
guard 1 : 5
guard 2 : skip
guard 3 : 7
guard 4 :skip
guard 5 :skip
// non optimized code -purely for demonstration purpose -
#include stdio.h
#include stdarg.h
#define size 5
#define amount 1000 // maximum amount asked by all the gaurds combined
int solution[size][amount];
int main (int argc, char const *argv[])
{
int arr[] = {5,2,7,2,9};
int min, i, j;
int sum = 0;
for(i = 0; isize; i++) {
sum += arr[i];
}
solution[0][arr[0]] = 1;
for(i = 1; i size; i++) {
for(j = 0; j= sum; j++) {
if(solution[i-1][j] == 1) {
if(j arr[i]) {
solution[i][j] = 1;
}
solution[i][j + arr[i]] = 1;
}
}
}
min = 10; // infinite value
for(i = 0; i sum; i++) {
if(solution[size - 1][i] i min)
min = i;
}
printf(%d, min);
return 0;
}
@marti check the solution for other testcases , I'll post the optimized
version after that.
On Wed, Feb 27, 2013 at 1:04 AM, Saurabh Paliwal
saurabh.paliwa...@gmail.com wrote:
Please mention the initial condition.
I mean I wouldn't pay to any guard (assuming their demands are all
positive numbers)
On Wed, Feb 27, 2013 at 12:39 AM, marti amritsa...@gmail.com wrote:
Sure..
http://stackoverflow.com/questions/14686745/guards-and-demand
On Monday, February 4, 2013 5:54:19 PM UTC+5:30, marti wrote:
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
approach would be to binary search on the answer but how do I verify if no.
of coins is a possible answer?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
-Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] help with o/p why 0 comes???
yeah true . one interesting thing I noticed is that if you run this code
#includestdio.h
int main()
{
int i = 0;
do {
printf (%d\n,(float)1);
}while(i++ 1);
return 0;
}
one would expect same output in both the rows but surprisingly it came
different for me every time .
any clues .. why ?
On Fri, Mar 1, 2013 at 12:05 PM, Karthikeyan V.B kartmu...@gmail.comwrote:
O/p will not be 0.
1.00 is the result which when read as %d takes the decimal value of
float 1.00 stored in memory - it will not be 1.00 or 0.
Since float is not stored as direct binary in memory as integer is stored,
instead there's a separate procedure for storing float as binary in memory
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] help with o/p why 0 comes???
output for me for the previous snippet
localhost:slingshot rohitjangid$ ./a.out
1799476872
1799474584
localhost:slingshot rohitjangid$ ./a.out
1710327432
1710325144
localhost:slingshot rohitjangid$ ./a.out
1856128648
1856126360
localhost:slingshot rohitjangid$ ./a.out
1724065416
1724063128
On Mon, Mar 4, 2013 at 7:33 AM, rohit jangid rohit.nsi...@gmail.com wrote:
yeah true . one interesting thing I noticed is that if you run this code
#includestdio.h
int main()
{
int i = 0;
do {
printf (%d\n,(float)1);
}while(i++ 1);
return 0;
}
one would expect same output in both the rows but surprisingly it came
different for me every time .
any clues .. why ?
On Fri, Mar 1, 2013 at 12:05 PM, Karthikeyan V.B kartmu...@gmail.comwrote:
O/p will not be 0.
1.00 is the result which when read as %d takes the decimal value of
float 1.00 stored in memory - it will not be 1.00 or 0.
Since float is not stored as direct binary in memory as integer is
stored, instead there's a separate procedure for storing float as binary in
memory
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] MS Question:WAP to print last n lines of a log file
Q1. Given a log file, pirnt last n lines. Note that the Log file is being written into. Q2. Implement Circular Buffer. Best Regards Ashish Goel Think positive and find fuel in failure -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
