Reversort solution Codejam 2021
Problem
Note: The main parts of the statements of the problems “Reversort” and “Reversort Engineering” are identical, except for the last paragraph. The problems can otherwise be solved independently. Reversort solution codejam 2021
Reversort is an algorithm to sort a list of distinct integers in increasing order. The algorithm is based on the “Reverse” operation. Each application of this operation reverses the order of some contiguous part of the list.
The pseudocode of the algorithm is the following:
Reversort(L):
for i := 1 to length(L) - 1
j := position with the minimum value in L between i and length(L), inclusive
Reverse(L[i..j])
After i−1i−1 iterations, the positions 1,2,…,i−11,2,…,i−1 of the list contain the i−1i−1 smallest elements of L, in increasing order. During the ii-th iteration, the process reverses the sublist going from the ii-th position to the current position of the ii-th minimum element. That makes the ii-th minimum element end up in the ii-th position. Reversort solution codejam 2021
For example, for a list with 44 elements, the algorithm would perform 33 iterations. Here is how it would process L=[4,2,1,3]L=[4,2,1,3]:
- i=1, j=3⟶L=[1,2,4,3]i=1, j=3⟶L=[1,2,4,3]
- i=2, j=2⟶L=[1,2,4,3]i=2, j=2⟶L=[1,2,4,3]
- i=3, j=4⟶L=[1,2,3,4]i=3, j=4⟶L=[1,2,3,4]
The most expensive part of executing the algorithm on our architecture is the Reverse operation. Therefore, our measure for the cost of each iteration is simply the length of the sublist passed to Reverse, that is, the value j−i+1j−i+1. The cost of the whole algorithm is the sum of the costs of each iteration. Reversort solution codejam 2021
In the example above, the iterations cost 33, 11, and 22, in that order, for a total of 66.
Given the initial list, compute the cost of executing Reversort on it.
Input
The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case consists of 2 lines. The first line contains a single integer NN, representing the number of elements in the input list. The second line contains NN distinct integers L1L1, L2L2, …, LNLN, representing the elements of the input list LL, in order.
Output
For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the total cost of executing Reversort on the list given as input.
Limits
Time limit: 10 seconds.
Memory limit: 1 GB. Reversort solution codejam 2021
Test Set 1 (Visible Verdict)
1≤T≤1001≤T≤100.
2≤N≤1002≤N≤100.
1≤Li≤N1≤Li≤N, for all ii.
Li≠LjLi≠Lj, for all i≠ji≠j.
Sample Reversort solution codejam 2021
Sample
Input
3 4 4 2 1 3 2 1 2 7 7 6 5 4 3 2 1
Output
Case #1: 6 Case #2: 1 Case #3: 12
Sample Case #1 is described in the statement above.
In Sample Case #2, there is a single iteration, in which Reverse is applied to a sublist of size 1. Therefore, the total cost is 1.
In Sample Case #3, the first iteration reverses the full list, for a cost of 7. After that, the list is already sorted, but there are 5 more iterations, each of which contributes a cost of 1.
Solution:
include <bits/stdc++.h>
using namespace std;
void solve(int t){
int n;
cin >> n;
vector a(n);
int cost = 0;
for(int& x : a){
cin >> x;
x–;
}
for(int i = 0; i < n; i++){
int j = i;
while(a[j] != i) j++;
cost += (j-i+1);
reverse(a.begin() + i, a.begin() + j + 1);
}
cout << “Case #” << t << “: “;
cout << (cost-1) << ‘\n’;
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
for(int t = 1; t <= T; t++) solve(t);
}
Also Read:
- [Solution] Reversort Engineering Solution Code Jam 2021
- [Solution] Median Sort Solution Code Jam 2021
- [Solution] Cheating Detection Solution Code Jam 2021
- [Solution] Moons and Umbrellas Solution Code Jam 2021
4 thoughts on “[Solution] Reversort solution Code Jam 2021”