Official Analysis (Java)

Solution 1

Explanation

Due to the low constraints, we can iterate over all possible pairs of intersecting paths and check whether they represent two cows.

Implementation

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

Copy
with open("circlecross.in") as read:
	crossings = read.readline().strip()

crossing_pairs = 0
# Iterate through all characters of the string
for a in range(len(crossings)):
	for b in range(a + 1, len(crossings)):
		for c in range(b + 1, len(crossings)):
			for d in range(c + 1, len(crossings)):
				"""

Solution 2

Explanation

Define $\texttt{start}_x$ and $\texttt{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. This condition can be formulated as the inequality $\texttt{start}_i < \texttt{start}_j < \texttt{end}_i < \texttt{end}_j$.

Since $N$ is small, we can afford to iterate over all possibilities for $i$ and $j$ and check whether the above condition is satisfied.

Implementation

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

Copy
with open("circlecross.in") as read:
	crossings = read.readline().strip()

start = [-1 for _ in range(26)]
end = [-1 for _ in range(26)]
for v, c in enumerate(crossings):
	c_id = ord(c) - ord("A")
	if start[c_id] == -1:
		start[c_id] = v
	else:

Solution 3

Explanation

For every cow $i$, we check which cows have exactly one entry/exit point between cow $i$'s entry and exit point. Notice that for each of these cows $j$, we know that they must cross $i$, so we add the pair $(i, j)$ to a hash set containing all crossings. We must take care to not store both $(i, j)$ and $(j, i)$ in the set, as that would result in overcounting.

Our final answer is the length of the hash set with all the pairs.

Implementation

Time Complexity: $\mathcal{O}(T^2)$, where $T$ is the length of FJ's string.

Copy
with open("circlecross.in") as read:
	crossings = read.readline().strip()

# Equivalent to the start array in Solution 2
first_found = [-1 for _ in range(26)]
found_crossings = set()
for i in range(len(crossings)):
	c_id = ord(crossings[i]) - ord("A")
	if first_found[c_id] == -1:
		# Mark the entry point of this cow