@Arpit Please explain your solution to me. As far as I understand, every alternate of two person should sum up equally. Which means every pair of (john, mary) has the same sum for john and mary.
On Jan 11, 2:55 am, Arpit Sood <[email protected]> wrote: > @jammy your code isnt working for the mentioned test case. > One simple approach is to go greedy on the test data, but that wont always > give the optimum answer. > > > > > > > > > > On Tue, Jan 11, 2011 at 1:11 PM, Arpit Sood <[email protected]> wrote: > > the output for first test case is wrong it should be > > (John)1 4 5 6 2 2 ----- (Mary)2 2 4 5 6 1 1 7 8 ------ (Mary) 8 1 7 > > minimum cuts made are 2 > > > On Tue, Jan 11, 2011 at 10:04 AM, Jammy <[email protected]> wrote: > > >> (a) it is intuitive to see we need to make a recursive function which > >> takes the following arguments: > >> 1) array, > >> 2) start index, > >> 3) length of the array, > >> 4) a sentinel indicating if it is the first half or second half > >> 5) a sum if it is the second half > >> 6) number of cuts so far > >> 7) a global minimal cuts > > >> So my recursive function looks something like this, > >> void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, > >> int cut, int &minV, vector<int> &res); > > >> and its wrapper just takes two arguments > >> void cutMin(int *arr, int len); > > >> The idea is to differentiate the first half and second half. If it's > >> the first half, you need make all possible cuts, and recursive call > >> itself to get the second done. If it's the second half, you need > >> calculate sums all the way to the end. Break out of the loop if it > >> equals to the sum of the first part. And then recursively call itself > >> to get the first half done. > > >> I hope my code explains the idea...Please report any bugs you find :) > > >> vector<int> minVector; //storing the cuts > > >> void cutMin(int *arr, int len){ > >> int cut=0, minV = INT_MAX; > >> vector<int> res; > >> cutMinHelper(arr, 0, len, true, 0, cut, minV, res); > >> if(minV<INT_MAX){ > >> cout<<"minimal cut is"<<minV<<endl; > >> } > > >> } > > >> void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum, > >> int cut, int &minV, vector<int> &res){ > >> if(isFirst && start<len){ > >> if(start==0) cut = 0; > >> int sum = arr[start]; > >> cut++; > >> for(int i = start+1; i < len; i++){ > >> vector<int> addOne = res; > >> addOne.push_back(i-1); > >> cutMinHelper(arr, i , len, !isFirst, sum, cut, > >> minV, addOne); > >> sum += arr[i]; > >> } > >> } > >> if(!isFirst && start<len){ > >> int i, sum2 = 0; > >> for(i = start; i < len; i++){ > >> sum2 += arr[i]; > >> if(sum2 == sum){ > >> break; > >> } > >> } > >> if( i==len-1 && sum2==sum) { > >> if(cut<minV){ > >> minV = cut; > >> minVector = res; > >> } > >> } > >> if(i<len-1){ > >> cut++; > >> vector<int> addOne = res; > >> addOne.push_back(i); > >> cutMinHelper(arr, i+1, len, !isFirst, 0, cut, minV, > >> addOne); > >> } > >> } > >> } > > >> (b) I didn't write the code, but I think the code would look like the > >> first one with few modifications. > > >> On Jan 10, 1:08 pm, shady <[email protected]> wrote: > >> > Given an array of numbers : a1, a2, a3..... an.... > >> > (a) divide them in such a way that every alternate segment is given > >> to > >> > two persons john and mary, equally,,,, the number of segments made > >> should be > >> > minimum... > >> > eg.... > >> > for input > >> > 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7 > >> > segments : > >> > (John)1 4 5 6 2 2 ----- (Mary)2 2 4 5 6 1 --- (john) 1 7 8 ------ (Mary) > >> 8 1 > >> > 7 > >> > minimum cuts made are 3 > > >> > (b) Divide the numbers in such a way that both recieve same sum of > >> > numbers. > >> > If input > >> > 3 4 5 7 2 5 2 > >> > segments > >> > (john) 3 4 5 ----- (mary) 7 2 5 ----- (john) 2 > >> > minimum cuts are 2 > > >> -- > >> 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]<algogeeks%2bunsubscr...@googlegroups > >> .com> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > Arpit Sood > > Some day you will see things my way. > >http://arpit-sood.blogspot.com > > -- > Arpit Sood > Some day you will see things my way.http://arpit-sood.blogspot.com -- 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.
