Re: [algogeeks] MXN matrix
Let Memo[i][j] be the sum of elements in the (sub) rectangle from (0,0) to (i,j) Then use principle of inclusion and exclusion to find the sum of elements from (a, b) to (c, d) in O(1) for N*N matrix, Complexity is O(N^4) On 28 April 2010 13:36, Ashish Mishra wrote: > you are given a M x N matrix with 0's and 1's > find the matrix with largest number of 1, > 1. find the largest square matrix with 1's > 2. Find the largest rectangular matrix with 1's > > -- > 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. > -- "Reduce, Reuse and Recycle" Regards, Vivek.S -- 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.
Re: [algogeeks] Build BST from binary tree without extra space
@Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar wrote: > pickup node in any order no matter(pre,post,inorder) and just one by > one. start adding the node into bst no need to use extra space u have > to just ditach the node from binary tree and attach it in bst. > > On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra > wrote: > > How to build BST from binary tree in place i.e without extra space ?? > > > > -- > > 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. > > > > > > -- > BL/\CK_D!AMOND > > -- > 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. > > -- "Reduce, Reuse and Recycle" Regards, Vivek.S -- 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.
Re: [algogeeks] Dijkstra For Longest Path?
@chitta koushik No, That might lead to negative edge cycles! 2010/1/15 chitta koushik > How abt negating values and using same single source shortest path algo ? > > 2010/1/15 saltycookie > >> longest path is NP-hard >> >> 2010/1/11 Johan >> >>> Ok, so I know that Dijkstra can be used to solve the single-source >>> shortest path problem quite efficiently. I however need to find the >>> single source longest path through a graph. Can Dijkstra be used for >>> this if I transform the edge lengths so that the longest edge is now >>> the shortest etc etc. Does anybody have any references to work done >>> which is similar to the this longest path problem? >>> >>> >>> -- >>> 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. >>> >>> >>> >>> >> >> >> -- >> 此致 >> 敬礼！ >> >> 林夏祥 >> >> -- >> 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. >> >> > > -- > 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. > > -- "Reduce, Reuse and Recycle" Regards, Vivek.S -- 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.
[algogeeks] Re: Good problem
to maximize the minimum distance between any two points:-> to maximize the
minimum distance between adjacent points
-> for this all points must be equally spaced.
hence, choose 'n' equally spaced points in the range (r1, r2) starting from
r1 and ending at r2.
2009/10/21 saltycookie
> Yes, you are quite right. If I am not mistaken, you give a good solution
> for finding the minimum maximum distance.
>
> But what about the original problem where we want to find the maximum
> minimum distance? I am not clear about the connection between the two
> problems.
>
> Thanks.
>
> 2009/10/21 Dave
>
>
>> 林夏祥 , think again. If we are trying to minimize the maximum distance,
>> then we want to minimize the upper bound. That is what I specified:
>> letting c be the upper bound, find the smallest c such that all of the
>> distances do not exceed c. That gives rise to the inequalities
>> |x(i)-x(j)| <= c.
>> If necessary, this can be written as two inequalities:
>> x(i) - x(j) <= c and
>> x(j) - x(i) <= c.
>>
>> Since the relationship is "and," we can just use the two inequalities
>> as part of the constraint conditions.
>>
>> Dave
>>
>> On Oct 21, 12:02 am, 林夏祥 wrote:
>> > I don't think LP can solve it. We are to maximize c, not minimize c.
>> > The formulas we have are:
>> >
>> > |x(i)-x(j)| >= c for all i and j
>> > r1(i) <= x(i) <= r2(i) for all i
>> > The first inequality actually is combination of two linear equalities:
>> x(i)
>> > - x(j) >= c or x(i) - x(j) <= -c. Notice the relation of the two is
>> "or",
>> > and we cannot put them together to get a system of linear inequalities.
>> > 2009/10/21 Dave
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > This is a linear programming problem. The way you formulate the
>> > > problem depends on the capabilities of the linear programming software
>> > > you have.
>> >
>> > > Basically, you want to
>> > > minimize c
>> > > by finding x(1) to x(n) such that
>> >
>> > > |x(i)-x(j)| <= c for all i and j
>> > > r1(i) <= x(i) <= r2(i) for all i
>> >
>> > > Dave
>> >
>> > > On Oct 5, 9:22 am, monty 1987 <1986mo...@gmail.com> wrote:
>> > > > We have to locate n points on the x-axis
>> > > > For each point xi
>> > > > the x co-ordinate of it lies between a
>> range
>> > > > [r1i,r2i]
>> > > > Now we have to decide the location of points such that
>> > > > minimum { distance between any two points } is maximum.
>> >
>> > > > Any answer is welcomed.
>> >
>> > --
>> > 此致
>> > 敬礼！
>> >
>> > 林夏祥- Hide quoted text -
>> >
>> > - Show quoted text -
>>
>>
>
>
> --
> 此致
> 敬礼！
>
> 林夏祥
>
>
> >
>
--
"Reduce, Reuse and Recycle"
Regards,
Vivek.S
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Good problem
I guess choosing n equally spaced points withing the given interval will be
the desired solution.
2009/10/20 Mithun Kumar Singh
> Hi,
>This problem is same as a Travelling salesman problemIn
> travelling salesman we need to cover points in Min distance...here we need
> to just opposite..
>
> PS: Answer may be misleading ...if so Pls correct me... :)
>
> -Mithun
>
>
>
>
> On Tue, Oct 20, 2009 at 6:16 PM, monty 1987 <1986mo...@gmail.com> wrote:
>
>> Hi,
>> Still waiting for solution...
>>
>> On Wed, Oct 7, 2009 at 3:18 PM, monty 1987 <1986mo...@gmail.com> wrote:
>>
>>> The important thing is all the points do not lie in same range i.e.
>>> x1 ,x2 ,x3 each of them have their own range.
>>>
>>>
>>> On Wed, Oct 7, 2009 at 3:15 PM, monty 1987 <1986mo...@gmail.com> wrote:
>>>
The min. distance between two points i.e. the euclidean distance between
two points.
On Tue, Oct 6, 2009 at 5:52 PM, MrM wrote:
>
> you can arrange them with equal distances !
> if n=1 then, it does not matter where you put the point !
> if n>1 then, put them with distances = (r2i-r1i) / (n-1) !
> it means ou put the first point on r1i and the last point on r2i, the
> remaining point are distributed with equal distances !
>
> On Oct 5, 5:22 pm, monty 1987 <1986mo...@gmail.com> wrote:
> > We have to locate n points on the x-axis
> > For each point xi
> > the x co-ordinate of it lies between a
> range
> > [r1i,r2i]
> > Now we have to decide the location of points such that
> > minimum { distance between any two points } is maximum.
> >
> > Any answer is welcomed.
>
>
>
>>>
>>
>>
>>
>
> >
>
--
"Reduce, Reuse and Recycle"
Regards,
Vivek.S
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: 100!
hope you mean "find *sum* of all the digits in number->100!" :) 2009/10/11 vicky > > find some of all the digits in number->100! > > > > -- "Reduce, Reuse and Recycle" Regards, Vivek.S --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: minimum difference.
@Varun S VIt wont work for this 1 3 4 5 2009/9/2 Varun S V > Since we difference between two minumum elements should suffice, how about > finding the min and second minimum element in the array in single scan and > returning their difference. This should take not more than O(N) time. > > Regards, > -Varun. > > > On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote: > >> Sort the array and find the minimum of difference of adjacent values of >> the sorted array. >> Time Complexity : O(nlogn), Space Complexity : O(1) >> >> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal >> wrote: >> >>> given a array of length n. find 2 number such that their differnce is >>> minimum. >>> >>> >>> >>> >>> >> >> >> -- >> Shishir Mittal >> Ph: +91 9936 180 121 >> >> >> >> > > > > -- "Reduce, Reuse and Recycle" Regards, Vivek.S --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Find longest interval
let A[i+1] = a[0] + a[1] + ... + a[i]; let B[i+1] = b[0] + b[1] + ... + b[i]; A[0] = B[0] = 0; sum of nos from i to j of a[] = A[j+1] - A[i]; // O(1) time Thus O(n^2) sol can be obtained for this problem by finding the sub-array sum in the range [i, j] for every i, j; But I have not used the fact that the given nos is either 0 or 1. There should be a better way, yet to think about it :) 2009/8/26 ankur aggarwal > Find longest interval We are given with two arrays A and B..each of size > N...elements of array contains either 1 or 0... > > we have to find such an interval (p,q)(inclusive) such that the sum of all > the elements of A (between this interval) and sum of all elements of B > (between this interval ) is equal... > > i.e. > > a[p]+a[p+1]+a[q]= b[p]+b[p+1]+b[q] > > > > -- "Reduce, Reuse and Recycle" Regards, Vivek.S --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
N! overflows... Try to write a program to find the value of 30! You don't have a variable that is large enough to store such a big number... 2009/7/31 sharad kumar > check this out > > Let x and y be the missing number, > > Now equation 1 is : x + y = [n(n+1)/2] - S > equation 2 is: x * y = N! /P > solve both we get elements > > On Fri, Jul 31, 2009 at 8:27 PM, Devi G wrote: > >> The logic is actually simple. Tot if we mark in some way an element when >> it's scanned, we can find the missing numbers in the second scannin. >> >> 3,5,1,2,9,10,8,6 >> >> When for loop sees '3' it knows elt 3 is there. So multiplies the number >> at 3rd position by some arbitrary number. (* I've taken the arbitrary >> number to be n here but CORRECT ONE IS n+3 cos n will fail in some cases* >> ) >> >> so, when it sees '5' multiplies the number at 5th position by n+3. >> It skips when the numbr is greater than n. >> >> n+3 = 11 here. >> >> So,after first loop, >> 33, 55, 11, 2 , 99, 110, 8, 66. >> >> So now, in the second scan, the indices of all elts that are divisible by >> n+3 are present in the array. >> elts at 4th and 7th positions are not divisible. hence missing numbers are >> 4 and 7. >> >> >> >> >> > > > > -- "Reduce, Reuse and Recycle" Regards, Vivek.S --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
@Devi;
Consider this,
N = 2
The array elements should these (N+2), numbers : {1, 2, 3, 4}
If the given array is {4, 3}
Will your code work correctly?
2009/7/31 Devi G
> The logic is actually simple. Tot if we mark in some way an element when
> it's scanned, we can find the missing numbers in the second scannin.
>
> 3,5,1,2,9,10,8,6
>
> When for loop sees '3' it knows elt 3 is there. So multiplies the number at
> 3rd position by some arbitrary number. (* I've taken the arbitrary number
> to be n here but CORRECT ONE IS n+3 cos n will fail in some cases*)
>
> so, when it sees '5' multiplies the number at 5th position by n+3.
> It skips when the numbr is greater than n.
>
> n+3 = 11 here.
>
> So,after first loop,
> 33, 55, 11, 2 , 99, 110, 8, 66.
>
> So now, in the second scan, the indices of all elts that are divisible by
> n+3 are present in the array.
> elts at 4th and 7th positions are not divisible. hence missing numbers are
> 4 and 7.
>
>
>
> >
>
--
"Reduce, Reuse and Recycle"
Regards,
Vivek.S
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
