@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>
>> .
>> 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
