A Huge Tower

Solución en video

Por Abhiraj Mallangi

Nota: la solución en video puede no coincidir con las demás. Código en C++ y Java.

Solución

Explicación

Primero, definamos algunas variables. Sean $a_1, a_2, ..., a_n$ los tamaños de los bloques, ordenados de menor a mayor. Sea $b_i$ la cantidad de índices $j$ tales que $j < i$ y $a_i \leq a_j + d$ . Sea $\texttt{ans}_i$ la respuesta si la torre consistiera solo de los bloques $a_1, a_2, ..., a_i$ . Por supuesto, esto significa que $\texttt{ans}_n$ será la respuesta final.

Para cualquier torre formada por los primeros $i - 1$ bloques, siempre habrá $b_i + 1$ formas de insertar el bloque de tamaño $a_i$ en la torre. Para entender por qué, consideremos dónde se puede insertar el bloque de tamaño $a_i$ . El bloque de tamaño $a_i$ siempre se puede insertar en la base de la torre, porque no hay ningún bloque más grande que $a_i$ en la torre. El bloque de tamaño $a_i$ se puede insertar encima de algún bloque $x$ de tamaño $a_x$ si y solo si $a_i \leq a_x + d$ .

Así, vemos que $\texttt{ans}_i = \texttt{ans}_{i-1} \cdot (b_i + 1)$ , porque hay $b_i + 1$ formas válidas de insertar el bloque $a_i$ en cualquiera de las $ans_{i-1}$ torres válidas.

Implementación

Esta solución usa 2 punteros en lugar de crear los arreglos $ans[]$ y $b[]$ .

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

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
const int MOD = 1e9 + 9;
 
int main() {
	int n, d;
	std::cin >> n >> d;
	std::vector<int> blocks(n);
	for (int i = 0; i < n; i++) { std::cin >> blocks[i]; }
 
	sort(blocks.begin(), blocks.end());  // ordenamos los bloques
 
	int right = 0;
	int res = 1;
	for (int left = 0; left < n; left++) {
		while (right < n - 1 && blocks[right + 1] - blocks[left] <= d) { right++; }
		// torre más grande que podemos construir cuando el bloque blocks[left] es la base
		int dist = right - left + 1;
		res = (res * 1LL * dist) % MOD;
	}
 
	std::cout << res << '\n';
}


import java.io.*;
import java.util.*;
 
public class tower {
	static final int MOD = 1000000009;
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int d = io.nextInt();
 
		int[] blocks = new int[n];
		for (int i = 0; i < n; i++) { blocks[i] = io.nextInt(); }
 
		Arrays.sort(blocks);  // ordenamos los bloques
		int right = 0;
		long res = 1;
		for (int left = 0; left < n; left++) {
			while (right < n - 1 && blocks[right + 1] - blocks[left] <= d) { right++; }
			// torre más grande que podemos construir cuando el bloque blocks[left] es la base
			int dist = right - left + 1;
			res = (res * dist) % MOD;
		}
 
		io.println(res);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


MOD = 10**9 + 9
 
n, d = map(int, input().split())
blocks = list(map(int, input().split()))
 
blocks.sort()  # ordenamos los bloques
 
right = 0
res = 1
for left in range(n):
	while right < n - 1 and blocks[right + 1] - blocks[left] <= d:
		right += 1
 
	# torre más grande que podemos construir cuando el bloque blocks[left] es la base
	dist = right - left + 1
	res = (res * dist) % MOD
 
print(res)