USACO 2018 January Contest Bronze Division - Out of Place

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We want to see how many distinct values are off from Bessie's position for each possible choice.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ifstream cin("outofplace.in");
    ofstream cout("outofplace.out");

    int n;
    cin >> n;

    vector<int> v(n+1);
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    int ans = n;
    for(int i = 1; i <= n; i++)
    {
        int prv = 0;
        bool ok = 1;
        for(int j = 1; j <= n; j++)
        {
            if(j == i)
                continue;
            if(v[j] < prv)
                ok = 0;
            prv = v[j];
        }
        if(ok)
        {
            int cntdistinct = 0;
            int cntdistinct2 = 0;
            int poz = 0;
            for(int j = 1; j <= n; j++)
            {
                if(j == i)
                {
                    poz = cntdistinct2;
                    continue;
                }
                if(v[j] > prv)
                    cntdistinct2++;
                if(v[j] > prv && (v[j] < v[i] || (v[j] == v[i] && j < i)))
                    cntdistinct++;
                prv = v[j];
            }
            ans = min(ans, abs(poz - cntdistinct));
        }
    }

    cout << ans;
    return 0;
}

with open("outofplace.in", "r") as fin:
    tokens = fin.read().split()
n = int(tokens[0])
v = [0] + [int(tokens[i]) for i in range(1, n+1)]

ans = n
for i in range(1, n+1):
    prv = 0
    ok = True
    for j in range(1, n+1):
        if j == i:
            continue
        if v[j] < prv:
            ok = False
        prv = v[j]
    if ok:
        cntdistinct = 0
        cntdistinct2 = 0
        poz = 0
        for j in range(1, n+1):
            if j == i:
                poz = cntdistinct2
                continue
            if v[j] > prv:
                cntdistinct2 += 1
            if v[j] > prv and (v[j] < v[i] or (v[j] == v[i] and j < i)):
                cntdistinct += 1
            prv = v[j]
        ans = min(ans, abs(poz - cntdistinct))

with open("outofplace.out", "w") as fout:
    fout.write(str(ans))