Re: [algogeeks] Re: Google Question--Suggest Algo
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size
of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly
selected
elements from the k subarrays. Basically means that we will
want to
split
the array in such way such that the sum
[algogeeks] Re: Google Question--Suggest Algo
O(N*K)
On Nov 28, 1:04 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size
of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing
[algogeeks] Re: Google Question--Suggest Algo
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
I don't think it is O(N*K)
It is O(N^2)
Just to confirm if i have understood correctly
Lets say n and k are given and are global to all subproblems
Subproblem Definition
F[i,j] - maximum expected sum that we can get by partitioning array from 0
to i into j subarrays. Each subarray satisfies the size bound
[ceiling(n/2k),floor(3n/2k)]
F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
subarray from i-r+1 to i}
So to calculate every subsequent subproblem we need to check solutions to
O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2)
On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution.
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
I don't think it is O(N*K)
It is O(N^2)
Just to confirm if i have understood correctly
Lets say n and k are given and are global to all subproblems
Subproblem Definition
F[i,j] - maximum expected sum that we can get by partitioning array from 0
to i into j subarrays. Each subarray satisfies the size bound
[ceiling(n/2k),floor(3n/2k)]
F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
subarray from i-r+1 to i}
So to calculate every subsequent subproblem we need to check solutions to
O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2)
On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final
[algogeeks] Re: Google Question--Suggest Algo
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time will be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
I don't think it is O(N*K)
It is O(N^2)
Just to confirm if i have understood correctly
Lets say n and k are given and are global to all subproblems
Subproblem Definition
F[i,j] - maximum expected sum that we can get by partitioning array from 0
to i into j subarrays. Each subarray satisfies the size bound
[ceiling(n/2k),floor(3n/2k)]
F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
subarray from i-r+1 to i}
So to calculate every subsequent subproblem we need to check solutions to
O(N/k) previous subproblems. And there are N subproblems, O((1/k)*N^2)
On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu duman...@gmail.com wrote:
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9]) + F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8]) + F(7, 2) ,
ExpVal (A[12 .. 7]) + F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution.
[algogeeks] Re: Google Question--Suggest Algo
Because in the previous example k = 3. On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source - http://stackoverflow.com/questions/8189334/google-combinatorial-optim... -- 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. -- 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: Google Question--Suggest Algo
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote:
You have an array with *n* elements. The elements are either 0 or 1. You
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k n. After you split the array into k subarrays. One element of each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to split
the array in such way such that the sum of all the expected values for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
Source -
http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
--
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.
--
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: Google Question--Suggest Algo
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the sum of all the expected values
for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
Source -
http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
--
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.
--
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.
--
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: Google Question--Suggest Algo
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the sum of all the expected values
for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4
Re: [algogeeks] Re: Google Question--Suggest Algo
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly
selected
elements from the k subarrays. Basically means that we will want
to
split
the array in such way such that the sum of all the expected
values
for the
elements selected from each subarray is maximum.
You can assume
