Statistics

Problem Statement for "BubbleSortIterations"

Problem Statement

Bubble-sort is a well-known sorting algorithm, although not a very efficient one. In each iteration of bubble-sort, the algorithm works from start to end along a list, comparing each pair of adjacent elements. If the adjacent elements are out of order, then they are swapped. If no elements are swapped in an iteration, then the list is sorted and the algorithm terminates; otherwise, the algorithm continues with another iteration. In order to analyze the performance of bubble-sort, you want to determine how many iterations are required to sort a given list in non-decreasing order. The list might be quite large, so it will be codified in the following way. You will be given int[]s X and Y, and ints L0, M, and n. Generate the list L of length n using the following pseudo-code. Array indices are 0-based. 
L[0] = L0
for i := 1 to n-1
    L[i] = (L[i-1] * X[i % length(X)] + Y[i % length(Y)]) MOD M
You must calculate the number of iterations required to bubble-sort L in non-decreasing order.

Definition

Class:
BubbleSortIterations
Method:
numIterations
Parameters:
int[], int[], int, int, int
Returns:
int
Method signature:
int numIterations(int[] X, int[] Y, int L0, int M, int n)
(be sure your method is public)

Notes

  • The input is encoded purely for convenience. The intended solution does not rely on any properties of the way it is generated, and will work for any list L.

Constraints

  • X and Y will each contain between 1 and 50 elements, inclusive.
  • Each element of X and Y will be between 0 and M-1, inclusive.
  • L0 will be between 0 and M-1, inclusive.
  • M will be between 1 and 1,000,000, inclusive.
  • n will be between 1 and 100,000, inclusive.

Examples

  1. {0}

    {10, 1, 5, 2, 3}

    10

    100

    5

    Returns: 3

    The generated sequence is 10, 1, 5, 2, 3. After one iteration it is 1, 5, 2, 3, 10. After two it is 1, 2, 3, 5, 10. The third iteration detects that the sequence is now sorted.

  2. {0}

    {1, 3, 5, 7, 9}

    1

    100

    5

    Returns: 1

    The generated sequence is 1, 3, 5, 7, 9. The sequence is already sorted, but one iteration is required to detect this.

  3. {999998}

    {500000}

    500000

    1000000

    100

    Returns: 1

    Be careful not to overflow when generating L.

  4. {234, 56, 567, 3147, 23464, 57128, 1254, 45, 23247, 1347, 145, 123}

    {3413, 171, 58, 569, 40, 467, 2456, 246, 2684, 5, 61, 8, 258, 24524, 2, 58, 245, 674}

    1

    99991

    100000

    Returns: 99228

  5. {0}

    {1, 2, 3, 4, 5, 6, 7, 0}

    1

    100

    8

    Returns: 8

  6. {100000}

    {900000, 0, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000}

    900000

    1000000

    10

    Returns: 2

    Tests for 64-bit in sequence generation.

  7. {2, 3, 4, 5, 6, 7}

    {1, 0}

    4

    15

    10

    Returns: 7

    Tests X.length > Y.length

  8. {1}

    {10}

    0

    1000000

    100000

    Returns: 1

    Maximum length sorted sequence, spanning the range

  9. {1}

    {999990}

    999995

    1000000

    100000

    Returns: 100000

    Maximum length decreasing sequence.

  10. {1}

    {0}

    1234

    99991

    99999

    Returns: 1

  11. {1}

    {1}

    50000

    100000

    99998

    Returns: 50001

  12. {1}

    {99999}

    50000

    100000

    100000

    Returns: 50001

  13. {999999}

    {999995,5}

    500000

    1000000

    99999

    Returns: 99999

  14. {999999}

    {4,999995}

    1

    1000000

    100000

    Returns: 50000

  15. {0}

    {1,3,2}

    1

    10

    3

    Returns: 2

  16. {0}

    {2,1,3}

    2

    10

    3

    Returns: 2

  17. {0}

    {2,3,1}

    2

    10

    3

    Returns: 3

  18. {0}

    {3,1,2}

    3

    10

    3

    Returns: 2

  19. {1}

    {3000}

    0

    900000

    100000

    Returns: 99568

  20. {1}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 999900}

    999000

    1000000

    99901

    Returns: 99900

  21. {1}

    {999999,999999,999999,999999,999999,999999,999999,999999,999999,999999, 999999,999999,999999,999999,999999,999999,999999,999999,999999,999999, 999999,999999,999999,999999,999999,999999,999999,999999,999999,999999, 999999,999999,999999,999999,999999,999999,999999,999999,999999,999999, 999999,999999,999999,999999,999999,999999,999999,999999,999999,100}

    5

    1000000

    99997

    Returns: 93

  22. {0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0}

    {32, 31, 29, 30, 25, 26, 28, 27, 17, 18, 20, 19, 24, 23, 21, 22, 1, 2, 4, 3, 8, 7, 5, 6, 16, 15, 13, 14, 9, 10, 12, 11}

    32

    100

    32

    Returns: 22

  23. {234, 56, 567, 3147, 23464, 57128, 1254, 45, 23247, 1347, 145, 123 }

    {3413, 171, 58, 569, 40, 467, 2456, 246, 2684, 5, 61, 8, 258, 24524, 2, 58, 245, 674 }

    1

    99991

    100000

    Returns: 99228

  24. {1 }

    {999999 }

    0

    1000000

    100000

    Returns: 99999

  25. {567, 5234, 42 }

    {3434, 5342, 3245 }

    563653

    1000000

    100000

    Returns: 99681

  26. {1 }

    {1 }

    1

    3

    3

    Returns: 3

  27. {1 }

    {1 }

    1

    2

    2

    Returns: 2

  28. {1 }

    {1 }

    1

    2

    100000

    Returns: 50001

  29. {0 }

    {3, 4, 2, 1 }

    3

    10000

    4

    Returns: 4

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: