USACO 2018 US Open Contest Silver Division - Out of Sorts

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We sort the data and find the maximum difference between the current position in the sorted array and the original position, as this is equivalent to the number of changes made by the bubble sort algorithm.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("sort.in");
ofstream cout("sort.out");

int main() {
    int n;
    cin >> n;

    vector<int> v(n + 1), srt(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        srt[i] = v[i];
    }
    sort(srt.begin(), srt.end());
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, i - (long long)(upper_bound(srt.begin(), srt.end(), v[i]) - srt.begin()) + 1);
    }
    cout << ans + 1;
    return 0;
}