Page **2** of **3**

Posted: **Tue Sep 12, 2006 11:28 pm**

by **Martin Macko**

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:

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.

Posted: **Tue Sep 12, 2006 11:39 pm**

by **kp**

Among all pairs with minimum sum of values I always take the one with minimum first element. So my code passes your test case.

Posted: **Wed Sep 13, 2006 2:48 am**

by **mf**

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:

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

Posted: **Wed Sep 13, 2006 8:29 am**

by **kp**

Ok, I give up

Do you know some greedy that works?

Posted: **Wed Sep 13, 2006 10:27 am**

by **vinay**

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.

Posted: **Wed Sep 13, 2006 11:17 pm**

by **sclo**

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.

Posted: **Tue Sep 19, 2006 7:15 am**

by **Towhid**

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:

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.

Posted: **Wed Nov 15, 2006 5:23 am**

by **coolguy**

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

Posted: **Sat Nov 25, 2006 3:34 am**

by **coolguy**

got it accepted . no need 2 reply . thanx anywayz .

bye

### 11088(Backtracking)

Posted: **Sat Jun 23, 2007 7:39 pm**

by **sabir**

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.

### To sabir...

Posted: **Sat Jun 23, 2007 8:31 pm**

by **nymo**

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.

Posted: **Tue Jun 26, 2007 7:52 pm**

by **sabir**

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]

### To Sabir:

Posted: **Wed Jun 27, 2007 8:52 am**

by **nymo**

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.

Posted: **Fri Jun 29, 2007 7:02 pm**

by **sabir**

thnks, i will try.

Posted: **Sun Jul 01, 2007 7:33 pm**

by **lucky16g**

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?

thanks ahead