Statistics

Problem Statement for "ItsWhomYouKnow"

Problem Statement

In Mafia City each person belongs to exactly one of C different clans. The clans are numbered from 0 to C-1.

A new doctor just arrived to Mafia City with his receptionist, Miss Susie. (They aren't in any clan, but that's not important.) Miss Susie is in charge of calling patients into the doctor's office.

The first day of their practice just started. There are already some people waiting in the doctor's waiting room. The arrays initialClans and initialPowers (with L elements each) describe these people in the order in which they arrived. The people have numbers from 0 to L-1, and for each person we know their clan (initialClans[i]) and their power (initialPowers[i]). More people will arrive during the day.


Miss Susie quickly understood that the local situation is different from her previous practice. Here, it does not matter how sick you are. Who arrived first matters somewhat, a person's power also matters a little, but neither of those two things is the most important one. It's whom you know. If someone is from a powerful clan, it's dangerous to keep them waiting for too long.

As Miss Susie observes the waiting patients, she is gradually learning new things about the clans. Miss Susie's opinion on the power of a clan is equal to the maximum of the powers of its members she already saw. (This includes those who are no longer in the waiting room.)

Whenever the doctor calls for a new patient, Miss Susie looks at all the waiting patients. Among their clans she selects the most powerful one (according to her current knowledge). In case of a tie, she prefers the clan with the smallest number among the tied ones. She invites in the member of that clan who has been waiting for the longest amount of time (i.e., the one with the smallest number).


In order to keep the input small, the new patients who arrive during the day are generated pseudorandomly. Please use the pseudocode below to generate a new patient. 


function new_patient():
    state = (state * 1103515245 + 12345) modulo 2^31
    clan = (state div 10) modulo C
    state = (state * 1103515245 + 12345) modulo 2^31
    power = state modulo P
    return (clan, power)

You are given the integer N.

Initialize the variable "state" to seed, and initialize the variable "answer" to zero.

Then, simulate N rounds of events. The rounds are numbered from 0 to N-1.

In round x, do the following:

  1. Two new patients arrive into the waiting room. Call new_patient() twice to generate them. Assign them the next two available numbers.
  2. The doctor calls for a new patient. Determine the number ID[x] of the patient Miss Susie calls into the office.
  3. answer += ID[x] * (x+1)
  4. state = (state + ID[x]) modulo 2^31

After the last round, return answer.

Definition

Class:
ItsWhomYouKnow
Method:
simulate
Parameters:
int, int, int, int[], int[], int
Returns:
long
Method signature:
long simulate(int N, int C, int P, int[] initialClans, int[] initialPowers, int seed)
(be sure your method is public)

Notes

  • The reference solution does not depend on the input being pseudorandom.
  • For the constraints used in this problem it is guaranteed that answer won't overflow a signed 64-bit integer variable.

Constraints

  • N will be between 1 and 100,000, inclusive.
  • C will be between 1 and 10^6, inclusive.
  • P will be between 1 and 10^9, inclusive.
  • initialClans will have between 0 and 100 elements, inclusive.
  • Each element of initialClans will be between 0 and C-1, inclusive.
  • initialPowers will have the same number of elements as initialClans.
  • Each element of initialPowers will be between 0 and P-1, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.

Examples

  1. 5

    10

    1000

    {}

    {}

    47

    Returns: 51

    The waiting room starts empty. Below is a full log of what happens during the five rounds: round 0: person number 0 (clan 0 power 405) enters the waiting room person number 1 (clan 9 power 91) enters the waiting room nurse calls in patient #0 answer incremented by 0 state at the end of the round is 160854091 round 1: person number 2 (clan 4 power 433) enters the waiting room person number 3 (clan 5 power 527) enters the waiting room nurse calls in patient #3 answer incremented by 6 state at the end of the round is 1993983530 round 2: person number 4 (clan 6 power 640) enters the waiting room person number 5 (clan 9 power 542) enters the waiting room nurse calls in patient #4 answer incremented by 12 state at the end of the round is 1965431546 round 3: person number 6 (clan 9 power 264) enters the waiting room person number 7 (clan 6 power 230) enters the waiting room nurse calls in patient #7 answer incremented by 28 state at the end of the round is 321580237 round 4: person number 8 (clan 3 power 531) enters the waiting room person number 9 (clan 8 power 1) enters the waiting room nurse calls in patient #1 answer incremented by 5 state at the end of the round is 176589002

  2. 3

    10

    1000

    {4, 7, 1, 2, 4, 4, 0, 9}

    {13, 2, 55, 17, 600, 0, 101, 100}

    47

    Returns: 44

    Again, the full log of actions is shown below. Note that even though we started from the same seed, in round 2 the new people generated are no longer the same as in Example 0 (because ID[1] was different). person number 0 (clan 4 power 13) starts in the waiting room person number 1 (clan 7 power 2) starts in the waiting room person number 2 (clan 1 power 55) starts in the waiting room person number 3 (clan 2 power 17) starts in the waiting room person number 4 (clan 4 power 600) starts in the waiting room person number 5 (clan 4 power 0) starts in the waiting room person number 6 (clan 0 power 101) starts in the waiting room person number 7 (clan 9 power 100) starts in the waiting room round 0: person number 8 (clan 0 power 405) enters the waiting room person number 9 (clan 9 power 91) enters the waiting room nurse calls in patient #0 answer incremented by 0 state at the end of the round is 160854091 round 1: person number 10 (clan 4 power 433) enters the waiting room person number 11 (clan 5 power 527) enters the waiting room nurse calls in patient #4 answer incremented by 8 state at the end of the round is 1993983531 round 2: person number 12 (clan 6 power 609) enters the waiting room person number 13 (clan 0 power 399) enters the waiting room nurse calls in patient #12 answer incremented by 36 state at the end of the round is 1663867411

  3. 3

    1000

    1000

    {123, 789, 456}

    {999, 999, 999}

    47

    Returns: 7

    The six new people are from clans other than 123, 456, and 789. As these three clans are tied for the highest power, the nurse will apply the tiebreaker rule: the nurse will first call patient #0 (clan 123), then patient #2 (clan 456) and only then patient #1 (clan 789).

  4. 3

    10

    1000

    {4, 7, 1, 2, 4, 4, 6, 9}

    {13, 2, 55, 17, 600, 0, 101, 100}

    47

    Returns: 26

  5. 100000

    1000000

    1000000000

    {}

    {}

    47

    Returns: 646138898940410

  6. 100000

    1000000

    1

    {}

    {}

    42

    Returns: 665594914844516

  7. 100000

    1

    1

    {}

    {}

    432

    Returns: 333333333300000

  8. 95764

    7

    249999

    {}

    {}

    1475191316

    Returns: 484853922096918

  9. 98395

    7310

    567183

    {5, 2161, 6490, 3944, 5929, 4478, 74, 6682, 2585, 4649, 3503, 1884, 1947, 4286}

    {538918, 376524, 463702, 253806, 34879, 392342, 370621, 358522, 205503, 250210, 36992, 131595, 350148, 102704}

    1797583853

    Returns: 536520842034106

  10. 95944

    463249

    98675

    {}

    {}

    417035555

    Returns: 555503154980086

  11. 95486

    124

    10236546

    {}

    {}

    1789542187

    Returns: 467947856640803

  12. 94691

    194

    2212

    {}

    {}

    2078532398

    Returns: 478853673859434

  13. 99219

    6227

    12095316

    {}

    {}

    489349967

    Returns: 551649160263968

  14. 96223

    49357

    680737

    {35847, 41101, 5424, 4889, 17416, 33504, 40797, 35839, 31228, 28548, 23958, 2174, 39832, 17367, 42224, 39887, 33879, 44178, 30920, 46411, 41833, 20643}

    {23313, 604945, 254824, 221631, 362769, 452604, 192954, 185259, 492613, 208327, 134088, 103198, 143298, 597291, 360767, 553020, 411419, 113335, 279828, 465484, 473, 128320}

    1906477425

    Returns: 513587514139302

  15. 96784

    6

    1

    {}

    {}

    179122525

    Returns: 603316736056853

  16. 92968

    129890

    127

    {9679, 22953, 109546, 19735, 120829, 71230, 44347, 83299, 113651, 6119, 115020, 81533, 30736, 93355, 8026, 49640, 16141, 2911, 11611, 39679, 7063, 115245, 71808, 40326, 31341, 80301, 117503, 96208, 70108, 19818, 72080, 75990, 99932, 35803, 81131, 112499, 129714, 74820, 10577, 73788, 64389, 44920, 72944, 6839, 124942, 15020, 54195, 54741, 46365, 118830, 39690, 73966, 110663, 99578, 64127, 78336, 18304, 8327, 127248, 66568, 15344, 118396, 60458, 85583, 103134, 59476, 107959, 2343, 56961, 106125, 73915, 68435, 100062, 126657, 8675, 102447, 103445, 37700, 102727, 92373, 64251, 65849, 14959, 98953, 32128, 46162, 104366, 43399, 21878}

    {59, 2, 75, 12, 85, 58, 120, 58, 125, 35, 81, 69, 87, 88, 88, 117, 3, 123, 71, 24, 105, 86, 36, 5, 98, 33, 69, 61, 49, 8, 92, 100, 13, 112, 66, 90, 75, 76, 61, 68, 95, 101, 46, 74, 39, 52, 98, 87, 114, 114, 26, 93, 80, 11, 125, 120, 13, 65, 103, 39, 51, 122, 42, 68, 107, 46, 108, 13, 104, 119, 11, 109, 79, 95, 54, 46, 6, 44, 74, 110, 7, 118, 50, 81, 103, 34, 32, 26, 37}

    1948158689

    Returns: 479901271039529

  17. 93427

    26198

    30816

    {19014, 15718, 20, 901, 13852, 14988, 17046, 14348, 20121, 8445, 9632, 3358, 9931, 4058, 5562, 13863, 11031, 16303, 13959, 7684}

    {16493, 18686, 16817, 8621, 10256, 18179, 755, 30096, 19952, 22055, 28619, 12429, 28043, 29951, 19484, 19310, 22832, 19491, 22605, 20447}

    1363446327

    Returns: 466006455685752

  18. 97566

    178126

    3678464

    {}

    {}

    183808378

    Returns: 559756032588498

  19. 92973

    7

    9179

    {}

    {}

    963875836

    Returns: 489898980578882

  20. 92882

    4132

    670134

    {}

    {}

    312614420

    Returns: 450622573491250

  21. 90012

    8186

    16024318

    {}

    {}

    1602883242

    Returns: 410992577125828

  22. 98376

    4932

    7

    {}

    {}

    1769321186

    Returns: 606377806859267

  23. 92864

    63950

    19455

    {}

    {}

    1698673775

    Returns: 465247113079198

  24. 97087

    104

    4707

    {}

    {}

    569139255

    Returns: 504605260602713

  25. 95456

    12

    38843

    {9, 1, 9, 3, 8, 10, 3, 8, 4, 11, 4, 8, 9, 1, 8, 0, 4, 11, 2, 7, 11, 3, 6, 9, 7, 0, 9, 6, 9, 3, 10, 8, 5, 1, 5, 1, 2, 9, 1, 3, 2, 1, 2, 8, 2, 11, 2, 1, 1, 2, 9}

    {25807, 22827, 7981, 27175, 19324, 35995, 14388, 22735, 5904, 20588, 6679, 2345, 13226, 36640, 8878, 21640, 5956, 20927, 28112, 33175, 35780, 37524, 23078, 34165, 34044, 27885, 28778, 28576, 27073, 32155, 1486, 12767, 21393, 3215, 28083, 6626, 28776, 38194, 8128, 6310, 21932, 28649, 3867, 21869, 12286, 26789, 30723, 33944, 31128, 33844, 7832}

    1533974457

    Returns: 433029308329769

  26. 93759

    67

    260459

    {}

    {}

    1396777957

    Returns: 460046290000442

  27. 92684

    586

    3

    {352, 196, 568, 220, 378, 379, 136, 207, 458, 35, 308, 306, 431, 113, 432, 428, 355, 509, 262, 46, 578, 502, 235, 277, 415, 59, 24, 402, 195, 427, 375, 532, 90}

    {1, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 2, 2, 0, 1, 2, 0, 2, 1, 1, 0, 1, 1, 0}

    189901465

    Returns: 529864677935553

  28. 99608

    13524

    56688521

    {}

    {}

    32134090

    Returns: 560377426790952

  29. 90336

    561

    753584

    {50, 392, 475, 195, 91, 283, 404, 522, 356, 38, 66, 311, 318, 53, 452, 474, 416, 340, 92, 259, 430, 382, 100, 386, 386, 180, 302, 30, 31, 195, 129, 228, 88, 7, 433, 437, 426, 433, 130, 157, 384, 551, 471, 268, 151, 76, 40, 247, 131, 72, 17, 140, 125, 530, 130, 299, 428, 560, 499, 24, 171, 554, 149, 236, 120, 155, 291, 495, 501, 471, 316}

    {429622, 471554, 634983, 192394, 13414, 448734, 511028, 513420, 427859, 360167, 393153, 582719, 316554, 322227, 413634, 394757, 37283, 654037, 551913, 281777, 148523, 490069, 411441, 106265, 691544, 112873, 621610, 35596, 385634, 669519, 356726, 696090, 710649, 599490, 154657, 1149, 273031, 368304, 167765, 650951, 41707, 432346, 504288, 752035, 339192, 154683, 278571, 268598, 346832, 428601, 689135, 116955, 215482, 701481, 185180, 651626, 241712, 295862, 696541, 257631, 483036, 729257, 553396, 357489, 163654, 553582, 378481, 116936, 153597, 186349, 592043}

    14434277

    Returns: 411205374404544

  30. 93727

    215061

    1480476

    {99714, 197687, 45072, 128505, 159589, 192223, 190286, 44639, 50673, 105547, 210938, 190887, 175522, 14068, 122921, 85665, 143803, 141426, 19568, 67858, 24965, 36308, 175381, 135094, 196013, 151916, 175104, 54593, 71747, 156571, 102103, 29095, 66994, 144940, 93769, 31358, 98524, 97581, 170238, 139736, 58978, 76267, 65782, 159541, 177461, 183247, 170552}

    {672802, 1194685, 80379, 1296659, 435070, 621235, 935428, 682001, 239533, 306722, 1241560, 383932, 546167, 719423, 574598, 198543, 617747, 436210, 79411, 567384, 1285932, 1364481, 455204, 415980, 1432260, 1032528, 1038513, 162406, 800582, 1361144, 48824, 1372377, 1243250, 314368, 223194, 879370, 631237, 462060, 868317, 398019, 180683, 449241, 1347047, 1330244, 1393569, 468732, 1149324}

    1070188718

    Returns: 502977724121482

  31. 91462

    240984

    834

    {}

    {}

    1605916986

    Returns: 468119807429525

  32. 91492

    1955

    79

    {}

    {}

    372122540

    Returns: 437389460899915

  33. 99284

    47115

    3

    {}

    {}

    1324603655

    Returns: 579847500046515

  34. 94338

    293268

    6

    {}

    {}

    1963767647

    Returns: 519329103743071

  35. 98403

    129150

    838

    {}

    {}

    1874417835

    Returns: 567249133387329

  36. 99993

    1453

    181856641

    {}

    {}

    813484984

    Returns: 560413637467447

  37. 90680

    1

    13332801

    {}

    {}

    852796077

    Returns: 248549720780440

  38. 99698

    219341

    88318

    {}

    {}

    1407805355

    Returns: 603829272107983

  39. 93027

    63

    4

    {}

    {}

    1678817963

    Returns: 532912462130142

  40. 97373

    608

    66593297

    {}

    {}

    1161698913

    Returns: 515391190897504

  41. 94624

    118

    6

    {}

    {}

    1643056859

    Returns: 562762717105472

  42. 97531

    676

    174

    {}

    {}

    1557649323

    Returns: 529244765316822

  43. 95062

    2

    8167690

    {}

    {}

    105888022

    Returns: 569092574431075

  44. 90151

    792

    240070

    {}

    {}

    1013905843

    Returns: 400132225658629

  45. 97442

    2

    10571829

    {}

    {}

    1728285218

    Returns: 384853733303327

  46. 93066

    139

    7800

    {114, 138, 124, 41, 40, 61, 70, 81, 49, 126, 130, 70, 117, 65, 86, 134, 29, 56, 65, 57, 8, 35, 62, 114, 21, 82, 55, 82, 24, 66, 132, 40, 71, 92, 35, 42, 20, 47, 14, 130, 45, 26, 73, 10, 82, 47, 22, 115, 70, 25, 76, 50, 126, 36, 34, 62, 137, 61, 79, 65, 116, 6, 79, 48, 6, 110, 44, 68, 124, 48}

    {3674, 105, 3027, 5210, 2026, 3288, 4155, 1466, 6443, 1444, 1466, 4939, 411, 1762, 2581, 4996, 3298, 5369, 2456, 6003, 2192, 5126, 760, 2480, 1884, 356, 4592, 3860, 7612, 7369, 6678, 2507, 1932, 2423, 6825, 3739, 1467, 1448, 4540, 2480, 6486, 3769, 2368, 2387, 5012, 6072, 424, 6840, 2512, 7444, 310, 5400, 7093, 561, 5001, 4909, 3274, 4647, 4146, 3481, 1199, 3100, 3150, 5391, 4446, 1836, 4342, 4589, 3387, 5666}

    428277337

    Returns: 459016114487941

  47. 97290

    178887

    461

    {}

    {}

    1375771134

    Returns: 556081649374706

  48. 92042

    7662

    18

    {}

    {}

    1862495166

    Returns: 443966153223749

  49. 93861

    1

    137726

    {}

    {}

    1447671307

    Returns: 275634944580840

  50. 98706

    714

    290

    {}

    {}

    217439203

    Returns: 535571123634873

  51. 92860

    3466

    7

    {}

    {}

    1120538438

    Returns: 518628212917854

  52. 99789

    2885

    73544625

    {}

    {}

    1118603551

    Returns: 561226157887285

  53. 93813

    12

    57

    {}

    {}

    1207634144

    Returns: 548244373129564

  54. 98651

    338

    52

    {}

    {}

    658136679

    Returns: 618975724919139

  55. 97898

    12

    6387127

    {}

    {}

    648575493

    Returns: 456406379298820

  56. 93593

    173

    6

    {}

    {}

    625973473

    Returns: 544252739706962

  57. 94836

    2

    387015329

    {}

    {}

    890467798

    Returns: 360528906553055

  58. 100000

    1000000

    1000000000

    {123, 789, 456 }

    {999, 999, 999 }

    47

    Returns: 646151134452444

  59. 100000

    1000000

    1000000000

    { }

    { }

    1

    Returns: 645686060163037

  60. 100000

    10

    10

    { }

    { }

    4523521

    Returns: 665633032392507

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: