There are apparently more than one way to make the cuts(totally it'll
still be three). The code only outputs first possible.
On Jan 11, 10:42 am, Arpit Sood <soodfi...@gmail.com> wrote:
> oh, i considered that the sum of the total numbers for both john and mary to
> be equal after the whole division process. I am not considering pair wise
> sum.
> That's why for input
> 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7
> segments should be:
> (John)1 4 5 6 2 2 ----- (Mary)2 2 4 5 6 1 1 7 8 ------ (John) 8 1 7
> minimum cuts made are 2
>
> but if we consider pair wise cuts as done by you, output will be :
> (John)1 4 5 6 2 2 ----- (Mary)2 2 4 5 6 1 --- (john) 1 7 8 ------ (Mary) 8 1
> 7
> minimum cuts = 3
>
>
>
> On Tue, Jan 11, 2011 at 8:38 PM, Jammy <xujiayiy...@gmail.com> wrote:
> > @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 <soodfi...@gmail.com> 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 <soodfi...@gmail.com> 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 <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>
> > <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 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.
