JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: 2011 TCO Marathon Championship Round
Problem: OptimalScheduling

Problem Statement

    N teams are expected to compete in a weekend-long regional FIRST robotics event. Over the weekend, each of the N teams will compete in M official matches. All of the matches will be held on a single field with a fixed delay between the matches. It can be assumed that each match takes no time and 1 unit of time passes between consecutive matches.



6 different teams compete in each match. They are divided into 2 alliances called Alliance 1 and Alliance 2. Each of the alliances contains 3 teams. Each team within an alliance plays at a certain position. These positions are called Position 1, Position 2 and Position 3.



For each of the N teams, the following information is available:
  • Unique team number.
  • Number of years within the FIRST organization. In the rest of the statement it will be called "age".
  • Rank of the team based on previous experience. It is an integer within 1..10. Higher rank means stronger team. For example, 1 is "unknown/rookie" and 10 is "winner from previous year or week".
In the event when N*M is not a multiple of 6, it is impossible to create a schedule where each team competes in exactly M matches. In this case the concept of fill-in teams is used. Let K be the smallest integer such that N*M+K is a multiple of 6. The event organizers will choose K out of N teams, these teams are called fill-in teams. Each fill-in team will need to play M+1 matches instead of M. The 3rd (1-based) chronological match for a fill-in team is considered to be a fill-in match. All other matches (i.e., 1st, 2nd, 4th, 5th, ...) for a fill-in team are official matches.



For an event schedule, a number of important metrics can be defined. These metrics are described in details below. Your task is to construct a schedule which minimizes the weighted sum of these metrics (where the weights are provided to your solution as an input parameter).



Quality metrics for a schedule.



Let us number all matches chronologically 0, 1, ..., G-1, where G = ceil((N * M) / 6) is the overall count of matches.



The following 7 quality metrics for a schedule are considered to be important in this problem:
  • Age difference metric. For match i, let A(i) and B(i) be the (arithmetic) average age of teams from Alliance 1 and Alliance 2, respectively. This metric is defined as the sum of abs(A(i) - B(i)), over all i, 0 <= i < G. (abs(x) denotes the absolute value of x.)
  • Rank difference metric. For match i, let A(i) and B(i) be the average rank of teams from Alliance 1 and Alliance 2, respectively. This metric is defined as the sum of abs(A(i) - B(i)), over all i, 0 <= i < G.
  • "Unique partner" fit metric. Consider a certain team T. Let A be the number of different teams with which team T played in the same alliance (considering only matches that are official for team T, but not considering the fill-in match, if there is such for team T). The value of this metric for team T is 2*M-A. The overall value of the metric is the sum of its values for each team.
  • "Unique challenger" fit metric. Consider a team T. Let A be the number of different teams with which T played in the same match, but in different alliances (considering only matches that are official for team T). The value of this metric for team T is 3*M-A. The overall value of the metric is the sum of its values for each team.
  • "Match time" fit metric. Consider a team T. Suppose it played in Q matches (including the fill-in match, if there is such for team T, so Q = M or Q = M+1). Let t[0] < t[1] < ... < t[Q-1] be the numbers of these matches in ascending order. We can define the time d[i] between i-th and (i+1)-th matches as d[i] = t[i+1] - t[i] - 1. The ideal time idt between matches is defined as idt = G/Q - 1 (the division is exact, so in general case idt is not an integer). The value of this metric for team T is the sum of abs(d[i] - idt), over all i, 0 <= i <= Q-2. The overall value of the metric is the sum of its values for each team.
  • Alliance 1/Alliance 2 assignment metric. Consider a team T. Let A and B be the number of matches where T played in Alliance 1 and Alliance 2, respectively (considering only matches that are official for team T). The value of this metric for team T is abs(A - B). The overall value of the metric is the sum of its values for each team.
  • "Alliance position" fit metric. Consider a team T. In each match it can play in one of 6 alliance/position combinations: Alliance 1/Position 1, Alliance 1/Position 2, Alliance 1/Position 3, Alliance 2/Position 1, Alliance 2/Position 2, Alliance 2/Position 3. We can number these combinations 0 to 5 in arbitrary order. Let C[i], 0 <= i < 6, be the number of matches where team T plays in combination i (considering only matches that are official for team T). The value of this metric for team T is the standard deviation of the sample C[0], C[1], ..., C[5]. More exactly, let avg(C) be defined as avg(C)=(C[0]+C[1]+...+C[5])/6 (exact division). Then the metric's value is the square root of ((C[0]-avg(C))^2 + (C[1]-avg(C))^2 + ... + (C[5]-avg(C))^2) / 6. The overall value of the metric is the sum of its values for each team.
Additionally, there is a bonus for schedules where there are no matches that are not official for more than 1 team. See the scoring section for details.



Input and output data. Scoring.



You will need to implement a method createSchedule. The following parameters will be provided as input to the method:
  • N -- the number of teams.
  • M -- the number of official matches that each team must play.
  • Z -- an array that describes teams. It will contain exactly N elements. Each element will represent a single team and will be formatted "NUM AGE RANK" (quotes for clarity). Here NUM, AGE and RANK are integers representing team's number, age and rank, correspondingly.
  • W -- an array that contains 7 integers being weights for the 7 metrics defined above.
  • S -- an array describing teams that must play fill-in matches. It will contain exactly K elements where K is the amount of fill-in teams. Each element will represent a single team and will be a team's number. It is guaranteed that team with such number is contained in Z.
Your method must return the schedule you have found as a String[]. It must contain exactly G elements, where G is the total number of matches. The i-th element (0-based) must represent the i-th cronologically match played. It must be formatted "A B C : D E F" (quotes for clarity), where A, B, C are the numbers of teams that play as Alliance 1/Position 1, Alliance 1/Position 2, Alliance 1/Position 3, correspondingly, and D, E, F are the numbers of teams that play as Alliance 2/Position 1, Alliance 2/Position 2 and Alliance 2/Position 3, correspondingly.



In order to get a score for a testcase, the schedule must be correct (6 distinct teams in each match; each team from S plays M+1 matches, each other team plays M matches). A failure to return anything or returning an incorrect schedule will be indicated using a score of -1. Otherwise the score for a test case is equal to W[0] * (age difference metric) + W[1] * (rank difference metric) + W[2] * ("unique partner" fit metric) + W[3] * ("unique challenger" fit metric) + W[4] * ("match time" fit metric) + W[5] * (Alliance 1/Alliance 2 assignment metric) + W[6] * ("alliance position" fit metric).



If the returned schedule is such that each match is official for at least 5 out of 6 participating teams, the additional bonus is applied: the score gets reduced by 5% (i.e., it is multipled by 0.95).



The normalized score for a test case is defined as Best / Your, where Best is the best score achieved for the test case by all competitors and Your is your score for this test case. In case Your is 0.0, the normalized score is equal to 1. In case Your is -1.0, the normalized score is equal to 0. If no competitors obtained a correct schedule for a test case, then normalized scores of all competitors for this test case are 0. Your overall score is the sum of normalized scores over all test cases.



Test case generation.



Each test case will be generated as follows (each occurence of "randomly" assumes uniform distribution, unless otherwise specified):
  • N will be chosen randomly between 40 and 64, inclusive.
  • M will be chosen depending on N. M=9 for N >= 60. M=10 for 50 <= N < 60. M=11 for 45 <= N < 50. M=12 for N < 45.
  • Z will be populated randomly from the following list of 2065 teams. The file is in TSV format. Each line represents a single team and contains 3 integers separated with tabulation characters. The first integer is team number, the second is age and the third is rank.
  • Each element of W will be chosen randomly. The limits are as follows: 0 <= W[0] <= 200, 0 <= W[1] <= 700, 300 <= W[2] <= 900, 300 <= W[3] <= 900, 500 <= W[4] <= 900, 100 <= W[5] <= 300, 0 <= W[6] <= 700.
  • S will be populated randomly from Z.
Tools



A tester is provided for offline testing. You can check its source code for a precise implementation of test case generation and scoring calculation.
 

Definition

    
Class:OptimalScheduling
Method:createSchedule
Parameters:int, int, String[], int[], int[]
Returns:String[]
Method signature:String[] createSchedule(int N, int M, String[] Z, int[] W, int[] S)
(be sure your method is public)
    
 

Notes

-The time limit is 10 seconds per single test case (which includes only the time spent in your code), the memory limit is 1024 MB.
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-The processing server specifications can be found here.
-There are 10 example and 100 full submission test cases.
 

Constraints

-All parameters will be generated exactly as described in section "Test case generation" of the problem statement.
 

Examples

0)
    
N = 40
M = 12
W = {171,131,392,471,658,139,415}
0 fill-in teams
1)
    
N = 63
M = 9
W = {134,70,824,455,522,290,177}
3 fill-in teams
2)
    
N = 58
M = 10
W = {54,18,556,447,760,226,22}
2 fill-in teams
3)
    
N = 45
M = 11
W = {133,621,364,374,641,200,352}
3 fill-in teams
4)
    
N = 41
M = 12
W = {124,254,634,510,745,238,640}
0 fill-in teams
5)
    
N = 46
M = 11
W = {81,75,482,630,820,286,83}
4 fill-in teams
6)
    
N = 49
M = 11
W = {105,408,311,604,585,105,281}
1 fill-in teams
7)
    
N = 60
M = 9
W = {170,602,899,714,732,175,209}
0 fill-in teams
8)
    
N = 62
M = 9
W = {136,228,304,498,597,145,378}
0 fill-in teams
9)
    
N = 60
M = 9
W = {113,466,546,365,630,148,74}
0 fill-in teams

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.