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

Official Analysis (Java)

Time Complexity: $\mathcal{O}(N^2)$, where $N$ is the number of cows.

Define $Start_x$ and $End_x$ to be the indices of the first and last occurrences of cow $x$ in the input string, respectively. We want to count the number of pairs of cows $(i,j)$ such that cow $i$ enters before cow $j$ and leaves somewhere between cow $j$'s entry and exit. In other words, $Start_i < Start_j < End_i < End_j$.

Since $N$ is small, we can afford to iterate over all possibilities for $i$ and $j$ and check whether the condition above is satisfied in $\mathcal{O}(N^2)$ time.

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen("circlecross.in","r",stdin);
	freopen("circlecross.out","w",stdout);
	string s; cin >> s;
	int Start[26], Exit[26];
	//Set all elements of Start and End arrays to -1.

Alternative Implementation

Time Complexity: $\mathcal{O}(N^4)$

Due to the low constraints, we can iterate over all $\mathcal{O}(N^4)$ possible pairs of intersecting paths and check whether they represent two cows.

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen("circlecross.in","r",stdin);
	freopen("circlecross.out","w",stdout);
	string s; cin >> s;
	int ans = 0;
	for (int a = 0; a < s.size(); ++a)