HockeyLeagueDraft
SRM 846 · 2023-05-22 · by misof
Problem Statement
This problem is inspired by the NHL draft.
There are P players waiting to be drafted. The players are numbered from 0 to P-1. Player i has attack strength A[i] and defense strength D[i].
There are T (T <= P) teams waiting to draft. Each team will only draft one of the available players. Teams are numbered from 0 to T-1 in the order in which they will make their draft picks.
Team j currently has total attack strength TA[j] and total defense strength TD[j]. Once they draft a player, they can either use them as an extra attacker (which will increase their TA[j] by the players A[i]) or as an extra defender (which will increase TD[j] by D[i]).
Each team is trying to maximize their power: the value TA[j]*TA[j] + TD[j]*TD[j]. From the set of players that are still available, they will pick the player and assign their use in a way that maximizes their power. In case of a tie, they will pick the player with the smallest number.
Return the number of the player drafted last (i.e., by team T-1).
In order to keep the input size small, the strengths of all players are teams are generated pseudorandomly as described below.
state = seed
for i = 0 to P-1:
state = (state * 1103515245 + 12345) modulo 2^31
A[i] = (state div 10) modulo MP
state = (state * 1103515245 + 12345) modulo 2^31
D[i] = (state div 10) modulo MP
for j = 0 to T-1:
state = (state * 1103515245 + 12345) modulo 2^31
TA[j] = (state div 10) modulo MT
state = (state * 1103515245 + 12345) modulo 2^31
TD[j] = (state div 10) modulo MT
Notes
- The reference solution does not depend on the input being pseudorandom. It would correctly solve any input of the same size.
Constraints
- T will be between 1 and 100,000, inclusive.
- P will be between T and 500,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- MP will be between 1 and 10^6, inclusive.
- MT will be between 1 and 10^8, inclusive.
5 3 47 1000000 10000000 Returns: 0
By using the given pseudocode you should generate the following player data: A = {562130, 187829, 682064, 125015, 773627, } D = {361440, 85409, 396243, 398352, 847743, } and the following team data: TA = {6951486, 8145440, 2958790, } TD = {2264032, 8844428, 298217, } The draft will then proceed as follows: team 0 drafted player 4 (and used them as an attacker) team 1 drafted player 2 (and used them as an attacker) team 2 drafted player 0 (and used them as an attacker)
12 7 42000 100 100 Returns: 2
By using the given pseudocode you should generate the following player data: A = {20, 44, 80, 11, 97, 58, 12, 72, 77, 31, 7, 93, } D = {8, 82, 16, 70, 52, 47, 83, 92, 70, 24, 67, 12, } and the following team data: TA = {66, 39, 61, 40, 12, 39, 35, } TD = {51, 54, 31, 48, 51, 69, 20, } The draft will then proceed as follows: team 0 drafted player 4 (as an attacker) team 1 drafted player 7 (as a defender) team 2 drafted player 11 (as an attacker) team 3 drafted player 6 (as a defender) team 4 drafted player 1 (as a defender) team 5 drafted player 3 (as a defender) team 6 drafted player 2 (as an attacker) Note that team 5 could have achieved the same power by drafting player 8 as a defender, but the tie was broken by choosing the player with the smaller number.
100 100 47 10 10 Returns: 0
100 8 47 10 10 Returns: 36
100 23 47 10 10 Returns: 6
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HockeyLeagueDraft with a public method int draft(int P, int T, int seed, int MP, int MT) · 112 test cases · 2 s / 256 MB per case