11088 - End up with More Teams

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Sep 12, 2006 11:28 pm

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

Post by kp » Tue Sep 12, 2006 11:39 pm

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:

Post by mf » Wed Sep 13, 2006 2:48 am

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

Post by kp » Wed Sep 13, 2006 8:29 am

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

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Wed Sep 13, 2006 10:27 am

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)
If I will myself do hashing, then who will do coding !!!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Sep 13, 2006 11:17 pm

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
Location: Bangladesh
Contact:

Post by Towhid » Tue Sep 19, 2006 7:15 am

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

Post by coolguy » Wed Nov 15, 2006 5:23 am

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

Post by coolguy » Sat Nov 25, 2006 3:34 am

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)

Post by sabir » Sat Jun 23, 2007 7:39 pm

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

Post by nymo » Sat Jun 23, 2007 8:31 pm

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

Post by sabir » Tue Jun 26, 2007 7:52 pm

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:

Post by nymo » Wed Jun 27, 2007 8:52 am

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

Post by sabir » Fri Jun 29, 2007 7:02 pm

thnks, i will try.

lucky16g
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm

Post by lucky16g » Sun Jul 01, 2007 7:33 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?

thanks ahead

Code: Select all

i give up this method

Post Reply

Return to “Volume 110 (11000-11099)”