Minimum number of cuts can be 1 and maximum can be n-1. Lets assume c
number of cuts 1=< c <= n-1 are required.
So brute force says :
iterate c 1 to n-1
and for these c cuts there would be (n-1)Cc combinations because there
are n-1 places in a1, a2,a3...an where these cuts can appear.
complexity would be order of n!.
On Jan 13, 11:34 pm, Jammy <xujiayiy...@gmail.com> wrote:
> brute force approach
>
> On Jan 12, 5:42 am, AKS <abhijeet.k.s...@gmail.com> wrote:
>
>
>
>
>
>
>
> > can someone just expain the plain simple logic used to solve this
> > problem ??
> > Cdn't get it seeing the code
>
> > On Jan 11, 10:08 pm, Jammy <xujiayiy...@gmail.com> wrote:
>
> > > 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 algogeeks@googlegroups.com.
> > > > > > >> To unsubscribe from this group, send email to
> > > > > > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> > > > > > >> .com>
> > > > > <algogeeks%2Bunsubscribe@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 algogeeks@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@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 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.
