Statistics

Problem Statement for "FindingKids"

Problem Statement

In Amagi Brilliant Park there is a famous bumper car ride. The park administration emphasizes safety. When they observed other bumper car rides, they noticed that collisions of more than two cars are very dangerous. Therefore, they decided to design a unique ride where this cannot happen.

This ride consists of a single track that is very long but only one car wide. For the purpose of this problem we will visualize the ride as the real number line and cars as points on this line. The line goes from the left to the right and coordinates increase towards the right.

All cars are always in motion: at any moment, some cars are going to the left and all other cars are going to the right. All cars always move at the same constant speed of 1 unit per microsecond. Whenever two cars occupy the same point, they bump into each other and both of them immediately switch their direction (from left to right and vice versa).

A group of n kids from a certain elementary school just entered the park. Kids love bumper cars, so all n of them went on the ride at the same time. Each kid chose a different car. All n cars start in distinct locations. There are no other cars on the ride. The kids are numbered 0 through n-1 in no particular order. For each kid i, you will be given its initial position pos[i] and the initial direction dir[i] of its car. The exact format is specified below.

The teacher is worried about being too far away from the kids. She asked you q queries. The queries are numbered from 0 to q-1. Each query has two parameters: kid[i] and time[i]. Here, kid[i] is the number of one particular kid, and time[i] is the time in microseconds from the beginning of the ride.

The answer to each query should be the distance between position 0 and the position of kid[i] at time[i]. Return the sum of answers to all the queries.

You are given the ints n and q mentioned above. You are also given ints A, B, and C. These are the seeds of a pseudo-random generator that will output the values of pos, dir, kid, and time. The pseudocode of the generator follows.

let M = 1,000,000,007

for i from 0 to n-1, inclusive:
    A := (A * B + C) modulo M
    p := A modulo (M - n + i + 1)
    if p is already in pos:
        p := M - n + i
    pos[i] := p
    if p modulo 2 == 0:
        dir[i] := "right"
    else:
        dir[i] := "left"

for i from 0 to q-1, inclusive:
    A := (A * B + C) modulo M
    kid[i] := A modulo n
    A := (A * B + C) modulo M
    time[i] := A

Definition

Class:
FindingKids
Method:
getSum
Parameters:
int, int, int, int, int
Returns:
long
Method signature:
long getSum(int n, int q, int A, int B, int C)
(be sure your method is public)

Notes

  • Assume that the duration of the ride is greater than any of the values time[i].
  • Distance is always a nonnegative quantity. Specifically, the distance from position x to 0 is |x| (the absolute value of x).

Constraints

  • n will be an integer from 1 to 200,000 inclusive.
  • q will be an integer from 1 to 200,000 inclusive.
  • A will be an integer from 0 to 1,000,000,006 inclusive.
  • B will be an integer from 0 to 1,000,000,006 inclusive.
  • C will be an integer from 0 to 1,000,000,006 inclusive.

Examples

  1. 5

    2

    0

    1

    1

    Returns: 15

    At time 0 the kids' positions are {1, 2, 3, 4, 5} and their directions are {left, right, left, right, left}. Query 0 is about kid 1 at time 7. At time 0.5, kid 1 bumps into kid 2 at position 2.5 and immediately starts going left. Kid 1 does not bump into anyone else. Thus, after another 6.5 microseconds she will end up at position -4. The answer to query 0 is |-4| = 4. (Distance is always nonnegative.) Query 1 is about kid 3 at time 9. At time 0.5, kid 3 bumps into kid 4 at position 4.5 and immediately starts going left. At the same time, kid 2 bumps into kid 1 at position 2.5 and immediately starts going right. At time 1.5, kid 3 bumps into kid 2 at position 3.5 and immediately starts going right again. Kid 3 does not bump into anyone else. In the remaining 7.5 microseconds kid 3 will travel from position 3.5 to position 11. The answer to query 1 is therefore 11. The correct return value is the sum of the answers, which is 4 + 11 = 15.

  2. 5

    4

    3

    2

    1

    Returns: 43376

    In order, the answers to the queries are {504, 1984, 8184, 32704}.

  3. 200000

    200000

    12345

    67890

    111213141

    Returns: 133378408428237

  4. 1

    200000

    299935478

    93657707

    751975948

    Returns: 55916462670542

  5. 200000

    200000

    459695835

    1

    0

    Returns: 108059168400000

  6. 200000

    200000

    405928708

    0

    1337

    Returns: 199960268800000

  7. 200000

    200000

    11158416

    1

    1

    Returns: 2311683500000

  8. 200000

    200000

    518432386

    854093692

    86569215

    Returns: 133028436645338

  9. 200000

    200000

    970299885

    328509249

    279508717

    Returns: 133028136604689

  10. 200000

    200000

    407384288

    21158936

    165339869

    Returns: 133321370354381

  11. 200000

    200000

    166944611

    752387871

    77404622

    Returns: 133563039624147

  12. 200000

    200000

    610380043

    482148257

    12222401

    Returns: 133456299414825

  13. 200000

    200000

    173965048

    283449012

    271669161

    Returns: 133596144863621

  14. 200000

    200000

    986748024

    799649815

    918466217

    Returns: 132957526469776

  15. 200000

    200000

    500779185

    866670622

    359419754

    Returns: 133134463410080

  16. 200000

    200000

    703675017

    142849459

    692112347

    Returns: 133208877242865

  17. 200000

    200000

    255029315

    449646332

    999058603

    Returns: 133863257860030

  18. 200000

    200000

    949293970

    577325836

    168050562

    Returns: 133253948435846

  19. 200000

    200000

    191557169

    337522684

    428963343

    Returns: 133403307063189

  20. 200000

    200000

    996358245

    13046793

    200268821

    Returns: 133546388204857

  21. 200000

    200000

    0

    0

    2

    Returns: 199960001800000

  22. 200000

    200000

    123456789

    987654321

    192837465

    Returns: 133430357128962

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: