Minimizing Haybales

Explicación

Hay un montón de formas de resolver esto, pero como probablemente llegaste desde el módulo de descomposición por raíz cuadrada, veamos solo esa. El editorial oficial también tiene algunas soluciones alternativas interesantes.

Subtarea

Intentemos primero resolver la subtarea y plantear una solución $\mathcal{O}(N^2)$ .

Intentemos construir el ordenamiento mínimo posible para cada prefijo del arreglo. Podemos hacerlo con una estrategia similar al ordenamiento por inserción.

Podemos insertar un elemento en el prefijo intercambiándolo hacia la izquierda hasta que llegue a la posición $i$ donde $|a[i] - a[i - 1]| > k$ porque es imposible seguir intercambiándolo. Sin embargo, si $a[i] > a[i + 1]$ , es más óptimo intercambiarlo de vuelta hacia la derecha hasta que llegue a un punto donde $a[i] < a[i + 1]$ .

Solución completa

Podemos acelerar esto con descomposición por raíz cuadrada. Partimos el arreglo en bloques de tamaño $\sqrt{n}$ .

Sabemos que un elemento $a[i]$ puede atravesar por completo un bloque si $a[i] + k \ge \texttt{MAX}$ y $a[i] - k \le \texttt{MIN}$ , donde $\texttt{MAX}$ y $\texttt{MIN}$ son el máximo y el mínimo del bloque respectivamente. Podemos hallar el bloque más a la derecha que el elemento $a[i]$ no puede atravesar, lo cual toma a lo sumo O( $\sqrt{n}$ ) ya que comprobamos cada bloque.

Podemos insertar este elemento en el bloque de raíz cuadrada en su posición correcta intercambiándolo hacia la izquierda dentro del bloque hasta que llegue a un lugar donde ya no se pueda intercambiar más hacia abajo. Esto también toma $\mathcal{O}(\sqrt{N})$ de tiempo por el tamaño del bloque.

Ahora necesitamos intercambiarlo de vuelta hacia la derecha hasta que llegue a un punto que haga el arreglo lexicográficamente mínimo. Podemos hacerlo hallando el primer bloque a su derecha que tenga su $\texttt{MAX} > a[i]$ comprobando cada bloque de nuevo en $\mathcal{O}(\sqrt{N})$ .

Notemos que hay un caso borde aquí donde $a[i]$ nunca se puede intercambiar hacia la izquierda más allá de otro elemento mayor que él por la restricción de $k$ , aunque el elemento $\texttt{MAX}$ sea mayor que $a[i]$ . En este caso, podemos empujar $a[i]$ al siguiente bloque y luego aplicar la estrategia de comprobar cuándo $\texttt{MAX} > a[i]$ . Podemos comprobarlo viendo que, después de insertar $a[i]$ en el bloque e intercambiar hacia la izquierda y hacia la derecha de forma apropiada como se describió arriba, $a[i]$ llega al final del bloque.

Ahora surge el problema de que, cuando agregamos suficientes elementos, el tamaño de un bloque podría ser potencialmente mayor que $\sqrt{n}$ . Para lidiar con esto, podemos partir el bloque en dos bloques más pequeños (cada uno de la mitad del tamaño del bloque original) e insertarlos en la lista de bloques. Insertar en un vector en C++ o ArrayList en Java depende del tamaño del arreglo, que en nuestro caso toma $\mathcal{O}(\sqrt{N})$ . Podemos demostrar que la cantidad de bloques está acotada por $2\sqrt{n}$ .

Procesar cada elemento del arreglo tomó $\mathcal{O}(\sqrt{N})$ de tiempo, así que la complejidad temporal total es $\mathcal{O}(N\sqrt{N})$ .

Implementación

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

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int n, k;
 
struct Block {
	int hi = -INT32_MAX;
	int lo = INT32_MAX;
	vector<int> vals;
 
	Block(vector<int> a) {
		for (int i : a) {
			vals.push_back(i);
			hi = max(hi, i);
			lo = min(lo, i);
		}
	}
 
	/** Adds element x to the block */
	void add(int x) {
		lo = min(lo, x);
		hi = max(hi, x);
		vals.push_back(x);
		int i = vals.size() - 1;
		while (i > 0 && abs(vals[i] - vals[i - 1]) <= k) {
			swap(vals[i], vals[i - 1]);
			i--;
		}
		while (i < vals.size() - 1 && vals[i] > vals[i + 1]) {
			swap(vals[i], vals[i + 1]);
			i++;
		}
	}
 
	/**
	 * @return whether the most optimal position for x is
	 * at the end, if it is starts from the end.
	 */
	bool reaches_end(int x) {
		vals.push_back(x);
		int i = vals.size() - 1;
		while (i > 0 && abs(vals[i] - vals[i - 1]) <= k) {
			swap(vals[i], vals[i - 1]);
			i--;
		}
		while (i < vals.size() - 1 && vals[i] > vals[i + 1]) {
			swap(vals[i], vals[i + 1]);
			i++;
		}
		bool ans = vals.back() == x;
		vals.erase(begin(vals) + i);
		return ans;
	}
};
 
int main() {
	cin >> n >> k;
	int len = (int)floor(sqrt(n));
	vector<Block> sqrt{Block()};
 
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		int j = sqrt.size() - 1;
 
		/*
		 * Finds the earliest block we can insert element x
		 * by swapping to the left
		 */
		while (j > 0 && (x + k >= sqrt[j].hi && x - k <= sqrt[j].lo)) { j--; }
 
		/*
		 * Handle edge case if x doesn't cross an element greater than it in
		 * block j while swapping left. Swaps element x to the right to the
		 * lexographically optimal position.
		 */
		if (j < sqrt.size() - 1 && sqrt[j].reaches_end(x)) {
			j++;
			while (j < sqrt.size() - 1 && x >= sqrt[j].hi) { j++; }
		}
		sqrt[j].add(x);
 
		// If block is too large split into two smalller blocks of equal size
		if (sqrt[j].vals.size() > len) {
			int half = (sqrt[j].vals.size()) / 2;
			vector<int> left, right;
			for (int k = 0; k < half; k++) { left.push_back(sqrt[j].vals[k]); }
			for (int k = half; k < sqrt[j].vals.size(); k++) {
				right.push_back(sqrt[j].vals[k]);
			}
			sqrt.insert(begin(sqrt) + j, Block(left));
			sqrt[j + 1] = Block(right);
		}
	}
 
	for (Block block : sqrt) {
		for (int num : block.vals) { cout << num << endl; }
	}
}


import java.io.*;
import java.util.*;
 
public class MinimizingHaybales {
	// sqrt(1e5) is roughly 300
	static final int BLOCK_SIZE = 300;
	static int k;
 
	public static class Block {
		public int hi, lo;
		List<Integer> vals;
 
		public Block() {
			vals = new ArrayList<>();
			hi = Integer.MIN_VALUE;
			lo = Integer.MAX_VALUE;
		}
 
		public Block(List<Integer> a) {
			vals = new ArrayList<>();
			hi = Integer.MIN_VALUE;
			lo = Integer.MAX_VALUE;
			for (int i : a) {
				vals.add(i);
				hi = Math.max(hi, i);
				lo = Math.min(lo, i);
			}
		}
 
		/**
		 * @param test If test is true, it checks the return condition without
		 *     actually adding x, otherwise it actually adds x in the correct
		 *     position
		 * @return whether the most optimal position for x is at the end, if it
		 *     is starts from the end.
		 */
		public boolean add(int x, boolean test) {
			if (!test) {
				lo = Math.min(lo, x);
				hi = Math.max(hi, x);
			}
			vals.add(x);
			int i = vals.size() - 1;
 
			while (i > 0 && Math.abs(vals.get(i) - vals.get(i - 1)) <= k) {
				int temp = vals.get(i);
				vals.set(i, vals.get(i - 1));
				vals.set(i - 1, temp);
				i--;
			}
			while (i < vals.size() - 1 && vals.get(i) > vals.get(i + 1)) {
				int temp = vals.get(i);
				vals.set(i, vals.get(i + 1));
				vals.set(i + 1, temp);
				i++;
			}
 
			boolean ans = vals.get(vals.size() - 1) == x;
			if (test) { vals.remove(i); }
			return ans;
		}
	}
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		ArrayList<Block> sqrt = new ArrayList<>();
 
		sqrt.add(new Block());
		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());
 
			/*
			 * Finds the earliest block we can insert element x by swapping to
			 * the left.
			 */
			int j = sqrt.size() - 1;
			while (j > 0 && (x + k >= sqrt.get(j).hi && x - k <= sqrt.get(j).lo)) {
				j--;
			}
 
			/*
			 * Handle edge case if x doesn't cross an element greater than it in
			 * block j while swapping left. Swaps element x to the right to the
			 * lexographically optimal position.
			 */
			if (j < sqrt.size() - 1 && sqrt.get(j).add(x, true)) {
				j++;
				while (j < sqrt.size() - 1 && x >= sqrt.get(j).hi) { j++; }
			}
			sqrt.get(j).add(x, false);
 
			// Split the block if it's too large
			if (sqrt.get(j).vals.size() > BLOCK_SIZE) {
				int half = (sqrt.get(j).vals.size()) / 2;
				ArrayList<Integer> left = new ArrayList<>();
				ArrayList<Integer> right = new ArrayList<>();
				for (int k = 0; k < half; k++) { left.add(sqrt.get(j).vals.get(k)); }
				for (int k = half; k < sqrt.get(j).vals.size(); k++) {
					right.add(sqrt.get(j).vals.get(k));
				}
				sqrt.add(j, new Block(left));
				sqrt.set(j + 1, new Block(right));
			}
		}
 
		for (Block block : sqrt) {
			for (int num : block.vals) { System.out.println(num); }
		}
	}
}