Skip to Content
CTRL K

Social Distancing I

Análisis oficial (C++) 

Explicación

El caso de ejemplo se puede resolver colocando dos vacas en los dos huecos más grandes. ej. 10001001000010 -> 10[1]010010[1]0010.

Sin embargo, esta estrategia no es óptima para casos como 1000001. Podemos usar análisis por casos para considerar cada caso por separado.

Todos los casos son:

  1. 100010001 - Colocar dos vacas en los dos huecos más grandes.
  2. 10000001 - Encajar dos vacas en las marcas de 1/31/3 y 2/32/3 del hueco más grande.
  3. 00001000 - Colocar en los dos extremos lejanos.
  4. 10000000/00000001 - Colocar una vaca en uno de los extremos lejanos, y otra en el hueco más grande.

Ahora podemos probar todos estos casos y maximizar DD.

Implementación

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

#include <bits/stdc++.h>
 
using namespace std;
 
int compute_D(string stalls) {
	int d = INT32_MAX;
	int last1 = -1;
 
	for (int i = 0; i < stalls.length(); i++) {
		if (stalls[i] == '1') {
			if (last1 != -1) d = min(d, i - last1);
			last1 = i;
		}
	}
 
	return d;
}
pair<int, int> get_largest_zeros(string stalls) {
	// luego podemos obtener los dos con máximo (end-start)
	pair<int, int> largestZero = {-1, -1};
 
	// obtenemos los tamaños
	int zeros_start = -1;
	for (int i = 0; i < stalls.size(); i++) {
		// si entramos a un '0' y aún no estamos contando, empezamos a contar
		if (stalls[i] == '0' && zeros_start == -1) { zeros_start = i; }
 
		// chocamos con un '1' y hemos contado algunos ceros, o hemos llegado al final
		if ((stalls[i] == '1' && zeros_start != -1) || i == stalls.size() - 1) {
			// insertamos la secuencia de ceros
			pair<int, int> zero = {zeros_start, i};
			if ((zero.second - zero.first) > (largestZero.second - largestZero.first)) {
				largestZero = zero;
			}
			zeros_start = -1;
		}
	}
 
	return largestZero;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	freopen("socdist1.in", "r", stdin);
	freopen("socdist1.out", "w", stdout);
 
	int n;
	cin >> n;
	string stalls;
	cin >> stalls;
 
	auto largest = get_largest_zeros(stalls);
 
	int d = 0;
	if (largest.first != -1) {
		// 100010001
		// colocamos en las ubicaciones más espaciadas
		string c = stalls;
 
		c[(largest.first + largest.second) / 2] = '1';
 
		auto nextLargest = get_largest_zeros(c);
		c[(nextLargest.first + nextLargest.second) / 2] = '1';
 
		d = max(d, compute_D(c));
	}
	if (largest.first != -1) {
		// 100000001
		// colocamos una en 1/3 y otra en 2/3
		int gap = largest.second - largest.first;
 
		string c = stalls;
		c[largest.first + gap / 3] = '1';
		c[largest.first + (gap * 2) / 3] = '1';
 
		d = max(d, compute_D(c));
	}
	if (stalls[0] == '0' && stalls[stalls.size() - 1] == '0') {
		// 000010000
		// colocamos en los dos extremos
		string c = stalls;
		c[0] = '1';
		c[stalls.size() - 1] = '1';
 
		d = max(d, compute_D(c));
	}
	if (stalls[0] == '0') {
		// 00010001
		// colocamos en el punto más lejano y dentro del mayor cero
		string c = stalls;
		c[0] = '1';
 
		auto nextLargest = get_largest_zeros(c);
		c[(nextLargest.first + nextLargest.second) / 2] = '1';
 
		d = max(d, compute_D(c));
	}
	if (stalls[stalls.size() - 1] == '0') {
		// 10010000
		// colocamos en el punto más lejano y dentro del mayor cero
		string c = stalls;
		c[stalls.size() - 1] = '1';
 
		auto nextLargest = get_largest_zeros(c);
		c[(nextLargest.first + nextLargest.second) / 2] = '1';
 
		d = max(d, compute_D(c));
	}
 
	cout << d << "\n";
}
Fundamentos