TopCoder problem "BubbleSortIterations" used in SRM 359 (Division I Level Three)



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

0)
    
{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.
1)
    
{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.
2)
    
{999998}
{500000}
500000
1000000
100
Returns: 1
Be careful not to overflow when generating L.
3)
    
{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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7854

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10770&pm=7854

Writer:

bmerry

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Sorting