@Abhishek,
I think your logic will not work. Although it can be done by greedy
approach, but your method needs some tweak.
Consider the case : 1,2,3,4,5,12
with your logic, we will get this answer
team 1: 1,3,5 (total=9)
team 2: 2,4,12(total=18)
difference is 9 and its huge.
what can be done is after sorting the array, keep track of the sum of all
elements in 2 variables for the 2 teams and keep assigning the next
element(in decreasing order) to the one with less sum, and update the sum.
Finally if the number of elements are not balanced for the 2 teams, transfer
the bottom diff/2 elements to the other team to make it balance ( where diff
is the difference in the number of elements in 2 teams)
Ex: for array: 1,2,3,4,5,12
sort in descending order in O(nlogn): 12,5,4,3,2,1
initially:
teamA={}, teamB={}
sumA=0, sumB=0
iteration 1:
teamA={12}, teamB={}
sumA=12, sumB=0
iteration 2:
teamA={12}, teamB={5}
sumA=12, sumB=5
iteration 3:
teamA={12}, teamB={5,4}
sumA=12, sumB=9
iteration 4:
teamA={12}, teamB={5,4,3}
sumA=12, sumB=12
iteration 5:
teamA={12,1}, teamB={5,4,3}
sumA=13, sumB=12
iteration 6:
teamA={12,1}, teamB={5,4,3,2}
sumA=13, sumB=14
now since the elements are not balanced in 2 arrays we need to transfer
lowest the (4-2)/2= 1 element from teamB to teamA i.e. transfer element 2 in
this case
final result:
teamA={12,1,2}, teamB={5,4,3}
sumA=15, sumB=12
difference is 3 unlike 9 in your case.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Mon, May 31, 2010 at 5:54 AM, sharad kumar <aryansmit3...@gmail.com>wrote:
> @abhishek:i meant after sorting split the array into 2 part each with
> equal sum....
>
> On Sun, May 30, 2010 at 11:45 PM, Abhishek Sharma
> <jkabhishe...@gmail.com>wrote:
>
>> @sharad: if you find the subarrays of equal sum then the number of players
>> might differ in the team... also can you tell me how will you do
>> that..according to me time cmoplexity will be higher..
>>
>> According to me:
>> sort the palyers based on skill points (O(nlogn) --mergesort) then assign
>> the players one by one to each team (O(n))
>>
>> Ex: Consider 10 players to be assigned to two teams.
>> skill points: 12, 12, 7, 8, 15, 19, 11, 14, 5, 10.
>>
>> Ans:
>> after sorting: 5, 7, 8, 10, 11, 12, 12, 14, 15, 19.
>> Team1: 5, 8, 12, 14, 19
>> Team2: 7, 11,12,15.
>>
>> This is not exactly even but i think is the closest approach.
>> correct me if I am wrong..
>>
>> Regards,
>> Abhishek
>>
>> On Sun, May 30, 2010 at 8:21 PM, sharad kumar <aryansmit3...@gmail.com>wrote:
>>
>>> sort the players based on skill point and get the subarray of equal
>>> sum......
>>>
>>>
>>> On Sun, May 30, 2010 at 6:58 PM, Veer Sharma
>>> <thisisv...@rediffmail.com>wrote:
>>>
>>>> Hi Friends,
>>>>
>>>> This is my first post to this forum. A "Hi" to all of you and here is
>>>> my first problem...
>>>>
>>>> Giiven int n, the total number of players and their skill-point.
>>>> Distribute the players on 2 evenly balanced teams.
>>>>
>>>> Lets see who gives the best solution (least space complexity / least
>>>> time complexity or both...)
>>>>
>>>> --
>>>> 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.
>>>>
>>>>
>>>
>>>
>>> --
>>> yezhu malai vaasa venkataramana Govinda Govinda
>>>
>>> --
>>> 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.
>>>
>>
>> --
>> 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.
>>
>
>
>
> --
> yezhu malai vaasa venkataramana Govinda Govinda
>
> --
> 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.
>
--
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.
