Coding Company

Explicación

Primero, ordenamos a las personas. Esto nos permite expresar la contribución de cada equipo como $(\text{Skill of last person}) - (\text{Skill of first person})$ . Sea $s_i$ la habilidad de la $i$ -ésima persona.

$dp[i][j][k] =$ El número de formas de formar equipos con las primeras $i$ personas tal que hay $j$ equipos “inconclusos” y la penalización total hasta el momento es $k$ . Si la $l$ -ésima persona es la menos habilidosa de un equipo inconcluso, definimos su contribución a la penalización como $-s_l$ . De forma similar, terminar un equipo con la persona $r$ contribuye $s_r$ a la penalización. Estas definiciones siguen directamente de la observación previa de que la contribución de un equipo es $s_r - s_l$ .

Hay 4 casos cuando transicionamos de $i - 1$ a $i$ :

Formamos un equipo que consiste solo de la persona $i$ .
- $dp[i - 1][j][k]$ transiciona al estado $dp[i][j][k]$ (los equipos inconclusos y la penalización no se ven afectados).
Agregamos a la persona $i$ a un equipo inconcluso.
- Esto transiciona al estado $dp[i][j][k]$ (de nuevo, los equipos inconclusos y la penalización no se ven afectados). Hay $j$ equipos inconclusos que podemos elegir extender, así que $dp[i][j][k] \mathrel{+}= j \cdot dp[i - 1][j][k]$ .
Usamos a la persona $i$ para “terminar” un equipo inconcluso.
- Esto transiciona al estado $dp[i][j - 1][k + s_i]$ (un equipo inconcluso menos, y sumamos a la penalización como se discutió arriba). Hay de nuevo $j$ equipos inconclusos para elegir, así que $dp[i][j - 1][k + s[i]] \mathrel{+}= j \cdot dp[i - 1][j][k]$ .
Empezamos un nuevo equipo inconcluso con la persona $i$ .
- Esto transiciona al estado $dp[i][j + 1][k - s[i]]$ (un equipo inconcluso más, y restamos de la penalización como se discutió arriba).

Dos cosas más:

$k$ en nuestro arreglo de DP puede ser negativo, así que simplemente sumamos 5000 a cada $k$ ; puede haber a lo sumo $N/2 = 50$ intervalos inconclusos, y cada uno contribuye a lo sumo $-100$ .
$dp[i]$ depende solo de $dp[i - 1]$ , así que podemos eliminar la primera dimensión que guardamos (para ahorrar memoria).

Creo que esto se llama el “truco de abrir y cerrar intervalos” (open and close interval trick). Ver el post de zscoder para más información y problemas.

Implementación

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

C++Python


#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int M = 1e9 + 7;
const int K = 5e3;  // K es un offset para tener en cuenta los negativos
 
int main() {
	int n;
	int x;  // penalización máxima
	cin >> n >> x;
	vector<int> s(n);
	for (int i = 0; i < n; i++) { cin >> s[i]; }
	sort(s.begin(), s.end());
 
	/*
	 * dp[N][N][X] -> dp[i][j][k] = primeras i personas, j grupos inconclusos, k
	 * penalización. por conveniencia, indexamos el arreglo dp desde 1 y el arreglo de personas
	 * desde 0 para que dp[i][j][k] se alinee con s[i] (es decir, habilidad de la persona
	 * i + 1 = s[i]). ¡nótese que solo hay que guardar 2 filas!
	 */
 
	// el subarreglo en el que estamos actualmente
	vector<vector<ll>> dp1(n + 1, vector<ll>(x + K + 1));
	// el siguiente subarreglo (lo llenaremos usando dp1)
	vector<vector<ll>> dp2(n + 1, vector<ll>(x + K + 1));
 
	dp1[0][K] = 1;  // dp[0][0][0] -> 0 personas, 0 grupos inconclusos, 0 penalización
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= (n - i); j++) {  // a lo sumo n - i grupos inconclusos
			for (int k = 0; k <= x + K; k++) {
				if (!dp1[j][k]) { continue; }
				dp2[j][k] += dp1[j][k];  // i tiene su propio grupo
				if (j && k + s[i] <= x + K) {
					dp2[j - 1][k + s[i]] += j * dp1[j][k];  // terminar grupo
				}
				if (j + 1 <= n - (i + 1)) {
					dp2[j + 1][k - s[i]] += dp1[j][k];  // crear nuevo grupo inconcluso
				}
				if (j <= n - (i + 1)) {
					dp2[j][k] += j * dp1[j][k];  // extender grupo inconcluso
				}
			}
		}
		for (int j = 0; j <= (n - (i + 1)); j++) {
			for (int k = 0; k <= x + K; k++) {
				dp1[j][k] = dp2[j][k] % M;  // i + 1 se convierte en el nuevo i
				dp2[j][k] = 0;
			}
		}
	}
 
	int ans = 0;
	for (int i = K; i <= x + K; i++) {
		ans += dp1[0][i];
		ans %= M;
	}
 
	cout << ans << endl;
}


MOD = 10**9 + 7
K = 5000  # K es un offset para tener en cuenta los negativos
 
 
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort()
 
"""
dp[N][N][X] -> dp[i][j][k] = primeras i personas, j grupos inconclusos, k
penalización. por conveniencia, indexamos el arreglo dp desde 1 y el arreglo de personas
desde 0 para que dp[i][j][k] se alinee con s[i] (es decir, habilidad de la persona
i + 1 = s[i]). ¡nótese que solo hay que guardar 2 filas!
"""
 
# el subarreglo en el que estamos actualmente
dp1 = [[0] * (x + K + 1) for _ in range(n + 1)]
 
# el siguiente subarreglo (lo llenaremos usando dp1)
dp2 = [[0] * (x + K + 1) for _ in range(n + 1)]
 
# Caso base: dp[0][0][0] -> 0 personas, 0 grupos inconclusos, 0 penalización
dp1[0][K] = 1
 
for i in range(n):
	for j in range(n - i + 1):  # A lo sumo n - i grupos inconclusos
		for k in range(x + K + 1):
			if dp1[j][k] == 0:
				continue
 
			# i tiene su propio grupo
			dp2[j][k] = (dp2[j][k] + dp1[j][k]) % MOD
 
			# Terminar un grupo inconcluso
			if j > 0 and k + s[i] <= x + K:
				dp2[j - 1][k + s[i]] = (dp2[j - 1][k + s[i]] + j * dp1[j][k]) % MOD
 
			# Crear un nuevo grupo inconcluso
			if j + 1 <= n - (i + 1):
				dp2[j + 1][k - s[i]] = (dp2[j + 1][k - s[i]] + dp1[j][k]) % MOD
 
			# Extender un grupo inconcluso
			if j <= n - (i + 1):
				dp2[j][k] = (dp2[j][k] + j * dp1[j][k]) % MOD
 
	for j in range(n - i):
		for k in range(x + K + 1):
			dp1[j][k] = dp2[j][k] % MOD  # i + 1 se convierte en el nuevo i
			dp2[j][k] = 0
 
ans = 0
for i in range(K, x + K + 1):
	ans = (ans + dp1[0][i]) % MOD
 
print(ans)