TopCoder Problem Statement - PickTeam
Choose the most effective team based on how well individuals work together.
001: /*
002: * TopCoder Single Round Match: 153
003: * Division: 2
004: * Level: 3
005: * Points: 1000
006: * Problem Statement: http://community.topcoder.com/stat?c=problem_statement&pm=1773
007: */
008:
009: import java.util.*;
010:
011: public class PickTeam {
012:
013: /*
014: * This method converts the String[] people in a List of Perosn objects
015: */
016: private static List getAllPeople(String[] people) {
017:
018: List l = new ArrayList<>();
019:
020: for (int i = 0; i < people.length; i++) {
021: Person p = new Person(i, people[i].split(" "));
022: l.add(p);
023: }
024:
025: return l;
026:
027: }
028:
029: /*
030: * Returns a set of all possible teams given the list of people and the
031: * desired team size.
032: */
033: private static Set getAllTeams(List allPeople,
034: int size) {
035:
036: // This is the set we'll return.
037: Set teams = new HashSet<>();
038:
039: /*
040: * Check that we have people to work with, and that the desired team
041: * size is not more than the number of people available.
042: */
043: if ((allPeople == null) || (allPeople.size() == 0) ||
044: (size > allPeople.size())) {
045: return teams;
046: }
047:
048: /*
049: * If the desired team size is 1. Then everyone get their own team.
050: */
051: if (size == 1) {
052: for (Person p : allPeople) {
053: Team t = new Team();
054: t.addTeamMember(p);
055: teams.add(t);
056: }
057: return teams;
058: }
059:
060: // Copies the list of allPeople
061: List currentPeople = new ArrayList<>();
062: currentPeople.addAll(allPeople);
063:
064: /*
065: * For each person, we'll call getAllTeams() will all of the remaining
066: * people
067: */
068: for (int i=0; i allPeople = getAllPeople(people);
069:
070: // Get a set of all possible teams
071: Set allTeams = getAllTeams(allPeople, teamSize);
072:
073: int maxScore = Integer.MIN_VALUE;
074: Team bestTeam = null;
075:
076: // Find the team with the greatest score.
077: for (Team team : allTeams) {
078: int score = team.getScore();
079: if (score > maxScore) {
080: maxScore = score;
081: bestTeam = team;
082: }
083: }
084:
085: return bestTeam.getNames();
086: }
087: }
088:
089: /*
090: * The Team class holds a set of Person which represents the people on the
091: * team. Also provide methods for calculating the score, and displaying
092: * the team members in the format expected by the tests.
093: */
094: class Team {
095:
096: Set teamMembers = new HashSet<>();
097:
098: // Calculates the score for the team.
099: public int getScore() {
100:
101: int score = 0;
102:
103: for (Person p : teamMembers) {
104: for (Person p1 : teamMembers) {
105: score += p.getCompatibility(p1);
106: }
107: }
108:
109: return score;
110: }
111:
112: // Returns the team member's names as a sorted array.
113: public String[] getNames() {
114:
115: String[] names = new String[teamMembers.size()];
116:
117: int i = 0;
118: for (Person p : teamMembers) {
119: names[i++] = p.name;
120: }
121:
122: Arrays.sort(names);
123: return names;
124: }
125:
126: public void addTeamMember(Person p) {
127: teamMembers.add(p);
128: }
129:
130: }
131:
132: class Person {
133:
134: final int id;
135: final String name;
136: final Map compatibilityMap = new HashMap();
137:
138: Person(int id, String[] data) {
139:
140: this.id = id;
141: name = data[0];
142:
143: for (int i = 1; i < data.length; i++) {
144: compatibilityMap.put((i - 1), Integer.parseInt(data[i]));
145: }
146: }
147:
148: // Returns an int representing how compatible this person is with the other.
149: public int getCompatibility(Person p) {
150: return compatibilityMap.get(p.id);
151: }
152:
153: }
The problem asks us to create the best possible team by selecting from a pool of individuals. Each individual has a set of scores which represent how compatible they are with each other individual. The team's score is determinined by summing the compatibility ratings for each person on the team with every other team member. The team with the highest score should be selected.
The solution use two inner classes to help represent the data: Person and Team. Person stores the person's name, an ID (which comes in handy since people may have the same name), and a Map that maps another Person's ID to their compatibility score.
Team holds a set of Person objects, and has methods for adding new team mebers, generating the required return value for the winning team, and calculating the score.
The hardest part of this problem, is coming up with the set of all possible teams - this is handled by the getAllTeams() method. The method works by iterating through the list of all people. For each person, getAllTeams() is called with a list of all people that come after the current person, and a team size that's decremented by one. For each of the teams returned, the current person is added to the team, and that team is added to the set that gets returned. The recursion continues until the size of the desired team is 1, in which case each person in the list of allPeople is effectively their own team.
The number of teams is small enough that this brute force approach is possible. Although, the code, as given may fail one of the test for taking more that 2 seconds. It ran in 0.6 seconds on my machine, so I'm not too concerned. I've written essentially the same algorithm in C, and it passed easily.
Once a Set of all possible teams is obtained, it's a simple matter of calculating the score for each team, and keeping track of which team has the highest.
No comments:
Post a Comment