@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 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.4333333
>> >
>> > > > > > 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.83333333
>> >
>> > > > > > 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.
>>
>>
> --
> 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.
>
--
Nitin Garg
"Personality can open doors, but only Character can keep them open"
--
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.
