[algogeeks] Re: wooden log problem
if you have n points to cut and a wooden log of lenght l,choose mid[l]
and choose a point which is closer to this l and do this for all
segments
On Jan 31, 10:14 am, ritu ritugarg.c...@gmail.com wrote:
You are given a wooden log of length n. It has n+1 grooves marked on
it from 0 to n. You are given an array containing numbers within the
range of 1 to n-1. These elements of the array represents the points
on the log at which u need to cut the wooden log. Now the cost of
cutting a log is proportional to the length of the original log being
cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new
original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this
log is 9-1=8, so the cost will be 8.
--
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.
[algogeeks] Re: wooden log problem
DP solution is .. c[i][j] = min (c[i][k] + c[k][j] + (a[j]-a[i])) where k=i+1 to j-1 c[i][j] = a[j]-a[i] when j=i+1 c[i][j] indicates the minimum cost to cut the log starting at a[i] and ending at a[j]... c[0][n] gives the answer.. correct me if i am wrong or any better solutions? -- 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.
[algogeeks] Re: wooden log problem
DP solution is .. c[i][j] = min (c[i][k] + c[k][j] + (a[j]-a[i])) where ji k=i+1 to j-1 c[i][j] = a[j]-a[i] when j=i+1 c[i][j] indicates the minimum cost to cut the log starting at a[i] and ending at a[j]... c[0][n] gives the answer.. correct me if i am wrong or any better solutions? -- 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.
[algogeeks] Re: wooden log problem
You have given a nice setup, but you haven't stated a problem or asked
a question.
On Jan 31, 12:14 pm, ritu ritugarg.c...@gmail.com wrote:
You are given a wooden log of length n. It has n+1 grooves marked on
it from 0 to n. You are given an array containing numbers within the
range of 1 to n-1. These elements of the array represents the points
on the log at which u need to cut the wooden log. Now the cost of
cutting a log is proportional to the length of the original log being
cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new
original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this
log is 9-1=8, so the cost will be 8.
--
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.
[algogeeks] Re: wooden log problem
sorry ..the complete question is
You are given a wooden log of length n. It has n+1 grooves marked on
it from 0 to n. You are given an array containing numbers within the
range of 1 to n-1. These elements of the array represents the points
on the log at which u need to cut the wooden log. Now the cost of
cutting a log is proportional to the length of the original log being
cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new
original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this
log is 9-1=8, so the cost will be 8.
The question is: given the value of 'n' and the Array A containing the
points at which u need to make a cut, find the order in which the cuts
must be made in order to minimize the total cost of cutting the wooden
log.
--
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.
Re: [algogeeks] Re: wooden log problem
vectorvectorint cuts(int n, vectorint A)
{
int min;
int numcuts = A.size();
vectorvectorint Cuts(vectorint V(0,n), n);
vectorvectorint Result(vectorint V(0,n), n);
for(int i=0;inumcuts;i++)
{
Cuts[A[i]][A[i]]=0;
Cuts[A[i]][A[i+1]]=0;
}
for(int cutlen=2;cutlennumcuts;cutlen++)
for(int i=0;i(numcuts-cutlen);i++)
{
min=INT_MAX;
for (k = i + 1; k (i + cutlen); ++k)
{
if(min (Cuts[A[i]][A[k]] + Cuts[A[k]][A[i+cutlen]]))
Result[A[i]][A[i+cutlen]]=k;
}
Cuts[i][i+len] = min + A[i + len] - A[i];
}
return Result;
}
On Tue, Feb 1, 2011 at 11:47 AM, ritu ritugarg.c...@gmail.com wrote:
sorry ..the complete question is
You are given a wooden log of length n. It has n+1 grooves marked on
it from 0 to n. You are given an array containing numbers within the
range of 1 to n-1. These elements of the array represents the points
on the log at which u need to cut the wooden log. Now the cost of
cutting a log is proportional to the length of the original log being
cut.
Eg: n=15 and A={1,5,9}
Now when u make a cut at 1, the cost is n (the size of original log)
When u cut at 9, the cost will be n-1 as the length of the new
original log is 1 to n i.e n-1
When u cut at 5, since 5 lies between 1 and 9 and the length of this
log is 9-1=8, so the cost will be 8.
The question is: given the value of 'n' and the Array A containing the
points at which u need to make a cut, find the order in which the cuts
must be made in order to minimize the total cost of cutting the wooden
log.
--
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.comalgogeeks%2bunsubscr...@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.
