JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 101: World Cup MM
Problem: WorldCupLineup

Problem Statement

    

Overview

In the game of soccer (often also known as "football" outside of the United States), a team has ten players and one goalkeeper on the field. A good coach seeks to maximize the effectiveness of their team. Different players may be more or less skilled at different positions, and in some cases, certain groups of players on the field may work especially well together.

Players are classified into three high-level positions: Forward, Midfield, and Defender. Midfield players, as their name implies, can move forward offensively, or pull back for defensive play. Occasionally, players may not be able to play the entire duration of a game. In some cases, an injury can happen. Other times, a player may behave with some indiscretion and find themselves shown a penalty card: yellow, for the first offense, as a warning, and red the second time around, resulting in their dismissal from play. As this possibility of having to replace players is very real, a lineup plan also involves having backup players planned.

For purposes of our simulation, each player is described by three status values: offensive attack, defensive skill, and aggression. For players in a forward position, the attack stat is used at double its value, but the defensive stat is ignored. For defenders, the defensive stat is used at double its value, but the attack stat is ignored. For midfield players, both stats are used at their nominal values. The aggresion stat is used as-is regardless of position, and refers to the chances of a given player being shown a card (see below) during each iteration.

There may additionally be several groups of players, also described by those stat values. When all players of a group are on the field together, their individual status values are all adjusted by the group stat values (which may potentially be negative).

Method Description

The input String[] players describes each player on the team in terms of the three statistics described above. Each element will be three integer values separated by commas, in the form "ATK,DEF,AGG" (quotes added for clarity). The input String[] groups will have two comma-delimited lists of integers: the first being the indexes of two or more players in the group, the second being the stats applied to that group; the form will be "P1,P2,...,Pn ATK,DEF,AGG".

Your return should be a String[] consisting of exactly ten elements. The first character of each element should be "F", "M" or "D", indicating if that position will be used as forward, midfield, or defense, respectively. The second character should be a space. After that should follow a comma-delimited list of player indexes of the players that will be used (in order of preference) to fill that position, with later players from the list being used for replacement due to injury or ejection. An example might look like "F 1,3,7". Note that it is permissible to not assign any players to a given position. (See next paragraph.)

If any of the 10 positions should not have any available players to fill the position, that position will be filled with a generic player having all stats of 0, and not being part of any group.

Constraints

  • Each team has exactly 30 players listed
  • There will be up to 50 groups, each with at least two players
  • Atk and Def for each player will be selected in the range 0..99
  • Agg for each player will be selected in the range 0..49
  • For each group, atk, def, and agg will each be selected in the range -25..25
  • For each test case, the injury rate (chance of each individual player getting injured at each of the four checks) will be 0..0.05

Scoring

The effectiveness of a team is simulated by calculating overall attack and defensive skill of all players on the field, and calculating MIN(ATTACK, DEFENSE). This calculation will take place exactly five times: at the start of a game, midway through the first half, at halftime, midway through the second half, and at the end of the game.

Over four iterations, the effects of play on the team (e.g. loss of players through injury or penalty) shall be computed. Thus, the team effectiveness will be calculated after 0, 1, 2, 3 and 4 iterations of player loss.

Your raw score for a given test case will be the sum of your effectiveness at each of the five measurement times, with a minimum score of 0 for a solution that returns a valid output and runs properly. Your overall score will be based on rank scoring. For each test case, you will score 1 point for each other competitior your score beats, and 0.5 points for each tie. That total will be summed over all test cases, divided by (# test cases) * (# competitors - 1), and scaled to 1000000.

Offline Tester

An offline tester for this contest is available here.

Notes

  • Time limit is 10s per test case
  • Memory limit is 1GB
  • There are 10 example tests and 100 provisional tests
 

Definition

    
Class:WorldCupLineup
Method:selectPositions
Parameters:String[], String[]
Returns:String[]
Method signature:String[] selectPositions(String[] players, String[] groups)
(be sure your method is public)
    
 

Examples

0)
    
Players:
60,95,6
11,76,30
28,85,46
11,27,44
97,25,49
12,58,39
41,95,8
89,27,1
29,40,28
6,1,26
36,32,17
86,15,19
63,62,19
78,32,9
60,99,31
23,28,11
85,9,5
40,95,45
27,11,17
68,75,38
39,1,32
36,0,22
59,20,49
98,76,46
28,91,35
52,68,40
42,35,1
52,31,17
31,86,49
59,34,3

Groups:
16,22 -23,12,-2
18,28 -5,-12,1
16,27 20,-15,12
2,6,25,29 23,-3,23
8,18,23,24 8,-20,-16
8,11,12,24 11,-14,-11
10,24 19,-25,-9
0,3,13,21 7,12,-12
2,17 7,13,-1
2,8,21 13,10,-3
15,16,26 23,-10,13
6,28 14,20,9
9,13,15,16 19,-4,23
22,25 -22,-24,-10
9,23,28 -14,-16,-9
5,15 23,7,13
13,17,19 -14,9,-2
0,6 25,-21,16
8,20,21,22,29 10,-24,24
11,29 -1,8,-10
0,12,18 -9,-10,-10
20,22,23,24 0,10,4
1)
    
Players:
91,15,42
99,44,6
28,44,5
39,40,37
16,10,36
90,9,47
68,55,25
87,41,6
46,10,47
42,62,44
30,62,38
9,0,10
30,79,4
56,27,47
9,40,24
8,93,11
78,99,42
14,44,0
79,19,18
97,11,22
18,69,28
69,36,7
8,81,43
47,97,20
29,0,11
38,73,12
94,81,40
34,89,6
99,42,16
36,88,6

Groups:
0,3,4,16,26 0,10,-10
10,27 21,-9,-19
8,17,24,27 -10,-17,-22
3,21,23 -15,-10,-6
17,24 7,24,25
4,29 3,-25,-24
9,11,28 -23,-17,11
8,24,29 19,3,12
0,25 6,-23,16
10,16 -9,21,-11
1,8,17 19,3,-22
5,27 11,-24,-17
5,18,29 8,4,-18
0,7,26 -20,-22,1
14,17,24,26 -24,25,-2
8,11,25 -10,17,-17
2)
    
Players:
52,18,30
54,2,31
21,73,46
54,90,0
24,69,22
89,0,40
21,18,44
92,5,9
2,89,6
82,63,31
0,55,12
27,41,7
97,60,20
25,95,34
20,96,36
35,34,5
32,0,34
14,22,43
91,47,14
75,48,19
92,17,27
84,53,22
56,91,15
57,70,14
33,17,35
22,42,34
62,43,36
15,57,41
90,32,31
93,60,41

Groups:
1,17 -11,20,24
8,18,26 -23,1,25
2,13,15,17,22,29 -10,-20,-25
0,21,26 -7,-15,13
8,20,22 0,-11,2
5,26 6,8,-3
1,3,22 -3,10,-21
2,4,5,6,9 -7,6,11
11,13,19 -24,5,-21
14,28,29 -18,-16,16
12,29 2,19,16
9,13,15,17,25 4,-2,13
0,4 18,-12,23
7,24 -8,21,24
15,20 -10,17,19
0,3 -13,8,-7
3,22 -19,-11,-10
3)
    
Players:
49,62,18
10,65,6
93,48,30
6,47,19
33,83,14
66,28,22
29,51,10
18,71,9
91,31,21
23,19,6
39,94,23
21,68,25
61,9,20
69,95,11
90,8,14
56,77,32
73,8,0
91,46,39
80,52,23
25,59,48
4,54,28
13,92,48
78,77,11
53,60,45
88,87,38
90,91,37
75,19,38
61,83,5
45,54,6
84,28,17

Groups:
0,10,16 -11,-12,1
5,24 -3,-21,-13
22,27 -2,8,-7
3,16 -4,-10,-17
13,14,16,27 -8,-14,21
0,6 21,-18,-22
15,17 14,11,18
10,12 -19,-8,-2
0,10,21,22 -4,-2,17
4)
    
Players:
41,97,2
49,55,32
80,40,46
15,86,34
58,15,12
48,55,46
68,40,8
8,45,43
3,97,39
89,76,32
80,85,26
44,27,2
26,89,14
68,34,31
67,21,3
8,75,23
8,71,7
89,7,35
35,99,22
30,6,36
89,17,31
70,8,11
17,44,26
61,26,15
28,37,21
83,77,39
69,19,14
78,18,47
62,88,43
77,0,4

Groups:
0,5,8,16 -6,9,-4
1,9 10,-14,-3
11,13,14 -18,7,-8
15,16,22,24,27 -15,-6,-3
11,13,20 14,-8,-25
14,24 18,4,-18
1,12,19 24,13,-23
1,2,3,8,28 -16,-16,17
4,7 16,-11,-6
5,12,23,27,28 9,-11,1
5,16 21,-25,-22
9,26 -25,-20,25
0,6 -20,-9,11
1,8,12,28 22,-10,12
13,18,27 15,10,-6
4,8,10,20,25 22,-2,-11
13,29 -9,-20,22
10,16,23 8,-12,-23
14,26 1,-8,-21
3,25 7,25,-19
0,7,10,20,25 18,-7,16
19,25 -24,-22,-10
24,28 25,0,-13
16,18 -12,10,24
9,14 9,13,25
15,26 -25,10,6
0,13,25 -6,-9,22
2,8 17,10,20
5,11 10,5,-20
13,18 -19,23,-23
20,23 0,-11,5
2,18,19,21 9,12,-3
4,7,20 10,-2,1
2,6,11 19,6,15
6,17 -4,-7,7
10,16,22,24,25 18,8,11
11,19 13,-16,-24
1,13,24 -25,-9,-1
6,7,10,15 21,-19,11
2,27 3,25,-23
11,24,26 -20,-6,-3
0,13,26 8,16,-18
26,28 23,-4,-1
6,21 3,6,-5
8,12,14,18,24,28 8,10,18
19,27,29 0,7,-2
18,28 -15,5,7
12,27 11,-4,18
5)
    
Players:
82,45,7
85,94,12
16,42,0
97,32,13
45,55,43
18,81,31
11,70,7
58,99,16
44,14,40
45,53,21
15,30,27
41,9,0
70,74,49
82,55,36
81,57,47
0,0,24
75,78,45
55,72,38
77,92,9
79,25,9
3,61,9
21,9,1
79,17,35
33,38,35
81,52,44
55,19,28
42,91,16
32,48,1
35,80,19
33,42,2

Groups:
4,8,10,20,26,28 19,11,-12
4,13,18,25,29 0,-6,-10
6)
    
Players:
81,46,10
69,80,26
80,90,2
89,75,33
87,95,49
15,40,9
9,51,8
44,69,44
15,14,19
64,28,16
72,76,42
27,61,42
96,53,45
46,9,7
24,6,34
23,7,16
20,20,44
45,58,8
8,14,18
59,72,21
74,36,18
9,2,29
8,58,31
31,97,28
35,8,25
42,45,15
43,49,19
79,57,25
34,63,27
81,30,17

Groups:
0,2 16,18,-25
14,15,27 -8,-15,1
1,19 -14,18,16
7,12,17,19 22,-15,11
8,19 -13,-6,17
1,7,20,22,27 -10,18,22
6,11 -5,6,0
2,8,11,13 -13,5,-15
7,19 2,-5,7
15,29 -19,-4,10
1,7,14,18,28 16,25,-5
2,12 20,6,25
8,11,12 7,2,20
2,24 24,3,17
1,11,29 -14,13,23
6,12,26 9,-3,-14
5,8 -3,17,-7
0,5,17,25,26 -19,8,0
8,23 -13,-24,22
13,16,17 -22,8,-7
3,11,14,21,22,26 -15,-6,13
3,12 3,9,10
4,16,24 16,3,11
4,12,21,26 -7,20,-17
16,19,25 -18,12,13
7,9 -10,12,-14
7)
    
Players:
57,28,3
83,14,18
70,23,14
14,12,7
49,45,44
89,69,48
60,38,41
92,41,43
35,15,24
97,41,10
58,90,44
56,1,8
49,48,30
60,94,44
55,50,20
94,91,22
81,48,23
22,41,0
83,81,23
45,42,43
94,25,46
55,91,36
56,76,5
73,39,28
83,61,30
79,23,31
88,3,47
90,56,18
56,78,10
54,87,43

Groups:
4,5,28 -14,25,6
4,14,28 -7,1,2
11,13 7,7,-22
3,20 7,-14,-12
17,19,24 -25,5,2
11,20 20,2,-25
3,26 21,-2,-17
8,14,18,24 -11,-8,-19
1,12,28 14,25,9
10,19,22,26 11,-17,17
0,3,10,11,19,21 7,15,-22
7,19,26 23,15,6
8,18 6,20,25
20,22,25,29 -13,15,-15
2,5 -25,-6,8
26,29 -16,9,4
20,24 -2,11,-21
10,24,28 10,-13,6
2,7,15,17 2,16,4
7,10,19,27 -25,11,-23
12,26 23,21,5
8,21 -23,17,19
2,24 16,-1,14
6,20 17,-5,-24
2,24,25 -23,-1,-21
4,7,8,13,14,29 13,-16,-14
8,21 13,20,-24
3,13,28 6,-17,1
11,21 25,10,-13
2,10 0,14,-6
0,5 -12,16,2
7,8 10,-2,13
14,24,25 4,7,9
3,7,18,20 14,-1,-9
2,20,27 24,-23,5
5,8,13,14,19,27 20,-23,-5
7,27 -1,-3,8
10,26,28 11,16,10
20,23 -15,11,-17
8,18 9,-22,8
6,23 5,19,19
10,14 10,-14,-11
7,24,26 -11,13,2
8)
    
Players:
1,72,21
68,39,36
26,92,12
41,33,44
22,35,42
86,37,8
48,10,11
32,3,14
71,27,26
16,16,15
65,59,42
10,44,25
73,27,34
71,36,41
76,55,18
16,2,19
8,94,29
26,75,3
48,43,12
18,98,19
21,93,44
69,29,25
2,83,41
22,21,9
94,67,10
93,37,34
52,37,13
84,94,1
45,14,8
54,48,18

Groups:
1,6,17,21 24,3,-17
5,26 -1,-20,9
1,7,16,18,27 -21,-5,7
2,3,7,18 14,-4,11
2,25 24,-24,1
5,15,29 -23,6,-2
5,11,16,27,28 -14,-21,-12
2,7,20 -12,-11,-16
6,29 -10,-1,-12
0,1 1,-25,15
9)
    
Players:
40,21,29
28,60,33
79,84,38
26,55,38
49,38,2
71,8,10
61,85,7
88,20,10
95,75,20
20,74,15
54,4,28
19,14,28
15,22,45
22,75,11
9,44,0
65,80,42
21,91,39
33,13,47
91,22,49
34,69,11
57,77,27
24,90,35
30,51,4
22,94,40
62,87,6
23,26,48
75,8,15
49,33,34
58,46,11
95,4,29

Groups:
12,13,20,21 1,19,13
5,17,26 20,8,-5
2,3,29 -5,-19,5

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.