TopCoder problem "DividingIntoTeams" used in East China Round 1 (Division I Level One)



Problem Statement

    

You want to form three teams from your friends. You have selected Alex, Bob and Charlie to be the captains of the first, second and third teams, respectively. You have n other friends, and you have numbered them from 1 to n.

You are given three int[]s, alexFriends, bobFriends and charlieFriends, representing the relations between the three captains and the other n friends. Each int[] contains exactly n elements, and is sorted in descending order by preference. The first element is the number of the captain's best friend - the person he would most want on his team. The last element is the number of the captain's worst friend - the person he would least want on his team.

The captains will pick their teams as follows. Alex selects a person, then Bob selects a person, then Charlie selects a person, and then the process continues starting from Alex again. The process ends after all the people have been selected. Each person can be selected only once. During each captain's turn, he will select the person he wants most among the people who have not yet been selected. Given an int k, return the name of the captain ("Alex", "Bob" or "Charlie", quotes for clarity) who will select person numbered k.

 

Definition

    
Class:DividingIntoTeams
Method:findYourTeam
Parameters:int[], int[], int[], int
Returns:String
Method signature:String findYourTeam(int[] alexFriends, int[] bobFriends, int[] charlieFriends, int k)
(be sure your method is public)
    
 

Constraints

-alexFriends, bobFriends and charlieFriends will each contain between 1 and 50 elements, inclusive.
-Each element of alexFriends, bobFriends and charlieFriends will be between 1 and n, inclusive, where n is the number of elements in alexFriends.
-All elements of alexFriends will be distinct.
-All elements of bobFriends will be distinct.
-All elements of charlieFriends will be distinct.
-k will be between 1 and n, inclusive.
 

Examples

0)
    
{1, 2, 3}
{1, 2, 3}
{1, 2, 3}
3
Returns: "Charlie"
In this case Alex selects friend with number 1, Bob - with number 2 and Charlie - with number 3. All the people have been selected, so the process ends.
1)
    
{1, 2, 3, 5, 4}
{3, 2, 1, 4, 5}
{2, 1, 5, 3, 4}
2
Returns: "Charlie"
In the first captain's turn Alex selects friend with number 1, Bob - with number 3 and Charlie - with number 2. In the second turn Alex selects friend with number 5, Bob - with number 4. All the people have been selected, so the process ends.
2)
    
{1, 2, 3, 4, 5}
{1, 3, 5, 4, 2}
{5, 4, 3, 2, 1}
4
Returns: "Bob"
3)
    
{1}
{1}
{1}
1
Returns: "Alex"
4)
    
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
{1, 8, 9, 4, 5, 6, 7, 3, 2, 10}
{9, 10, 8, 4, 5, 7, 6, 1, 2, 3}
4
Returns: "Bob"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8787

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12226&pm=8787

Writer:

DStepanenko

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Simulation