Cow Gymnastics

Explicación

Como dice el enunciado, contamos en cuántas sesiones la vaca A terminó delante de la vaca B, para todos los pares. Si la vaca A supera a la vaca B en las $K$ sesiones, incrementamos la respuesta. Obtenemos la salida final una vez que iteramos sobre todos los pares.

Solución en video

Por David Li

Video de YouTube (YV1rcD-sB00)

Código de la solución en video

C++Java


#include <iostream>
using namespace std;
 
int N, K;
int rankings[10][20], better[20][20];
 
int main() {
	freopen("gymnastics.in", "r", stdin);
	freopen("gymnastics.out", "w", stdout);
 
	// leemos la entrada
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < N; j++) {
			cin >> rankings[i][j];
			rankings[i][j]--;
		}
	}
 
	// calculamos la cantidad de veces que la vaca a queda delante de la vaca b
	for (int i = 0; i < K; i++) {              // recorremos las pruebas
		for (int j = 0; j < N; j++) {          // rankings[i][j] = vaca a
			for (int k = j + 1; k < N; k++) {  // rankings[i][k] = vaca b
				better[rankings[i][j]][rankings[i][k]]++;
			}
		}
	}
 
	// calculamos la respuesta
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (better[i][j] == K)  // si la vaca i queda delante de la vaca j K veces, entonces
				ans++;
		}
	}
 
	// imprimimos la respuesta
	cout << ans;
 
	return 0;
}


import java.io.*;
import java.util.*;
 
public class gymnastics {
	public static void main(String[] args) throws IOException {
		// leemos la entrada
		BufferedReader br = new BufferedReader(new FileReader("gymnastics.in"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
 
		int[][] data = new int[K][N];  // guarda los datos de entrada
		int[][] better =
		    new int[N][N];  // guarda cuántas veces la vaca a queda delante de la vaca b
 
		// leemos la entrada
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				data[i][j] = Integer.parseInt(st.nextToken()) - 1;
			}
		}
 
		// calculamos la cantidad de veces que la vaca a queda delante de la vaca b
		for (int i = 0; i < K; i++) {              // recorremos las pruebas
			for (int j = 0; j < N; j++) {          // data[i][j] = vaca a
				for (int k = j + 1; k < N; k++) {  // data[i][k] = vaca b
					better[data[i][j]][data[i][k]]++;
				}
			}
		}
 
		// calculamos la respuesta
		int ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (better[i][j] == K)  // si la vaca i queda delante de la vaca j K veces
				                        // entonces incrementamos la respuesta
					ans++;
			}
		}
 
		// imprimimos la respuesta
		PrintWriter out = new PrintWriter("gymnastics.out");
		out.print(ans);
		out.close();
	}
}

Implementación

Complejidad temporal: $\mathcal{O}(K \cdot N^3)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
template <typename T> int index(const vector<T> &vec, const T &n) {
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] == n) { return i; }
	}
	return -1;
}
 
int main() {
	std::ifstream read("gymnastics.in");
	int session_num;
	int cow_num;
	read >> session_num >> cow_num;
	vector<vector<int>> sessions(session_num, vector<int>(cow_num));
	for (int s = 0; s < session_num; s++) {
		for (int c = 0; c < cow_num; c++) {
			read >> sessions[s][c];
			sessions[s][c]--;
		}
	}
 
	int better_pairs = 0;
	for (int c1 = 0; c1 < cow_num; c1++) {
		for (int c2 = 0; c2 < cow_num; c2++) {
			if (c1 == c2) { continue; }
 
			bool better = true;
			for (const vector<int> &s : sessions) {
				if (index(s, c1) < index(s, c2)) {
					better = false;
					break;
				}
			}
			better_pairs += better;
		}
	}
 
	std::ofstream("gymnastics.out") << better_pairs << endl;
}


import java.io.*;
import java.util.*;
 
public class Gymnastics {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("gymnastics.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int sessionNum = Integer.parseInt(initial.nextToken());
		int cowNum = Integer.parseInt(initial.nextToken());
		int[][] sessions = new int[sessionNum][cowNum];
		for (int s = 0; s < sessionNum; s++) {
			StringTokenizer session = new StringTokenizer(read.readLine());
			for (int c = 0; c < cowNum; c++) {
				sessions[s][c] = Integer.parseInt(session.nextToken()) - 1;
			}
		}
 
		int betterPairs = 0;
		for (int c1 = 0; c1 < cowNum; c1++) {
			for (int c2 = 0; c2 < cowNum; c2++) {
				if (c1 == c2) { continue; }
 
				boolean valid = true;
				for (int[] s : sessions) {
					if (index(s, c1) < index(s, c2)) {
						valid = false;
						break;
					}
				}
 
				if (valid) { betterPairs++; }
			}
		}
 
		PrintWriter written = new PrintWriter("gymnastics.out");
		written.println(betterPairs);
		written.close();
	}
 
	static int index(int[] arr, int n) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == n) { return i; }
		}
		return -1;
	}
}


with open("gymnastics.in") as read:
	session_num, cow_num = [int(i) for i in read.readline().split()]
	sessions = []
	for _ in range(session_num):
		sessions.append([int(c) - 1 for c in read.readline().split()])
 
better_pairs = 0
for c1 in range(cow_num):
	for c2 in range(cow_num):
		if c1 == c2:
			continue
 
		for s in sessions:
			if s.index(c1) < s.index(c2):
				break
		else:
			better_pairs += 1
 
print(better_pairs, file=open("gymnastics.out", "w"))

Solución alternativa

Generamos el ranking a medida que leemos los datos.

Podemos crear un arreglo 2D de booleanos que indica si la vaca $A$ tiene un ranking más alto que la vaca $B$ en algún momento. Después de leer cada ranking, para todos los $\frac{N(N-1)}{2}$ pares ponemos $b[A][B]=\text{true}$ .

Luego iteramos por todos los pares en tiempo $\mathcal{O}(N^2)$ y comprobamos si cumplen la condición. Al menos uno de $b[A][B]$ y $b[B][A]$ debe ser true, y por lo tanto solo hay que comprobar si ambos son true. Si uno de ellos es false, incrementamos nuestro $\texttt{count}$ en 1. Esto es porque si ambos son true, entonces el par cambia el orden del ranking en algún momento y no es válido. Si solo uno es true, entonces el par mantuvo un orden consistente.

Notemos que al menos uno de ellos debe ser true, ya que en cada ranking o $A>B$ o $B>A$ .

Implementación

Complejidad temporal: $\mathcal{O}(K \cdot N^2)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	std::ifstream read("gymnastics.in");
	int session_num;
	int cow_num;
	read >> session_num >> cow_num;
 
	/*
	 * better[c1][c2] = true
	 * si c1 fue mejor que c2 en *alguna* sesión (indexación desde cero).
	 */
	vector<vector<bool>> better(cow_num, vector<bool>(cow_num));
	for (int s = 0; s < session_num; s++) {
		vector<int> session(cow_num);
		for (int &c : session) {
			read >> c;
			c--;
		}
		for (int i = 0; i < session.size(); i++) {
			for (int j = i + 1; j < session.size(); j++) {
				better[session[j]][session[i]] = true;
			}
		}
	}
 
	int better_pairs = 0;
	for (int c1 = 0; c1 < cow_num; c1++) {
		for (int c2 = c1 + 1; c2 < cow_num; c2++) {
			better_pairs += !better[c1][c2] || !better[c2][c1];
		}
	}
 
	std::ofstream("gymnastics.out") << better_pairs << endl;
}


import java.io.*;
import java.util.*;
 
public class Gymnastics {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("gymnastics.in"));
 
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int sessionNum = Integer.parseInt(initial.nextToken());
		int cowNum = Integer.parseInt(initial.nextToken());
 
		/*
		 * better[c1][c2] = true
		 * si c1 fue mejor que c2 en *alguna* sesión (indexación desde cero).
		 */
		boolean[][] better = new boolean[cowNum][cowNum];
		for (int s = 0; s < sessionNum; s++) {
			StringTokenizer line = new StringTokenizer(read.readLine());
			int[] session = new int[cowNum];
			for (int c = 0; c < cowNum; c++) {
				session[c] = Integer.parseInt(line.nextToken()) - 1;
			}
 
			for (int i = 0; i < session.length; i++) {
				for (int j = i + 1; j < session.length; j++) {
					better[session[j]][session[i]] = true;
				}
			}
		}
 
		int betterPairs = 0;
		for (int c1 = 0; c1 < cowNum; c1++) {
			for (int c2 = c1 + 1; c2 < cowNum; c2++) {
				if (!better[c1][c2] || !better[c2][c1]) { betterPairs++; }
			}
		}
 
		PrintWriter written = new PrintWriter("gymnastics.out");
		written.println(betterPairs);
		written.close();
	}
}


with open("gymnastics.in") as read:
	session_num, cow_num = [int(i) for i in read.readline().split()]
	"""
	better[c1][c2] = True
	si c1 fue mejor que c2 en *alguna* sesión (indexación desde cero).
	"""
	better = [[False for _ in range(cow_num)] for _ in range(cow_num)]
	for _ in range(session_num):
		session = [int(c) - 1 for c in read.readline().split()]
		for i in range(len(session)):
			for j in range(i + 1, len(session)):
				better[session[j]][session[i]] = True
 
better_pairs = 0
for c1 in range(cow_num):
	for c2 in range(c1 + 1, cow_num):
		better_pairs += not better[c1][c2] or not better[c2][c1]
 
print(better_pairs, file=open("gymnastics.out", "w"))