hey what is the question .. m getting half of the posts ... can you please
paste and send the question back
On Mon, Feb 21, 2011f at 10:52 PM, Gaurav Gupta
<1989.gau...@googlemail.com>wrote:
> 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.
>
>
--
With Regards,
*Jalaj Jaiswal* (+919019947895)
Software developer, Cisco Systems
B.Tech IIIT ALLAHABAD
--
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.
