Statistics

Problem Statement for "FloatingMedian"

Problem Statement

In meteorology, a common statistical tool is the median of a given set of measurements. (You can find a definition of the median in the Notes section.)

You are writing software for a device that measures temperature once a second. The device has a small digital display. At any moment, the display has to show the median of temperatures measured in the last K seconds.

Before you upload your software into the device, you would like to test it on a computer.

Instead of measuring temperatures, we will use a random number generator (RNG) to generate fake temperatures. Given three ints seed, mul and add, we define a sequence of temperatures:

  • t0 = seed
  • tk+1 = (tk * mul + add) mod 65536

In addition to the parameters of the RNG, you will be given two ints N and K.

Consider the sequence containing the first N temperatures generated by the RNG (i.e., values t0 to tN-1). This sequence has N-K+1 contiguous subsequences of length K. For each such subsequence compute its median.

Your method will be given the numbers seed, mul, add, N, and K. Compute all the medians as described above, and return a long containing their sum.

Definition

Class:
FloatingMedian
Method:
sumOfMedians
Parameters:
int, int, int, int, int
Returns:
long
Method signature:
long sumOfMedians(int seed, int mul, int add, int N, int K)
(be sure your method is public)

Notes

  • Given K numbers, their median is the ((K+1)/2)-th smallest of them, rounding down for even K, and indexing from 1. For example, the median of (1, 2, 6, 5, 4, 3) is 3, and the median of (11, 13, 12, 14, 15) is 13.

Constraints

  • seed, mul, and add are between 0 and 65535, inclusive.
  • N is between 1 and 250,000, inclusive.
  • K is between 1 and 5,000, inclusive.
  • N is greater than or equal to K.

Examples

  1. 3

    1

    1

    10

    3

    Returns: 60

    The generated temperatures are: 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12. The length-3 contiguous subsequences are (3, 4, 5), (4, 5, 6), ..., and (10, 11, 12). Their medians are 4, 5, ..., 11. The sum of these medians is 4+5+...+11 = 60.

  2. 10

    0

    13

    5

    2

    Returns: 49

    This time the generated temperatures are 10, 13, 13, 13, and 13. The medians you should compute are 10, 13, 13, and 13.

  3. 10

    0

    7

    5

    2

    Returns: 28

  4. 4123

    2341

    1231

    7

    3

    Returns: 102186

    Generated temperatures: 4123, 19382, 23581, 23040, 1743, 18362, 60593.

  5. 47

    5621

    1

    125000

    1700

    Returns: 4040137193

    A quite large random test case.

  6. 47474

    5621

    1

    250000

    5000

    Returns: 8024139123

  7. 1

    2

    0

    250000

    23

    Returns: 80

  8. 32321

    46543

    32552

    17

    17

    Returns: 25569

    Watch out for integer overflow when generating the temperatures.

  9. 453

    2

    64

    351

    349

    Returns: 196416

  10. 62000

    1

    1

    250000

    4789

    Returns: 7643623468

  11. 59003

    1

    2

    250000

    4948

    Returns: 7791440981

  12. 32000

    1

    65534

    250000

    4877

    Returns: 7838388810

  13. 32312

    5621

    1

    250000

    1

    Returns: 8188512824

  14. 2312

    5621

    1

    250000

    2

    Returns: 5459597502

  15. 12

    5621

    1

    250000

    3

    Returns: 8189672636

  16. 1342

    5621

    1

    250000

    4

    Returns: 6558391466

  17. 5342

    5621

    1

    250000

    5

    Returns: 8189773423

  18. 5342

    5621

    1

    250000

    10

    Returns: 7445288217

  19. 5342

    5621

    1

    250000

    470

    Returns: 8159311713

  20. 5342

    5621

    1

    250000

    4700

    Returns: 8029389174

  21. 5342

    5621

    1

    250000

    4999

    Returns: 8021974075

  22. 5342

    5621

    1

    250000

    5000

    Returns: 8020332398

  23. 32312

    4749

    32174

    250000

    1

    Returns: 8195130512

  24. 2312

    4749

    32174

    250000

    2

    Returns: 5466685796

  25. 12

    4749

    32174

    250000

    3

    Returns: 8200474426

  26. 1342

    4749

    32174

    250000

    4

    Returns: 6553562754

  27. 5342

    4749

    32174

    250000

    5

    Returns: 8188528886

  28. 5342

    4749

    32174

    250000

    10

    Returns: 7441233970

  29. 5342

    4749

    32174

    250000

    470

    Returns: 8156352552

  30. 5342

    4749

    32174

    250000

    4700

    Returns: 8037125160

  31. 5342

    4749

    32174

    250000

    4999

    Returns: 8029664338

  32. 5342

    4749

    32174

    250000

    5000

    Returns: 8027928740

  33. 65535

    1

    0

    250000

    1

    Returns: 16383750000

  34. 32321

    46543

    32552

    17

    17

    Returns: 25569

  35. 32321

    46543

    32552

    250000

    5000

    Returns: 8028017305

  36. 47

    5621

    1

    125000

    1700

    Returns: 4040137193

  37. 65535

    65535

    65535

    250000

    5000

    Returns: 0

  38. 2423

    2342

    34343

    250000

    5000

    Returns: 11141910477

  39. 12

    347

    6

    250000

    5000

    Returns: 8022041130

  40. 32

    51

    6342

    250000

    1000

    Returns: 8159464550

  41. 123

    13743

    12345

    250000

    5000

    Returns: 8021019601

  42. 65530

    65535

    65535

    250000

    4999

    Returns: 8028103035

  43. 65535

    65535

    0

    2

    1

    Returns: 65536

  44. 1532

    2354

    4234

    250000

    5000

    Returns: 2592600582

  45. 65535

    65535

    65535

    250000

    2500

    Returns: 0

  46. 32321

    46543

    32551

    240000

    4999

    Returns: 7696717437

  47. 0

    1

    1

    250000

    5000

    Returns: 7734014667

  48. 1337

    65534

    2

    250000

    3

    Returns: 5461574920

  49. 57

    65501

    50000

    250000

    5000

    Returns: 8035343957

  50. 65535

    65535

    13

    250000

    5000

    Returns: 3430014

  51. 10

    2

    3

    250000

    5000

    Returns: 16055650533

  52. 47

    5621

    1

    250000

    5000

    Returns: 8023179659

  53. 65534

    65533

    65530

    250000

    5000

    Returns: 8028296292

  54. 47

    5623

    1

    125000

    1700

    Returns: 4034637764

  55. 34

    157

    31

    150000

    5000

    Returns: 4751093065

  56. 1

    1

    2

    250000

    50

    Returns: 7940052591

  57. 40000

    40000

    40000

    200000

    4000

    Returns: 8642860096

  58. 3

    1

    1

    250000

    5000

    Returns: 7734159846

  59. 47

    5621

    1

    25000

    5000

    Returns: 650821320

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: