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 <[email protected]> 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-optimization-interview-problm > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
