11088 - End up with More Teams

[Martin Macko]

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]

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]

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]

Ok, I give up
Do you know some greedy that works?

[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.

[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.

[Towhid]

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.

[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

[coolguy]

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

[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.

[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.

[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]

[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.

[sabir]

thnks, i will try.

[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

Code: Select all

i give up this method