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 methods are 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
|
|
|
No comments:
Post a Comment