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:

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.

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:

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.

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. 8)

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:

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.

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

Code: Select all

i give up this method