MergeToSort
2021 Regional 2 · 2021-04-13 · by misof
Problem Statement
Given is a sequence A consisting of N positive integers. You would like to transform it into a sequence that is sorted in non-decreasing order.
The only allowed transformation step is taking two consecutive elements and replacing them by their sum.
Find and return the minimum number of steps needed.
In order to keep the input size small, the sequence is constructed pseudorandomly using the pseudocode given below. In the pseudocode, x^y denotes x to the power of y.
L = length(Aprefix)
for i = 0 to L-1:
A[i] = Aprefix[i]
state = seed
for i = L to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
b = blo + ((state / 1000) modulo (bhi-blo+1))
state = (state * 1103515245 + 12345) modulo 2^31
x = 2^(b-1)
A[i] = x + ((state / 10) modulo x)
Notes
- It can easily be shown that a solution always exists.
- The reference solution does not depend on the input being (pseudo)random.
- The constraints imply that all elements of A will satisfy 1 <= A[i] < 2^25.
Constraints
- N will be between 1 and 100,000, inclusive.
- Aprefix will have between 0 and 100 elements, inclusive.
- Aprefix will have at most N elements.
- Each element of Aprefix will be between 1 and 2^25 - 1, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- blo and bhi will satisfy 1 <= blo <= bhi <= 25.
4
{20, 10, 35, 38}
0
1
1
Returns: 1
The optimal solution is to merge the first two elements, producing the sorted sequence {30, 35, 38}.
5
{10, 10, 10, 10}
47
15
25
Returns: 0
The sequence {10, 10, 10, 10, 26361440} is already in non-decreasing order, no changes are needed.
15
{420, 470}
420047
9
10
Returns: 7
A = {420, 470, 547, 689, 892, 890, 822, 931, 488, 607, 354, 943, 315, 914, 321}
100000
{}
436734
1
25
Returns: 99717
100000
{}
252
1
1
Returns: 0
Submissions are judged against all 99 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MergeToSort with a public method int minSteps(int N, vector<int> Aprefix, int seed, int blo, int bhi) · 99 test cases · 2 s / 256 MB per case