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.
