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 <xujiayiy...@gmail.com> 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 <sinv...@gmail.com> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<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
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
