Statistics

Problem Statement for "HowUnsorted"

Problem Statement

The problem statement contains superscripts and subscripts that can be seen in the applet.
Given a randomly generated sequence, it can be useful to know how unsorted it is. The sequence 
	a1, a2, a3, a4, ... , an
gets 1 'unsortedness point' for every distinct pair (i,j) where i < j but ai > aj. The terms in the sequence are defined by the following formula: 
	a1 = 1   and   ak = (m * ak-1 + c) % (231 - 1)
Here % denotes the modulus or remainder operator. Return the number of unsortedness points scored by this n-element sequence.

Definition

Class:
HowUnsorted
Method:
howMany
Parameters:
int, int, int
Returns:
long
Method signature:
long howMany(int m, int c, int n)
(be sure your method is public)

Notes

  • Make sure to use 64-bit types when generating the random values.

Constraints

  • m will be between 1 and 2000000000 inclusive.
  • c will be between 0 and 2^31-2 inclusive.
  • n will be between 3 and 100000 inclusive.

Examples

  1. 1234257123

    123

    100000

    Returns: 2504702368

  2. 1

    1

    10000

    Returns: 0

  3. 2

    1

    100000

    Returns: 2418862875

  4. 1

    10000000

    100000

    Returns: 2496181732

  5. 11

    13

    100000

    Returns: 2503704581

  6. 1

    2147483646

    100000

    Returns: 4999750004

  7. 1

    2147483646

    10000

    Returns: 49975004

  8. 1

    2147433546

    100000

    Returns: 3061347243

  9. 742938285

    0

    100000

    Returns: 2491816869

  10. 95070637

    0

    100000

    Returns: 2500768557

  11. 1226874159

    0

    100000

    Returns: 2501133639

  12. 62089911

    0

    100000

    Returns: 2501281163

  13. 1343714438

    0

    100000

    Returns: 2493527808

  14. 1078318381

    0

    12341

    Returns: 37971016

  15. 1203248318

    0

    12312

    Returns: 37801774

  16. 397204094

    0

    98988

    Returns: 2452199341

  17. 10

    20

    100000

    Returns: 2499385852

  18. 35

    89

    10932

    Returns: 29627002

  19. 2000000000

    2147433546

    100000

    Returns: 2496920584

  20. 2

    10

    5

    Returns: 0

    The sequence used here is: 1, 12, 34, 78, 166 Since the values are sorted, the return is 0.

  21. 1000

    100

    6

    Returns: 3

    The sequence here is: 1, 1100, 1100100, 1100100100, 588472836, 62316822 The 3 unsortedness points come from the pairs (4,6), (5,6), and (4,5).

  22. 1234257123

    123

    1500

    Returns: 558406

  23. 1234257123

    123

    100000

    Returns: 2504702368

  24. 2

    3

    100000

    Returns: 2418846750

  25. 100000

    100000

    100000

    Returns: 2489184225

  26. 1234257123

    123

    99997

    Returns: 2504601670

  27. 1

    1

    100000

    Returns: 0

  28. 23342

    243243

    100000

    Returns: 2485698323

  29. 1987653241

    1987653241

    100000

    Returns: 2502699622

  30. 1234257123

    123

    99999

    Returns: 2504658156

  31. 2000000000

    123456789

    100000

    Returns: 2502462773

  32. 1

    2

    100000

    Returns: 0

  33. 1

    0

    100000

    Returns: 0

  34. 1

    2147483646

    100000

    Returns: 4999750004

  35. 2

    15

    100000

    Returns: 2418846750

  36. 1111111119

    2133333997

    99999

    Returns: 2501210367

  37. 2

    2147483646

    100000

    Returns: 0

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: