Skip to Content
CTRL K

Social Distancing

Análisis oficial (C++) 

Solución en video 1

Por Kyle Xu

Nota: la solución en video puede no ser la misma que las demás soluciones. Código en C++, Python y Java.

Video de YouTube (LI5xk95Cauc)

Solución en video 2

Nota: la solución en video puede no ser la misma que las demás soluciones. Código en C++.

Video de YouTube (mt8QhnFOkr0)

Solución

Explicación

Observemos que, para cualquier distancia, si no es posible que todas las vacas se paren sobre pasto con la distancia especificada, entonces tampoco es posible para ninguna distancia mayor que esa. Además, aunque puede ser difícil calcular DD de forma directa (ni siquiera se sabe cómo encarar tal problema), no es tan difícil comprobar si una cierta distancia propuesta es válida. Esto lo convierte en un problema perfecto de búsqueda binaria.

Hay que comprobar, para una distancia mínima especificada dd entre vacas, si todas las vacas se pueden colocar sobre pasto. Esto se puede hacer recorriendo los intervalos ordenados (disjuntos entre sí) y colocando las vacas de forma óptima.

Consideremos el primer intervalo. Es más eficiente colocar la vaca en el extremo izquierdo del intervalo para dejar el mayor espacio posible para las demás. Luego, si hay espacio en el mismo intervalo a distancia dd, colocamos la siguiente vaca. Repetimos hasta que no quede más lugar en el intervalo actual, y entonces pasamos al siguiente. De nuevo colocamos la vaca lo más a la izquierda posible, manteniendo al menos distancia dd respecto de la vaca anterior (si no podemos colocar una vaca en este intervalo, lo saltamos). Repetimos este proceso hasta que se hayan colocado todas las vacas o no queden más intervalos. Si no quedan intervalos y todavía hay vacas sin colocar, entonces la distancia propuesta no es válida.

Implementación

Complejidad temporal: O((N+M)log⁡(maxDist))\mathcal{O}((N+M)\log (\texttt{maxDist}))

#include <bits/stdc++.h>
 
using namespace std;
 
void setIO(string prob = "") {
	if (!prob.empty()) {
		freopen((prob + ".in").c_str(), "r", stdin);
		freopen((prob + ".out").c_str(), "w", stdout);
	}
}
 
const int MAX_N = 1e5;
 
pair<long long, long long> intervals[MAX_N];
 
int main() {
	setIO("socdist");
 
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) { cin >> intervals[i].first >> intervals[i].second; }
	sort(intervals, intervals + m);
 
	long long lo = 0;
	long long hi = intervals[m - 1].second - intervals[0].first + 1;
	while (lo < hi) {
		long long mid = lo + (hi - lo + 1) / 2;
		int count = 1;
		int intervalCount = 0;
		long long current = intervals[0].first;
 
		// intentar colocar la siguiente vaca en el primer parche de pasto
		// disponible
		while (current + mid <= intervals[m - 1].second) {
			while (current + mid > intervals[intervalCount].second) { intervalCount++; }
			current = max(intervals[intervalCount].first, current + mid);
			count++;
			if (count == n) break;
		}
 
		if (count >= n) lo = mid;
		else hi = mid - 1;
	}
	cout << lo << '\n';
}
with open("socdist.in", "r") as r:
	n, m = map(int, r.readline().split())
	intervals = [tuple(map(int, r.readline().split())) for _ in range(m)]
	intervals.sort()
 
 
def possible_placement(d: int) -> bool:
	cows = n
	prev_cow_location = intervals[0][0] - d
 
	for begin, end in intervals:
		if prev_cow_location + d < begin:
			prev_cow_location = begin - d
 
		while begin <= prev_cow_location + d <= end:
			prev_cow_location += d
			cows -= 1
 
	return cows <= 0
 
 
left, right = 0, intervals[-1][1] - intervals[0][0]
 
while left < right:
	mid = (left + right + 1) // 2
	if possible_placement(mid):
		left = mid
	else:
		right = mid - 1
 
print(left, file=open("socdist.out", "w"))
import java.io.*;
import java.util.*;
 
public class SocDist {
	static class Pair implements Comparable<Pair> {
		long first, second;
 
		public Pair(long x, long y) {
			first = x;
			second = y;
		}
 
		public int compareTo(Pair x) {
			if (this.first == x.first) return (int)(this.second - x.second);
			return (int)(this.first - x.first);
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader("socdist.in"));
		PrintWriter pw = new PrintWriter("socdist.out");
		StringTokenizer st = new StringTokenizer(in.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		Pair intervals[] = new Pair[m];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine());
			intervals[i] = new Pair(Long.parseLong(st.nextToken()),
			                        Long.parseLong(st.nextToken()));
		}
 
		Arrays.sort(intervals);
		long lo = 0;
		long hi = intervals[m - 1].second - intervals[0].first + 1;
		while (lo < hi) {
			long mid = lo + (hi - lo + 1) / 2;
			int count = 1;
			int intervalCount = 0;
			long current = intervals[0].first;
			// intentar colocar la siguiente vaca en el primer parche de pasto
			// disponible
			while (current + mid <= intervals[m - 1].second) {
				while (current + mid > intervals[intervalCount].second) {
					intervalCount++;
				}
				current = Math.max(intervals[intervalCount].first, current + mid);
				count++;
				if (count == n) break;
			}
			if (count >= n) lo = mid;
			else hi = mid - 1;
		}
		pw.println(lo);
		pw.close();
	}
}
Fundamentos