## 11088 - End up with More Teams

Moderator: Board moderators

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
kp wrote:I solved it using both DP and greedy.

Greedy is as follows:
1. Take one guy with maximum value
2. Take two appropriate guys with minimum sum of values

However, I have not proved it.
This greedy should not pass the judge, as it does not work for the following input:

Code: Select all

``````9
8 8 7 7 7 7 6 6 4
0``````
In the first step the greedy can take 8+6+6 and form only two teams. (The other one would be 8+7+7). However, if it started with 8+8+4, it could form three teams.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Among all pairs with minimum sum of values I always take the one with minimum first element. So my code passes your test case.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
kp wrote:Among all pairs with minimum sum of values I always take the one with minimum first element. So my code passes your test case.
It fails this test case:

Code: Select all

``````7
2 4 6 6 7 9 9``````
Your greedy would choose 9,2,9 as the first team, and wouldn't be able to make a second team.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Ok, I give up
Do you know some greedy that works?

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
there shouldn't be one...
I can't see how to take the decision greedily...
u have to just keep the sum >=20...
and maximize the no. of groups..
it has got overlapping sub-problems... so dp
but doesn't seem to have a greedy solution.. as far as I worked on it.
If I will myself do hashing, then who will do coding !!!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I think the only greedy decision that works is to always pick the largest value, then the other 2 values must be picked by brute force.

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Contact:
mf wrote:
kp wrote:Among all pairs with minimum sum of values I always take the one with minimum first element. So my code passes your test case.
It fails this test case:

Code: Select all

``````7
2 4 6 6 7 9 9``````
Your greedy would choose 9,2,9 as the first team, and wouldn't be able to make a second team.
But When there are 7 persons, I know I can form at most 2 teams. So, I use only the higher 6 persons and ignore the person with value 2. I think, the greedy works nicely.
From 0 to 0

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm
Im having trouble formulating the DP , the order of my dp is bigger den most of urs , it is O( 2^n * n^3 ) ......
2^n for da state and n^ 3 for choosing the 3 members . i think there is an efficient way of implementing this dp could anyone please show me da right way to do this dp ........
bye bye
In good company

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm
got it accepted . no need 2 reply . thanx anywayz .
bye
In good company

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

### 11088(Backtracking)

can any one give me any hint how to solve this prob using backtracking,
i tried but ...i read prev all post but do not get any idea about bracktracking solution.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### To sabir...

To sabir:
The recurrence I use is ...Best[S] = max(Best[S - SiSjSk] + 1/0); S is the whole set and Si, Sj, Sk are three team members... if they are good to form a team, it counts as 1 and 0 otherwise.
regards,
nymo

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am
thanks nymo for ur reply.but i do not understand full.can u explain more
detail. what u mean by max(Best[S - SiSjSk])

sorry for poor english.
[YOU CAN NOT CHANGE YOUR FATE]

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### To Sabir:

Hi,
We are looking for the maximum number of promising teams that can be formed. Key observation is Constraint - n ≤ 15. So, we can use bitmasks quite easily to donote contestants i.e. one bit for one contestant. Now you just need to write a nice recursive function which tries the recurrence...

Code: Select all

``````Best(S) = max(Best(S - SiSjSk) + 1/0);
``````
Here, S denotes the contestants. Say, for n=5; you mark bits 0 to 4 providing S is just an integer. Then you take all combinations of three contestants [SiSjSk] and if their ability points put up greater or equal 20, you take one team and tries to find out Best(S - SiSjSk) which will return the maximum number of promising teams if you leave from the initial set the three members you just took.

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am
thnks, i will try.

lucky16g
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm
Greedy is as follows:
1. Take one guy with maximum value
2. Take two appropriate guys with minimum sum of values

i have try the mothod to sove it, but

wa
can any one help me?

``````i give up this method