Skip to Content
CTRL K

Team Building

Análisis oficial (C++) 

Explicación

Digamos que queremos encontrar la respuesta para alguna subsección de la entrada de ejemplo. Entonces, necesitaríamos la cantidad de elementos a considerar para Farmer John y Farmer Paul, y el tamaño del equipo. Un enfoque naive sería recorrer esto en tiempo NMKNMK, y debido a las cotas bajas de NN, MM y KK, esto sí entra dentro del límite de tiempo. Así que simplemente ejecutamos una DP bottom-up donde

dp[i][j][k]\texttt{dp}[i][j][k] = la cantidad de equipos de tamaño kk después de haber considerado las primeras ii vacas del equipo de Farmer John, las primeras jj vacas del equipo de Farmer Paul.

Luego, nuestra transición sería:

dp[i][j][k]\texttt{dp}[i][j][k] = dp[i−1][j][k]+dp[i][j−1][k]−dp[i−1][j−1][k]\texttt{dp}[i - 1][j][k] + \texttt{dp}[i][j - 1][k] - \texttt{dp}[i - 1][j - 1][k]

Si la ii-ésima vaca de FJ es mayor que la jj-ésima vaca de FP, también sumamos dp[i−1][j−1][k−1]\texttt{dp}[i - 1][j - 1][k - 1], porque al emparejar esas dos vacas, solo nos quedan k−1k - 1 lugares más por considerar.

Implementación

Complejidad temporal: O(NMK)\mathcal{O}(NMK)

#include <bits/stdc++.h>
 
using std::vector;
const int MOD = 1e9 + 9;
 
int main() {
	freopen("team.in", "r", stdin);
	freopen("team.out", "w", stdout);
 
	int n, m, k;
	std::cin >> n >> m >> k;
 
	vector<long long> fj(n), fp(m);
 
	for (int i = 0; i < n; i++) { std::cin >> fj[i]; }
 
	for (int i = 0; i < m; i++) { std::cin >> fp[i]; }
 
	std::sort(fj.rbegin(), fj.rend());
	std::sort(fp.rbegin(), fp.rend());
 
	/*
	 * dp[i][j][k] = la cantidad de equipos de tamaño k después de haber
	 * considerado las primeras $i$ vacas del equipo de Farmer John, las
	 * primeras $j$ vacas del equipo de Farmer Paul.
	 */
	vector<vector<vector<long long>>> dp(
	    n + 1, vector<vector<long long>>(m + 1, vector<long long>(k + 1)));
 
	// caso base: hay una forma de construir un equipo de tamaño cero.
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) { dp[i][j][0] = 1; }
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int s = 1; s <= k; s++) {
				/*
				 * la cantidad actual de equipos será al menos la
				 * cantidad de equipos de no incluir i y no incluir j
				 */
				dp[i + 1][j + 1][s] += dp[i + 1][j][s];
				dp[i + 1][j + 1][s] += dp[i][j + 1][s];
				dp[i + 1][j + 1][s] -= dp[i][j][s];
 
				if (fj[i] > fp[j]) { dp[i + 1][j + 1][s] += dp[i][j][s - 1]; }
 
				// evitar resultados negativos
				dp[i + 1][j + 1][s] += MOD;
				dp[i + 1][j + 1][s] %= MOD;
			}
		}
	}
 
	std::cout << dp[n][m][k] << std::endl;
}
import java.io.*;
import java.util.*;
 
public class Team {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("team");
		final int MOD = 1000000009;
 
		int n = io.nextInt();
		int m = io.nextInt();
		int k = io.nextInt();
 
		int[] fj = new int[n];
		for (int i = 0; i < n; i++) { fj[i] = io.nextInt(); }
 
		int[] fp = new int[m];
		for (int i = 0; i < m; i++) { fp[i] = io.nextInt(); }
 
		Arrays.sort(fj);
		Arrays.sort(fp);
 
		/*
		 * dp[i][j][k] = la cantidad de equipos de tamaño k después de haber
		 * considerado las primeras i vacas del equipo de Farmer John, las
		 * primeras j vacas del equipo de Farmer Paul.
		 */
		long[][][] dp = new long[n + 1][m + 1][k + 1];
 
		// caso base: hay una forma de construir un equipo de tamaño cero.
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= m; j++) { dp[i][j][0] = 1; }
		}
 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				for (int s = 1; s <= k; s++) {
					// transiciones de dp
					dp[i + 1][j + 1][s] += dp[i + 1][j][s];
					dp[i + 1][j + 1][s] += dp[i][j + 1][s];
					dp[i + 1][j + 1][s] -= dp[i][j][s];
 
					if (fj[i] > fp[j]) { dp[i + 1][j + 1][s] += dp[i][j][s - 1]; }
 
					// evitar resultados negativos
					dp[i + 1][j + 1][s] += MOD;
					dp[i + 1][j + 1][s] %= MOD;
				}
			}
		}
 
		io.println(dp[n][m][k]);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
Fundamentos