USACO 2017 February Contest Bronze Division - Why Did the Cow Cross the Road II

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Brute force each pair of cows and try to count the number of changes.

Source codes

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

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

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

    string s;
    cin >> s;

    vector<pair<int, int> > positions(26);
    for(int i = 0; i < 52; i++)
    {
        int letter = s[i] - 'A';
        if(positions[letter].first == 0)
            positions[letter].first = i+1;
        else
            positions[letter].second = i+1;
    }

    int cnt = 0;
    for(int i = 0; i <= 26; i++)
        for(int j = 0; j <= 26; j++)
            if(i != j)
            {
                bool ok = 1;
                if(positions[j].first >= positions[i].first && positions[i].second >= positions[j].first)
                {
                    if(positions[j].second >= positions[i].first && positions[i].second >= positions[j].second)
                        ok = 0;
                }
                if(!(positions[j].first >= positions[i].first && positions[i].second >= positions[j].first))
                {
                    if(!(positions[j].second >= positions[i].first && positions[i].second >= positions[j].second))
                        ok = 0;
                }
                cnt += ok;
            }

    cout << cnt/2;
    return 0;
}

with open("circlecross.in", "r") as fin:
    s = fin.readline().strip()

positions = [[0, 0] for _ in range(26)]
for i, ch in enumerate(s):
    letter = ord(ch) - ord('A')
    if positions[letter][0] == 0:
        positions[letter][0] = i + 1
    else:
        positions[letter][1] = i + 1

cnt = 0
for i in range(26):
    for j in range(26):
        if i != j:
            a, b = positions[i]
            c, d = positions[j]
            ok = True
            if a <= c <= b:
                if a <= d <= b:
                    ok = False
            else:
                if not (a <= d <= b):
                    ok = False
            if ok:
                cnt += 1

with open("circlecross.out", "w") as fout:
    fout.write(str(cnt // 2))