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

Authors: Benjamin Qi, Danh Ta Chi Thanh, Ryan Chou, Ananth Kashyap, Ben Dodge, Ishwarendra Jha

Edit This Page

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: O(N4)\mathcal{O}(N^4)

C++

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


int main() {
	freopen("circlecross.in", "r", stdin);
	string crossings;
	cin >> crossings;


	int crossing_pairs = 0;
	// Iterate through all characters of the string

Java

import java.io.*;
import java.util.*;


public class CircleCross {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("circlecross");
		String crossings = io.next();


		int crossingPairs = 0;
		// Iterate through all characters of the string

Python

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 startx\texttt{start}_x and endx\texttt{end}_x to be the indices of the first and last occurrences of cow xx in the input string, respectively. We want to count the number of pairs of cows (i,j)(i,j) such that cow ii enters before cow jj and leaves somewhere between cow jj's entry and exit. This condition can be formulated as the inequality starti<startj<endi<endj\texttt{start}_i < \texttt{start}_j < \texttt{end}_i < \texttt{end}_j.

Since NN is small, we can afford to iterate over all possibilities for ii and jj and check whether the above condition is satisfied.

Implementation

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

C++

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


int main() {
	freopen("circlecross.in", "r", stdin);
	string crossings;
	cin >> crossings;


	vector<int> start(26, -1);
	vector<int> end(26, -1);

Java

import java.io.*;
import java.util.*;


public class CircleCross {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("circlecross");
		String crossings = io.next();


		int[] start = new int[26];
		int[] end = new int[26];

Python

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 ii, we check which cows have exactly one entry/exit point between cow ii's entry and exit point. Notice that for each of these cows jj, we know that they must cross ii, so we add the pair (i,j)(i, j) to a hash set containing all crossings. We must take care to not store both (i,j)(i, j) and (j,i)(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: O(T2)\mathcal{O}(T^2), where TT is the length of FJ's string.

C++

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


int main() {
	freopen("circlecross.in", "r", stdin);
	string crossings;
	cin >> crossings;


	// Equivalent to the start array in Solution 2
	vector<int> first_found(26, -1);

Java

import java.io.*;
import java.util.*;


public class CircleCross {
 	Code Snippet: Crossing Pair Class (Click to expand)


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("circlecross");
		String crossings = io.next();

Python

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

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum