PROBLEM STATEMENT
You are throwing a party at a club and are hiring promoters to help you get
people to attend. The promoters you deal with want you to pay them ahead of
time, but they will guarantee the amount of people they will bring. Since you
only have a certain amount of cash on hand you need a program to decide how to
get the most people to attend for your money. Another issue is that each
promoter will only work with his friends, so if two promoters aren't friends
directly or indirectly they cannot work together. Given how much each promoter
costs, the number of people they will bring, who they're directly friends with,
and how much money you have on hand determine the maximum number of people that
can attend your party. For example:
costs = {10,20,30,10}
people = {20,10,40,30}
friends = {"0 1","1 2"} (i.e. 0 and 1 are friends, 1 and 2 are friends)
money = 35
There are 4 promoters. Promoter 0 costs 10 dollars, will bring 20 people and
is friends with promoter 1 and 2. Promoter 1 costs 20 dollars, will bring 10
people and is friends with promoter 0 and 2. Promoter 2 costs 30 dollars, will
bring 40 people and is friend with promoter 0 and 1. Promoter 3 costs 10
dollars, will bring 30 people and is friends with nobody.
You have 35 dollars on hand so you have to choose between two promoters(0 & 1)
for 10 and 20 dollars, one promoter(2) for 30 dollars, or one promoter(3) for
10 dollars. Promoter 2 gets you the most people for your money. Method
returns 40.
To further clarify the friends issue:
1) If promoter A is friends with promoter B then promoter A is automatically
friends with all of promoter B's friends. This means 2 promoters are friends
as long as their exists some chain of friendship between them.
2) Friendship is two-way so if promoter A is friends with promoter B then
promoter B is automatically friends with promoter A. For example, if there are
4 promoters and friends = {"0 1","0 2","1 3"} this means that all promoters are
friends with each other.
Create a class PartyPromo that contains the method maxPeople, which takes an
int[] costs, an int[] people, a String[] friends, and an int money and returns
the maximum number of people you can get to attend.
DEFINITION
Class: PartyPromo
Method: maxPeople
Parameters: int[], int[], String[], int
Returns: int
Method signature (be sure your method is public): int maxPeople(int[] costs,
int[] people, String[] friends, int money);
NOTES
- Promoter K will have a cost of costs[K] and will bring an amount of people
equal to people[K]
- When referring to promoters the numbers are 0-based so for example, promoter
2 is the third promoter
- If friends contains the String "A B" then promoter A is friends with promoter
B and vice versa
- You can use a single promoter at most 1 time (i.e. you can't buy the same
promoter more than once)
- Friends may contain repeats, but the repeated instances can be ignored
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- costs will contain between 1 and 50 elements inclusive
- Each element of costs will be between 0 and 1000
- people will contain between 1 and 50 elements inclusive
- people and costs will contain the same number of elements
- Each element of people will be between 0 and 10000 inclusive
- friends will contain between 0 and 50 elements inclusive
- Each element of friends will be of the format "A B" (quotes for clarity) such
that:
A is not equal to B
A and B are separated by a single space
A is between 0 and (number of elements in people -1) inclusive
B is between 0 and (number of elements in people -1) inclusive
A and B will not contain any leading zeros
- Each element of friends will contain no leading or trailing white space
- money will be between 0 and 100000 inclusive
EXAMPLES
1) costs = {10,20,30,10}
people = {20,10,40,30}
friends = {"0 1","1 2"}
money = 35
This is the example from above. Method returns 40.
2) costs = {10,20,30,10}
people = {20,10,40,30}
friends = {"0 1","0 2","3 2","0 1"}
money = 35
This is the same as example 1 but now everyone is friends. We can now choose
promoters 0 and 3. Method returns 50.
3) costs = {0,10,400,50,20}
people = {20,30,100,0,10}
friends = {"0 1","2 1","1 2","2 3","3 4"}
money = 399
Everyone is friends with each other so any set of promoters that fit into the
cost structure can be chosen. The promoter for 400 is too expensive so we end
up taking everyone else. Method returns 60.
4) costs = {10,20,30,40,50,60,70,80,90,100}
people = {10,20,30,40,50,60,70,80,90,0}
friends = {"0 1","1 2","2 3","3 4","4 5","5 6","6 7","7 8","8 9"}
money = 480
Method returns 450.
5) costs = {10,20,30,40,50,60,70,80,90,100}
people = {10,20,30,40,50,60,70,80,90,100}
friends = {"0 1","1 2","2 3","3 4","5 6","6 7","7 8","8 9"}
money = 480
Method returns 400.
6) costs = {0,50,0,100,0}
people = {40,20,50,10,30}
friends = {"2 4"}
money = 0
Method returns 80.
7) costs = {20,90,100}
people = {20,90,100}
friends = {}
money = 0
Method returns 0.