Load Balancing

Solución 1: Con Árbol de Segmentos

Explicación

El problema se puede resolver barriendo una línea de abajo hacia arriba. Esta línea divide la granja en dos regiones, norte y sur. Al comienzo, todas las vacas pertenecen a la región norte.

Para cada una de estas líneas, necesitamos una forma eficiente de determinar la partición oeste/este óptima que divide la granja en cuatro pedazos de modo que el número máximo de vacas que aparece en una de las cuatro regiones, $M$ , quede minimizado. Para lograrlo, usamos dos árboles de segmentos como tablas de frecuencias para guardar el número de vacas en una cierta coordenada $x$ que pertenecen a una de las dos regiones, norte y sur, respectivamente.

Luego, hacemos una búsqueda binaria sobre ambos árboles de segmentos para hallar la mejor partición oeste/este que minimiza $M$ . En particular, empezamos desde la raíz de los árboles de segmentos y siempre agregamos o el subárbol izquierdo o el derecho a la región oeste o este, según cuál de estas dos opciones lleve al menor aumento de $M$ .

Al final, actualizamos nuestra mejor solución global y movemos la línea a la siguiente coordenada $y$ de interés. Agregamos todas las vacas con la coordenada $y$ actual a la región sur y las quitamos de la región norte.

Implementación

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

C++Java


#include <bits/stdc++.h>
using namespace std;
 
struct SegmentTree {
	int size;
	vector<int> tree;
	SegmentTree() : size(1 << 20) { tree.assign(size * 2, 0); }
 
	/**
	 * Aumentamos el valor en x en value, es decir a[x] += value
	 */
	void update(int x, int value) {
		x += size;
		tree[x] += value;
		while (x > 0) {
			x /= 2;
			tree[x] = tree[2 * x] + tree[2 * x + 1];
		}
	}
 
	/**
	 * Búsqueda binaria sobre las coordenadas x de modo que el número máximo de vacas M
	 * en las regiones quede minimizado.
	 * @param other La otra región dividida horizontalmente sobre la que se busca
	 * simultáneamente
	 * @return int El número minimizado de vacas según la partición norte/sur
	 * actual
	 */
	int query(SegmentTree &other) {
		// el tamaño de las cuatro regiones
		int west_size, east_size, other_west_size, other_east_size;
		west_size = east_size = other_west_size = other_east_size = 0;
		// empezamos con todo el árbol de segmentos como subárbol de búsqueda
		int mid = 1;
		while (mid < size) {
			int l = mid * 2;
			int r = mid * 2 + 1;
			// agregamos el subárbol que minimiza el conteo máximo global de vacas
			if (max(west_size + tree[l], other_west_size + other.tree[l]) <
			    max(east_size + tree[r], other_east_size + other.tree[r])) {
				mid = r;
				west_size += tree[l];
				other_west_size += other.tree[l];
			} else {
				mid = l;
				east_size += tree[r];
				other_east_size += other.tree[r];
			}
		}
 
		// Agregamos la última coordenada x o al lado oeste o al este
		if (max(west_size + tree[mid], other_west_size + other.tree[mid]) <
		    max(east_size + tree[mid], other_east_size + other.tree[mid])) {
			west_size += tree[mid];
			other_west_size += other.tree[mid];
		} else {
			east_size += tree[mid];
			other_east_size += other.tree[mid];
		}
 
		/*
		 * el valor M correspondiente a la mejor partición oeste/este según
		 * las particiones norte/sur actuales
		 */
		return max(max(west_size, east_size), max(other_west_size, other_east_size));
	}
};
 
int main() {
	freopen("balancing.in", "r", stdin);
	freopen("balancing.out", "w", stdout);
 
	int N;
	cin >> N;
	vector<pair<int, int>> cows(N);
	for (pair<int, int> &c : cows) { cin >> c.first >> c.second; }
 
	// ordenamos por las coordenadas y y dividimos la granja en norte y sur
	sort(cows.begin(), cows.end(),
	     [&](const pair<int, int> &c1, const pair<int, int> &c2) {
		     return make_pair(c1.second, c1.first) < make_pair(c2.second, c2.first);
	     });
 
	// north y south guardan el número de puntos en las coordenadas x
	SegmentTree north;
	SegmentTree south;
 
	/*
	 * empezamos la línea de barrido desde abajo, es decir toda la granja está en la
	 * región norte
	 */
	for (int i = 0; i < N; i++) { north.update(cows[i].first, 1); }
 
	// el número mínimo posible de vacas según el enunciado
	int M = N;
 
	// barrido de abajo hacia arriba
	for (int i = 0; i < N;) {
		// cada vez, movemos los puntos de la línea de norte a sur
		int j = i;
		while (j < N && cows[i].second == cows[j].second) {
			north.update(cows[j].first, -1);
			south.update(cows[j].first, 1);
			j++;
		}
		/*
		 * para la partición actual de norte y sur, determinamos la partición
		 * óptima entre oeste y este haciendo una búsqueda binaria
		 */
		M = min(M, north.query(south));
		// movemos la línea de barrido a la siguiente coordenada y de interés
		i = j;
	}
 
	cout << M << endl;
}


import java.io.*;
import java.util.*;
 
public class Balancing {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("balancing.in"));
 
		int N = Integer.parseInt(br.readLine());
		Pair[] cows = new Pair[N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			cows[i] = new Pair(Integer.parseInt(st.nextToken()),
			                   Integer.parseInt(st.nextToken()));
		}
		br.close();
 
		// ordenamos por las coordenadas y y dividimos la granja en norte y sur
		Arrays.sort(cows, (a, b) -> a.compareBTo(b));
 
		// north y south guardan el número de puntos en las coordenadas x
		SegmentTree north = new SegmentTree();
		SegmentTree south = new SegmentTree();
 
		/*
		 * empezamos la línea de barrido desde abajo, es decir toda la granja está
		 * en la región norte
		 */
		for (int i = 0; i < N; i++) { north.update(cows[i].a, 1); }
 
		// el número mínimo posible de vacas según el
		// enunciado
		int M = N;
 
		// barrido de abajo hacia arriba
		for (int i = 0; i < N;) {
			// cada vez, movemos los puntos de la línea de norte a sur
			int j = i;
			while (j < N && cows[i].b == cows[j].b) {
				north.update(cows[j].a, -1);
				south.update(cows[j].a, 1);
				j++;
			}
			/*
			 * para la partición actual de norte y sur, determinamos la
			 * partición óptima entre oeste y este haciendo una búsqueda
			 * binaria
			 */
			M = Math.min(M, north.query(south));
			// movemos la línea de barrido a la siguiente coordenada y de interés
			i = j;
		}
 
		PrintWriter pw = new PrintWriter(new FileWriter("balancing.out"));
		pw.println(M);
		pw.close();
	}
 
	static class SegmentTree {
		int size;
		int[] tree;
 
		public SegmentTree() {
			size = 1 << 20;
			tree = new int[size * 2];
		}
 
		/**
		 * Aumentamos el valor en x en value, es decir a[x] += value
		 */
		public void update(int x, int value) {
			x += size;
			tree[x] += value;
			while (x > 1) {
				x /= 2;
				tree[x] = tree[x * 2] + tree[x * 2 + 1];
			}
		}
 
		/**
		 * Búsqueda binaria sobre las coordenadas x de modo que el número máximo de vacas M
		 * en las regiones quede minimizado.
		 *
		 * @param other La otra región dividida horizontalmente sobre la que se busca
		 *              simultáneamente
		 * @return int El número minimizado de vacas según la partición norte/sur
		 *         actual
		 */
		public int query(SegmentTree other) {
			// el tamaño de las cuatro regiones
			int westSize, eastSize, otherWestSize, otherEastSize;
			westSize = eastSize = otherWestSize = otherEastSize = 0;
			// empezamos con todo el árbol de segmentos como subárbol de búsqueda
			int mid = 1;
			while (mid < size) {
				int l = mid * 2;
				int r = mid * 2 + 1;
				// agregamos el subárbol que minimiza el conteo máximo global de
				// vacas
				if (Math.max(westSize + tree[l], otherWestSize + other.tree[l]) <
				    Math.max(eastSize + tree[r], otherEastSize + other.tree[r])) {
					mid = r;
					westSize += tree[l];
					otherWestSize += other.tree[l];
				} else {
					mid = l;
					eastSize += tree[r];
					otherEastSize += other.tree[r];
				}
			}
 
			// Agregamos la última coordenada x o al lado oeste o al este
			if (Math.max(westSize + tree[mid], otherWestSize + other.tree[mid]) <
			    Math.max(eastSize + tree[mid], otherEastSize + other.tree[mid])) {
				westSize += tree[mid];
				otherWestSize += other.tree[mid];
			} else {
				eastSize += tree[mid];
				otherEastSize += other.tree[mid];
			}
 
			/*
			 * el valor M correspondiente a la mejor partición oeste/este según
			 * las particiones norte/sur actuales
			 */
			return Math.max(Math.max(westSize, eastSize),
			                Math.max(otherWestSize, otherEastSize));
		}
	}
 
	// BeginCodeSnip{class Pair}
	static class Pair implements Comparable<Pair> {
		public int a;
		public int b;
 
		public Pair(int a, int b) {
			this.a = a;
			this.b = b;
		}
 
		/**
		 * Ordena el objeto por orden lexicográfico.
		 */
		@Override
		public int compareTo(Pair other) {
			if (a == other.a) { return b - other.b; }
			return a - other.a;
		}
 
		/**
		 * Ordena el objeto por orden lexicográfico invertido.
		 */
		public int compareBTo(Pair other) {
			if (b == other.b) { return a - other.a; }
			return b - other.b;
		}
	}
	// EndCodeSnip
}

Alternativa usando un BIT

También hay una solución alternativa usando un Árbol de Fenwick (BIT).

C++Java


#include <algorithm>
#include <array>
#include <fstream>
#include <iostream>
#include <vector>
 
using std::array;
using std::vector;
 
const int MAX_Y = 1000000;
 
// BeginCodeSnip{BIT (from the PURS module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;
 
  public:
	BIT(int size) : size(size), bit(size + 1, 0), arr(size) {}
 
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}
 
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip
 
int main() {
	std::ifstream cin("balancing.in");
	int n;
	cin >> n;
 
	vector<array<int, 2>> coords(n);
	for (int i = 0; i < n; i++) { cin >> coords[i][0] >> coords[i][1]; }
 
	BIT<int> left(MAX_Y + 1);
	BIT<int> right(MAX_Y + 1);
 
	for (array<int, 2> i : coords) { right.add(i[1], 1); }
 
	int res = n;
	std::sort(begin(coords), end(coords));
	for (int i = 0; i < n;) {
		int j = i;
		while (j < n && coords[j][0] == coords[i][0]) {
			left.add(coords[j][1], 1);
			right.add(coords[j][1], -1);
			j++;
		}
		i = j;
 
		int l = 0;
		int r = MAX_Y / 2;
		while (l <= r) {
			int mid = (l + r) / 2;
			int up =
			    std::max(i - left.pref_sum(2 * mid), n - i - right.pref_sum(2 * mid));
			int down = std::max(left.pref_sum(2 * mid), right.pref_sum(2 * mid));
 
			if (up > down) {
				l = mid + 1;
			} else if (up < down) {
				r = mid - 1;
			} else {
				res = std::min(res, down);
				break;
			}
		}
	}
 
	std::ofstream("balancing.out") << res << endl;
}


public class Balancing {
	static final int MAX_Y = 1_000_000;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("balancing.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("balancing.out"));
 
		int N = Integer.parseInt(br.readLine());
		int[][] coords = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			coords[i] = new int[2];
			coords[i][0] = Integer.parseInt(st.nextToken());
			coords[i][1] = Integer.parseInt(st.nextToken());
		}
 
		BIT left = new BIT(MAX_Y + 1);
		BIT right = new BIT(MAX_Y + 1);
		for (int[] i : coords) { right.update(i[1], 1); }
		int ret = N;
		Arrays.sort(coords, (int[] a, int[] b) -> a[0] - b[0]);
 
		for (int i = 0; i < N;) {
			int j = i;
			while (j < N && coords[j][0] == coords[i][0]) {
				left.update(coords[j][1], 1);
				right.update(coords[j][1], -1);
				j++;
			}
			i = j;
 
			int l = 0;
			int r = MAX_Y / 2;
			while (l <= r) {
				int mid = (l + r) / 2;
				int up = Math.max(i - left.sum(2 * mid), N - i - right.sum(2 * mid));
				int down = Math.max(left.sum(2 * mid), right.sum(2 * mid));
				if (up > down) {
					l = mid + 1;
				} else if (up < down) {
					r = mid - 1;
				} else {
					ret = Math.min(ret, down);
					break;
				}
			}
		}
		pw.println(ret);
		pw.close();
		br.close();
	}
 
	static class BIT {
		public int[] bit;
		public BIT(int N) { bit = new int[N + 1]; }
 
		public int sum(int r) {
			r++;
			int ret = 0;
			while (r > 0) {
				ret += bit[r];
				r -= r & -r;
			}
			return ret;
		}
 
		public void update(int idx, int v) {
			idx++;
			while (idx < bit.length) {
				bit[idx] += v;
				idx += idx & -idx;
			}
		}
	}
}

Solución 2: Con búsqueda binaria

Explicación

Como alternativa, también podemos hacer búsqueda binaria sobre la respuesta sin usar una estructura de datos PURQ. Para comprobar si un número máximo elegido de vacas en cualquiera de las cuatro regiones, de ahora en más $M^*$ , es factible, calculamos la altura máxima de las cuatro regiones para cada partición $x$ posible con a lo sumo $M^*$ vacas en la región. Luego recorremos cada coordenada $x$ y comprobamos si la suma de las alturas de las regiones sur y norte es mayor que la altura de la granja. Como hay dos regiones en el norte y dos en el sur, siempre tomamos el mínimo entre noroeste/noreste y suroeste/sureste. Si hay una partición $x$ que hace que la suma sea mayor que la altura de la granja, entonces hay una solución con la partición $x$ e $y$ actuales.

Hacemos una compresión de coordenadas sobre las coordenadas $x$ e $y$ para simplificar la implementación.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
/**
 * Calcula la altura máxima de la región inferior izquierda para cada partición
 * posible según la coordenada x que tiene a lo sumo max_cows vacas
 * en la región.
 * @return bound[i] es la altura máxima posible para la región 0..i,
 * 0..bound[i], en la que el número de vacas es menor o igual que max_cows
 */
vector<int> calc_max_height(int max_cows, const vector<pair<int, int>> &cows) {
	// número total de vacas en la región actual
	int sum = 0;
	// número de vacas según las coordenadas y
	vector<int> count(cows.size());
	// la altura máxima actual de la región
	int y_bound = cows.size() - 1;
	// las alturas máximas de la región según la partición x
	vector<int> bound(cows.size());
	for (int x = 0, i = 0; x < cows.size(); x++) {
		while (i < cows.size() && cows[i].first == x) {
			int y = cows[i].second;
			count[y]++;
			// actualizamos la suma de vacas en la región activa
			if (y <= y_bound) { sum++; }
			i++;
		}
		/*
		 * si se supera el número máximo permitido de vacas en la región,
		 * disminuimos la altura de la región
		 */
		while (sum > max_cows) {
			sum -= count[y_bound];
			y_bound--;
		}
		bound[x] = y_bound;
	}
	return bound;
}
 
int main() {
	freopen("balancing.in", "r", stdin);
	freopen("balancing.out", "w", stdout);
 
	int N;
	cin >> N;
	vector<pair<int, int>> cows(N);
	for (pair<int, int> &c : cows) { cin >> c.first >> c.second; }
 
	// BeginCodeSnip{Coordinate Compression}
	//  comprimimos coordenadas x
	sort(cows.begin(), cows.end());
	int new_x = 0;
	int actual_x = cows[0].first;
	for (int i = 0; i < N; i++) {
		if (cows[i].first != actual_x) {
			new_x++;
			actual_x = cows[i].first;
		}
		cows[i].first = new_x;
	}
 
	// comprimimos coordenadas y
	sort(cows.begin(), cows.end(),
	     [&](const pair<int, int> &c1, const pair<int, int> &c2) {
		     return make_pair(c1.second, c1.first) < make_pair(c2.second, c2.first);
	     });
	int new_y = 0;
	int actual_y = cows[0].second;
	for (int i = 0; i < N; i++) {
		if (cows[i].second != actual_y) {
			new_y++;
			actual_y = cows[i].second;
		}
		cows[i].second = new_y;
	}
	// EndCodeSnip
 
	sort(cows.begin(), cows.end());
	int l = 1, h = N + 1;
	// búsqueda binaria sobre el máximo de M
	while (l < h) {
		int mid = (h + l) / 2;
		bool possible = false;
 
		vector<int> west_south_height = calc_max_height(mid, cows);
 
		for (pair<int, int> &t : cows) { t.second = N - 1 - t.second; }
		vector<int> west_north_height = calc_max_height(mid, cows);
 
		reverse(cows.begin(), cows.end());
		for (pair<int, int> &t : cows) {
			t.first = N - 1 - t.first;
			t.second = N - 1 - t.second;
		}
		vector<int> east_south_height = calc_max_height(mid, cows);
 
		for (pair<int, int> &t : cows) { t.second = N - 1 - t.second; }
		vector<int> east_north_height = calc_max_height(mid, cows);
 
		// para cada partición x posible
		for (int x = 0; x < N - 1; x++) {
			/*
			 * si la suma de las alturas de las regiones sur y norte es
			 * mayor que la altura de la granja, entonces hay una solución
			 * con el máximo M actual, es decir mid
			 */
			if (min(west_south_height[x], east_south_height[N - 2 - x]) + 1 +
			        min(west_north_height[x], east_north_height[N - 2 - x]) + 1 >=
			    N) {
				possible = true;
				break;
			}
		}
 
		if (possible) {
			h = mid;
		} else {
			l = mid + 1;
		}
	}
 
	cout << l << endl;
}