Connection Status:
Competition Arena > BubbleSortIterations

BubbleSortIterations

SRM 359 · 2007-07-21 · by bmerry

SRM 359 · 2007-07-21 · by bmerry · Sorting
Class Name: BubbleSortIterations
Return Type: int
Method Name: numIterations
Arg Types: (vector<int>, vector<int>, int, int, int)
Problem Statement

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.

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
4)
{0}
{1, 2, 3, 4, 5, 6, 7, 0}
1
100
8
Returns: 8
5)
{100000}
{900000, 0, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000}
900000
1000000
10
Returns: 2

Tests for 64-bit in sequence generation.

6)
{2, 3, 4, 5, 6, 7}
{1, 0}
4
15
10
Returns: 7

Tests X.length > Y.length

7)
{1}
{10}
0
1000000
100000
Returns: 1

Maximum length sorted sequence, spanning the range

8)
{1}
{999990}
999995
1000000
100000
Returns: 100000

Maximum length decreasing sequence.

Submissions are judged against all 29 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BubbleSortIterations with a public method int numIterations(vector<int> X, vector<int> Y, int L0, int M, int n) · 29 test cases · 2 s / 256 MB per case

Submitting as anonymous