same question as wat i asked in partioning of array such that the diff is
min.
On 31 May 2010 22:07, Senthilnathan Maadasamy
senthilnathan.maadas...@gmail.com wrote:
Same question with interesting answers in stackoverflow :
@Divya: nope, your Q requires equal count too whereas this doesn't.
On Thu, Jun 3, 2010 at 1:06 PM, divya jain sweetdivya@gmail.com wrote:
same question as wat i asked in partioning of array such that the diff is
min.
On 31 May 2010 22:07, Senthilnathan Maadasamy
Still the solution will be similar and actually a bit simpler.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
yep, constraints are fewer here
but in terms of problem statement 'same' and 'similar' can create
diversions.
On Thu, Jun 3, 2010 at 6:01 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Still the solution will be similar and actually a bit simpler.
--
This should be solvable by dp as in knapsack problem
where value = weights
and W = S/2.
where S = sum of all elements in the array.
The claim here is diff in sum of two subsets will be minimum
when one maximizes a sub-set sum (say s) where sum (s) is closest to S/2.
Divya's problem is looking
@abhishek,sharad: It is not important to have equal no. of players in
2 team and difference in skills of 2 teams may not be zero always. The
aim is to have as balanced a team as possible baced on skill sets. For
example is there are 4 players with skill [9,2,1,2,], then the
solution is Team1 [9]
This problem is like 2 processor job scheduling problem ,We may get an
optimal solution for different instances using different algorithm
apart from brute force.Whereas Brute force covers all possible subsets
but may take years to complete if N is large.
above algo fails in the following example.
ya I guess its the same problem..
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Mon, May 31, 2010 at 10:00 AM, W Karas wka...@yahoo.com wrote:
Is this the same problem as:
http://groups.google.com/group/algogeeks/browse_frm/thread/26c31cc2530a88e1#
?
Or can the teams have
Well, in that case, then just forget the balancing the number of elements
in the 2 teams portion of my solution above :)
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Mon, May 31, 2010 at 10:38 AM, Nik_nitdgp nikhil.bhoja...@gmail.comwrote:
This problem is like 2 processor job
Same question with interesting answers in stackoverflow :
http://stackoverflow.com/questions/890171/algorithm-to-divide-a-list-of-numbers-into-2-equal-sum-lists
On Mon, May 31, 2010 at 5:54 PM, Anurag Sharma anuragvic...@gmail.comwrote:
Well, in that case, then just forget the balancing the
Is this the same problem as:
http://groups.google.com/group/algogeeks/browse_frm/thread/26c31cc2530a88e1#
?
Or can the teams have different numbers of players?
On May 30, 2:28 pm, Veer Sharma thisisv...@rediffmail.com wrote:
Hi Friends,
This is my first post to this forum. A Hi to all of
Yes this seems to be working.
On Feb 3, 6:50 pm, Aravind Narayanan [EMAIL PROTECTED] wrote:
On Feb 3, 2008 10:12 PM, Ridvan Gyundogan [EMAIL PROTECTED] wrote:
Hi Aravind,
I think it will not work in this array:
{1,2,3,4,5,6,7,7,7,7}
It would give currentelem=7 and c=3 but 7 is not
Hi HC
On Jan 30, 2008 12:53 AM, hc busy [EMAIL PROTECTED] wrote:
I think there was a typo. I wanted to say its a constant space,
linear time algorithm instead of constant time linear space
algorithm Maybe that helps to make sense of it.
Well, one must find a number that repeats at least
Hi HC,
Here, In this sentence
So there needs to be a number that is
repeated once after seeing n/2+2 numbers for this to be possible(and
the rest must all be the same)
How did u find this number ?
k bye
On Jan 26, 2008 3:32 AM, hc busy [EMAIL PROTECTED] wrote:
#2 is weird, start by
I think there was a typo. I wanted to say its a constant space,
linear time algorithm instead of constant time linear space
algorithm Maybe that helps to make sense of it.
Well, one must find a number that repeats at least twice after seeing
n/2+2 numbers, (then require the rest to be that same
I think there was a typo. I wanted to say its a constant space,
linear time algorithm instead of constant time linear space
algorithm Maybe that helps to make sense of it.
Well, one must find a number that repeats at least twice after seeing
n/2+2 numbers, (then require the rest to be that same
for question no. 2
median wil be the answer because repeated element is one more than the
half of the no. of element
for finding medain we can use modified quick sort which uses the fact that
we have to go only one side depending on the no. of element we found on that
side.
in general algo
On Jan 25, 2008 11:47 PM, Sumedh Sakdeo [EMAIL PROTECTED] wrote:
*1) find the second biggest number in a given array of size n. you have to
use n+logn number of searches or less
By this you want to have a complexity less than or equal to n + log n
rite?
Consider an array { 17 , 4, 3, 18
#2 is weird, start by observing that if you've seen n/2+2 items then
you're done.
You want n/2+1 equal numbers. So there needs to be a number that is
repeated once after seeing n/2+2 numbers for this to be possible(and
the rest must all be the same), now divide and conquer. For all
possible
2.
keep a counter n
take the first element of the array say e and initialize the counter n=1
for each remaining number in the array
if n==0, e=current element, n=1
if current element is equal to e, n++
else n--
if n==0 there is no number
otherwise check the number of occurrences of e in the array
*1) find the second biggest number in a given array of size n. you have to
use n+logn number of searches or less
By this you want to have a complexity less than or equal to n + log n rite?
Consider an array { 17 , 4, 3, 18 , 9 , 15, 6 }
max1 max2 are index in array.
Iteration 1:-i=1 ( as
#2 is weird, start by observing that if you've seen n/2+2 items then
you're done.
You want n/2+1 equal numbers. So there needs to be a number that is
repeated once after seeing n/2+2 numbers for this to be possible(and
the rest must all be the same), now divide and conquer. For all
possible
22 matches
Mail list logo
