Why Did the Cow Cross the Road II

Solución 1

Explicación

Por las restricciones bajas, podemos iterar sobre todos los pares posibles de caminos que se cruzan y comprobar si representan dos vacas.

Implementación

Complejidad temporal: $\mathcal{O}(N^4)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("circlecross.in", "r", stdin);
	string crossings;
	cin >> crossings;
 
	int crossing_pairs = 0;
	// Iteramos por todos los caracteres del string
	for (int a = 0; a < crossings.size(); a++) {
		for (int b = a + 1; b < crossings.size(); b++) {
			for (int c = b + 1; c < crossings.size(); c++) {
				for (int d = c + 1; d < crossings.size(); d++) {
					/*
					 * Si encontramos dos caminos de entrada/salida tales que a < b < c < d,
					 * los caminos de las vacas (a, c) y (b, d) se cruzan,
					 * así que hay un par que se cruza
					 */
					crossing_pairs +=
					    (crossings[a] == crossings[c] && crossings[b] == crossings[d]);
				}
			}
		}
	}
 
	freopen("circlecross.out", "w", stdout);
	cout << crossing_pairs << endl;
}


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;
		// Iteramos por todos los caracteres del string
		for (int a = 0; a < crossings.length(); a++) {
			for (int b = a + 1; b < crossings.length(); b++) {
				for (int c = b + 1; c < crossings.length(); c++) {
					for (int d = c + 1; d < crossings.length(); d++) {
						/*
						 * Si encontramos dos caminos de entrada/salida tales que a < b < c <
						 * d, los caminos de las vacas (a, c) y (b, d) se
						 * cruzan, así que hay un par que se cruza
						 */
						crossingPairs += (crossings[a] == crossings[c] &&
						                  crossings[b] == crossings[d])
						                     ? 1
						                     : 0;
					}
				}
			}
		}
 
		io.println(crossingPairs);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


with open("circlecross.in") as read:
	crossings = read.readline().strip()
 
crossing_pairs = 0
# Iteramos por todos los caracteres del 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)):
				"""
				Si encontramos dos caminos de entrada/salida tales que a < b < c < d,
				los caminos de las vacas (a, c) y (b, d) se cruzan,
				así que hay un par que se cruza
				"""
				crossing_pairs += (
					crossings[a] == crossings[c] and crossings[b] == crossings[d]
				)
 
print(crossing_pairs, file=open("circlecross.out", "w"))

Solución 2

Explicación

Definimos $\texttt{start}_x$ y $\texttt{end}_x$ como los índices de la primera y la última aparición de la vaca $x$ en el string de entrada, respectivamente. Queremos contar la cantidad de pares de vacas $(i,j)$ tales que la vaca $i$ entra antes que la vaca $j$ y sale en algún punto entre la entrada y la salida de la vaca $j$ . Esta condición se puede formular como la desigualdad $\texttt{start}_i < \texttt{start}_j < \texttt{end}_i < \texttt{end}_j$ .

Como $N$ es pequeño, podemos permitirnos iterar sobre todas las posibilidades de $i$ y $j$ y comprobar si se cumple la condición anterior.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$ , donde $N$ es la cantidad de vacas.

C++JavaPython


#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);
	for (int i = 0; i < crossings.size(); i++) {
		if (start[crossings[i] - 'A'] == -1) {
			start[crossings[i] - 'A'] = i;
		} else {
			end[crossings[i] - 'A'] = i;
		}
	}
 
	int crossing_pairs = 0;
	// Revisamos todos los pares de vacas (i, j)
	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < 26; j++) {
			// Sumamos 1 si se cumple la condición de la explicación
			crossing_pairs +=
			    (start[i] < start[j] && start[j] < end[i] && end[i] < end[j]);
		}
	}
 
	freopen("circlecross.out", "w", stdout);
	cout << crossing_pairs << endl;
}


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];
		Arrays.fill(start, -1);
		Arrays.fill(end, -1);
		for (int i = 0; i < crossings.length(); i++) {
			int cID = crossings.charAt(i) - 'A';
			if (start[cID] == -1) {
				start[cID] = i;
			} else {
				end[cID] = i;
			}
		}
 
		int crossingPairs = 0;
		// Revisamos todos los pares de vacas (i, j)
		for (int i = 0; i < 26; i++) {
			for (int j = 0; j < 26; j++) {
				// Sumamos 1 si se cumple la condición de la explicación
				crossingPairs +=
				    (start[i] < start[j] && start[j] < end[i] && end[i] < end[j]) ? 1
				                                                                  : 0;
			}
		}
 
		io.println(crossingPairs);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


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:
		end[c_id] = v
 
crossing_pairs = 0
# Revisamos todos los pares de vacas (i, j)
for i in range(26):
	for j in range(26):
		# Sumamos 1 si se cumple la condición de la explicación
		crossing_pairs += start[i] < start[j] and start[j] < end[i] and end[i] < end[j]
 
print(crossing_pairs, file=open("circlecross.out", "w"))

Solución 3

Explicación

Para cada vaca $i$ , vemos qué vacas tienen exactamente un punto de entrada/salida entre el punto de entrada y el de salida de la vaca $i$ . Observemos que para cada una de esas vacas $j$ , sabemos que se cruzan con $i$ , así que agregamos el par $(i, j)$ a un conjunto hash que contiene todos los cruces. Hay que cuidar de no guardar tanto $(i, j)$ como $(j, i)$ en el conjunto, porque eso sobrecontaría.

La respuesta final es la longitud del conjunto hash con todos los pares.

Implementación

Complejidad temporal: $\mathcal{O}(T^2)$ , donde $T$ es la longitud del string de FJ.

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("circlecross.in", "r", stdin);
	string crossings;
	cin >> crossings;
 
	// Equivalente al arreglo start de la Solución 2
	vector<int> first_found(26, -1);
	set<pair<char, char>> found_crossings;
	for (int i = 0; i < crossings.size(); i++) {
		int c_id = crossings[i] - 'A';
		if (first_found[c_id] == -1) {
			// Marcamos el punto de entrada de esta vaca
			first_found[c_id] = i;
			continue;
		} else {
			/*
			 * Conjunto de vacas que tienen exactamente un punto entre
			 * el punto de entrada y el de salida de la vaca actual
			 */
			set<char> appearances;
			int start = first_found[c_id] + 1;
			int end = i;
			for (int j = start; j < end; j++) {
				if (appearances.count(crossings[j])) {
					appearances.erase(crossings[j]);
				} else {
					appearances.insert(crossings[j]);
				}
			}
 
			for (int c : appearances) {
				pair<char, char> intersection{crossings[i], c};
				// Ordenamos para guardar solo (i, j), y no también (j, i)
				if (intersection.first > intersection.second) {
					swap(intersection.first, intersection.second);
				}
				found_crossings.insert(intersection);
			}
		}
	}
 
	freopen("circlecross.out", "w", stdout);
	cout << found_crossings.size() << endl;
}


import java.io.*;
import java.util.*;
 
public class CircleCross {
	// BeginCodeSnip{Crossing Pair Class}
	static class CrossingPair {
		public char a;
		public char b;
 
		public CrossingPair(char a, char b) {
			this.a = a;
			this.b = b;
		}
 
		@Override
		public int hashCode() {
			return Objects.hash(a, b);
		}
 
		@Override
		public boolean equals(Object obj) {
			return (obj instanceof CrossingPair && a == ((CrossingPair)obj).a &&
			        b == ((CrossingPair)obj).b);
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("circlecross");
		String crossings = io.next();
 
		// Equivalente al arreglo start de la Solución 2
		int[] firstFound = new int[26];
		Arrays.fill(firstFound, -1);
		Set<CrossingPair> foundCrossings = new HashSet<>();
		for (int i = 0; i < crossings.length(); i++) {
			int cID = crossings.charAt(i) - 'A';
			if (firstFound[cID] == -1) {
				// Marcamos el punto de entrada de esta vaca
				firstFound[cID] = i;
				continue;
			} else {
				/*
				 * Conjunto de vacas que tienen exactamente un punto entre
				 * el punto de entrada y el de salida de la vaca actual
				 */
				Set<Character> appearances = new HashSet<>();
				int start = firstFound[cID] + 1;
				int end = i;
				for (int j = start; j < end; j++) {
					if (appearances.contains(crossings.charAt(j))) {
						appearances.remove(crossings.charAt(j));
					} else {
						appearances.add(crossings.charAt(j));
					}
				}
 
				for (char c : appearances) {
					CrossingPair pair = new CrossingPair(crossings.charAt(i), c);
					// Ordenamos para guardar solo (i, j), y no
					// también (j, i)
					if (pair.a > pair.b) {
						char temp = pair.a;
						pair.a = pair.b;
						pair.b = temp;
					}
					foundCrossings.add(pair);
				}
			}
		}
 
		io.println(foundCrossings.size());
		io.close();
	}
 
	// CodeSnip{Kattio}
}


with open("circlecross.in") as read:
	crossings = read.readline().strip()
 
# Equivalente al arreglo start de la Solución 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:
		# Marcamos el punto de entrada de esta vaca
		first_found[c_id] = i
		continue
	else:
		"""
		Conjunto de vacas que tienen exactamente un punto entre
		el punto de entrada y el de salida de la vaca actual
		"""
		appearances = set()
		start = first_found[c_id] + 1
		end = i
		for j in range(start, end):
			if crossings[j] in appearances:
				appearances.remove(crossings[j])
			else:
				appearances.add(crossings[j])
 
		for c in appearances:
			# Ordenamos para guardar solo (i, j), y no también (j, i)
			intersection = tuple(sorted([crossings[i], c]))
			found_crossings.add(intersection)
 
print(len(found_crossings), file=open("circlecross.out", "w"))