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
Definition
- Class:
- HockeyLeagueDraft
- Method:
- draft
- Parameters:
- int, int, int, int, int
- Returns:
- int
- Method signature:
- int draft(int P, int T, int seed, int MP, int MT)
- (be sure your method is public)
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.
Examples
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
500000
100000
4747
999997
99999997
Returns: 434472
500000
100000
4747
12
23
Returns: 140030
27
27
268543586
6
5
Returns: 23
26
26
420679459
6
1
Returns: 18
31
31
288469429
5
3
Returns: 15
41
41
284290351
6
1
Returns: 32
32
32
1964529467
1
1
Returns: 31
36
36
1954741865
5
2
Returns: 25
25
25
210761941
4
3
Returns: 12
17
17
1792312856
3
2
Returns: 12
41
41
822004006
2
1
Returns: 39
36
36
2102970538
1
6
Returns: 35
44
44
932258961
4
7
Returns: 31
34
34
1932976813
5
7
Returns: 25
48
48
1941996298
10
3
Returns: 9
16
16
1154103055
1
5
Returns: 15
6
6
1347510144
3
10
Returns: 2
16
16
1675592994
2
10
Returns: 15
40
40
1023781398
1
2
Returns: 39
42
42
1839181670
1
5
Returns: 41
37
37
1110194861
2
2
Returns: 36
29
29
414487470
2
6
Returns: 27
120268
13
1747997964
36
110364
Returns: 252
193843
305
35518693
1204
77310
Returns: 12599
1628
242
1817480547
48562
5
Returns: 524
186
1
759520630
374329
3789076
Returns: 28
437
36
1802475493
2737
14195
Returns: 287
13416
7007
1506823224
560
5
Returns: 10148
2783
8
1534570060
8573
3
Returns: 2505
105112
1351
1831387875
1
4063
Returns: 1350
469
1
875414610
700271
211282
Returns: 382
2972
114
206002095
96
2981937
Returns: 465
11400
3430
1007692883
161
1811088
Returns: 8838
9697
3
1067603013
6803
3
Returns: 8307
1100
1021
547069335
820817
7
Returns: 404
115992
1424
1698748993
12
12512671
Returns: 8621
36
5
1142594330
45
6878
Returns: 30
91
31
215358517
4609
8980001
Returns: 39
10811
21
285293582
5824
2929
Returns: 10043
252231
32299
896250281
87889
26946982
Returns: 194693
4
3
1993230996
19
11950973
Returns: 0
258300
5852
803597401
1450
55016587
Returns: 196985
158
2
1670106070
2013
137
Returns: 0
34093
9471
1830033539
20887
21
Returns: 30246
355651
735
1519433312
20
52820
Returns: 7409
1928
1105
628497001
3792
1838951
Returns: 757
5926
579
773446207
9
4
Returns: 2777
1
1
1140382381
11770
2452105
Returns: 0
133
2
2145261723
230
1938800
Returns: 102
479324
764
1539321840
20273
608957
Returns: 55906
105
1
860737133
4
657168
Returns: 4
7526
221
1681912352
206031
6
Returns: 6628
34882
3
1649856827
241313
55856
Returns: 12012
468998
1394
884159313
87530
37183534
Returns: 32569
113944
13
1836004745
1357
70789445
Returns: 4303
99397
39412
1339768883
1
142580
Returns: 39411
242999
60933
32727530
247515
27693873
Returns: 154397
17674
6440
258153880
49
8
Returns: 15924
80555
26021
1294680473
166
7367
Returns: 21609
124245
71472
1644141517
1
1199924
Returns: 71471
3085
643
1899269995
5817
163714
Returns: 61
416721
8
871662290
1
2
Returns: 7
73309
1
246373014
29
211
Returns: 25
10000
7712
295453068
45878
4078
Returns: 4792
177387
18195
38178864
358282
16726973
Returns: 171817
467695
96557
1569484844
14
31
Returns: 254609
465794
92422
1074310782
28858
1402
Returns: 232837
471992
96409
803809273
2
59128201
Returns: 130218
474839
92774
1630469677
1
57914
Returns: 92773
496757
98670
79891797
30387
8250
Returns: 207774
472352
91386
13445971
2963
14803
Returns: 352225
473070
91365
10630351
50
47
Returns: 46528
463694
95918
97715260
430
1186
Returns: 56096
470470
93773
1248164950
4533
59990
Returns: 433980
478909
93710
330554205
524068
504
Returns: 163521
490683
99828
1395948568
2390
5
Returns: 334724
496097
98770
753059422
22
475103
Returns: 155244
461172
95634
2054642359
1283
279
Returns: 277749
498832
99126
2062272684
2
205
Returns: 130110
495018
91552
965605668
32682
4846
Returns: 190609
461281
94852
928930744
2806
713393
Returns: 207840
464752
95763
1131907697
63021
65810
Returns: 194862
460154
92230
612509451
25
3846819
Returns: 298515
464219
96376
474121281
169309
496246
Returns: 395709
485176
90266
959180391
112
5257404
Returns: 459069
95764
95764
268543586
128654
56300
Returns: 77871
97245
97245
1039591800
6
7062484
Returns: 97173
99138
99138
841741944
35080
426
Returns: 62043
91604
91604
1558380042
27356
15909
Returns: 66612
91804
91804
1789542187
49911
4530769
Returns: 54402
97928
97928
1340917328
94494
33064496
Returns: 7130
94147
94147
640818900
1193
24
Returns: 56685
98376
98376
2046595582
6
7815141
Returns: 98356
93014
93014
758823778
306
432
Returns: 30060
98640
98640
1685176129
98
234
Returns: 91207
91100
91100
1585910533
3
5
Returns: 91099
92968
92968
2108757054
8148
21
Returns: 92959
92466
92466
1453170456
5
14
Returns: 92434
92017
92017
95408474
51
12
Returns: 88874
93917
93917
649419618
3
519151
Returns: 93913
500000
100000
99999999
999999
99999999
Returns: 20047
500000
100000
500000
20
500000
Returns: 53319
500000
100000
123131
123123
1231234
Returns: 160299
500000
100000
123131
2
2
Returns: 135192
500000
100000
500000
20
20
Returns: 53023
500000
100000
47
3
3
Returns: 180845
500000
100000
42000
3
3
Returns: 179757