SortingInIterations

TCO07 Round 4 · 2007-03-07 · by Mike Mirzayanov

TCO07 Round 4 · 2007-03-07 · by Mike Mirzayanov · Simple Math, Simple Search, Iteration

Show categories

Class Name: SortingInIterations

Return Type: long

Method Name: sum

Arg Types: (int, int, int, int, int, int, int)

Problem Statement

John is going to sort a sequence of numbers using a special algorithm. First all numbers a[0], a[1], a[2], ..., a[n-1] are written on a blackboard. During the first iteration, John checks all numbers in the order of increasing indices (so, he checks a[0] first, followed by a[1], a[2],..., and ends the first iteration with a[n - 1]). At any moment, he can erase the number he is looking at from the blackboard and write it into his notebook. When looking at number a[i], John erases it from the board and writes into his notebook if and only if it is equal to the smallest unerased number on the blackboard. All other iterations are similar to the first one, but, of course, John checks only the numbers which were not erased from the blackboard. The process is over when all numbers are erased from the board and written into John's notebook in non-descending order.

For example, if John is given a sequence of {3, 5, 1, 4, 2}, the process will go as follows. During the first iteration, John will erase 1 and 2 from the board, writing them to the notebook and changing the sequence to {3, 5, 4}. During the second iteration, 3 and 4 will be written into his notebook, so only 5 will be on the board during the third iteration.

You will be given four ints: a0, X, Y, M, n. The sequence John will need to sort can be generated using the following algorithm:

a[0] = a0;
a[i] = (a[i - 1] * X + Y) mod M, for 0 &lt i &lt n (where mod is a remainder operation.).

You will be given two more ints start and finish. Return the sum of all numbers John will erase from the board during all iterations with indices (1-based) between start and finish, inclusive. If John will need less than finish iterations to sort the sequence, return -1.

Constraints

a0 will be between 0 and M-1, inclusive.
X will be between 0 and 4*10^5, inclusive.
Y will be between 0 and 4*10^5, inclusive.
M will be between 1 and 4*10^5, inclusive.
n will be between 1 and 4*10^5, inclusive.
start will be between 1 and 4*10^5, inclusive.
finish will be between start and 4*10^5, inclusive.

Examples

4
2
0
7
10
1
1
Returns: 5

The sequence is 4 1 2 4 1 2 4 1 2 4. The bolded elements will be erased during the first iteration.

1
0
0
5
5
1
2
Returns: 1

The sequence is 1, 0, 0, 0, 0. We need two iterations to erase all numbers.

7
6
9
10
10
2
3
Returns: 20

0
1
1
100000
100000
1
1
Returns: 4999950000

Be careful with overflows.

399999
1
399999
400000
400000
1
400000
Returns: 79999800000

1
7
0
10
10
1
10
Returns: -1

John needs only four iterations.

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

Coding Area

Language: C++17 · define a public class SortingInIterations with a public method long long sum(int a0, int X, int Y, int M, int n, int start, int finish) · 135 test cases · 2 s / 256 MB per case