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. 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. > > -- > 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.