Análisis por casos

Un problema de análisis por casos (casework) es uno que se puede partir en casos distintos, cada uno resoluble por separado.

Suelen exigir dibujar muchos casos y hacer observaciones sobre cada uno.

Podemos buscar similitudes entre casos distintos para resolver varios de ellos con el mismo método.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Bronze	Sleepy Cow Herding	Normal		Solución

Solución - Sleepy Cow Herding

Solución

Resolvemos de forma independiente el mínimo y el máximo de movimientos. Llamamos “elementos” a las posiciones de las vacas, y decimos que dos elementos son adyacentes si no hay ningún elemento entre ellos.

Mínimo

Hay 3 casos para la cantidad mínima de movimientos:

Los 3 elementos ya son consecutivos.
Hay dos elementos adyacentes con exactamente una posición vacía entre ellos.
Cualquier otro caso que no cumpla los dos anteriores.

En el primer caso, la respuesta es $0$ porque los elementos ya son consecutivos.

En el segundo caso, la respuesta es $1$ porque el único movimiento necesario es el que inserta el elemento aislado en el hueco entre los otros dos.

El tercer caso da $2$ porque, en cualquier otro caso de prueba, la solución óptima es llevar el elemento mínimo a $\text{max}-2$ o el máximo a $\text{min}+2$ , y entonces nos reducimos al segundo caso.

Máximo

El máximo siempre es finito porque cada operación disminuye de forma estricta la distancia entre los extremos (llamémosla el “span”) en al menos uno. La mejor estrategia para maximizar la cantidad de movimientos es colocar cada elemento lo más cerca posible de un extremo (sin que siga siendo un extremo). Después de un movimiento, el span será igual a la mayor distancia entre dos elementos adyacentes, y cada movimiento siguiente disminuirá el span en uno hasta que llegue a dos. Por lo tanto, el máximo es la mayor distancia entre dos elementos adyacentes menos 1.

Implementación

Complejidad temporal: $\mathcal{O}(1)$

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	freopen("herding.in", "r", stdin);
	freopen("herding.out", "w", stdout);
 
	vector<int> a(3);
	for (int &b : a) { cin >> b; }
	sort(a.begin(), a.end());
 
	/*
	 * La cantidad mínima de movimientos solo puede ser 0, 1 o 2.
	 * 0 si ya son consecutivos,
	 * 1 si hay una diferencia de 2 entre algún par de números,
	 * y 2 en todos los demás casos.
	 */
	if (a[0] == a[2] - 2) {
		cout << 0 << endl;
	} else if ((a[1] == a[2] - 2) || (a[0] == a[1] - 2)) {
		cout << 1 << endl;
	} else {
		cout << 2 << endl;
	}
 
	// el máximo es la mayor diferencia entre un extremo y el del medio, menos uno.
	cout << max(a[2] - a[1], a[1] - a[0]) - 1;
}


import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("herding.in"));
		PrintWriter pw = new PrintWriter(new File("herding.out"));
		int[] cows = new int[3];
		cows[0] = sc.nextInt();
		cows[1] = sc.nextInt();
		cows[2] = sc.nextInt();
		Arrays.sort(cows);
 
		/*
		 * La cantidad mínima de movimientos solo puede ser 0, 1 o 2.
		 * 0 si ya son consecutivos,
		 * 1 si hay una diferencia de 2 entre algún par de números,
		 * y 2 en todos los demás casos.
		 */
		if (cows[2] == cows[0] + 2) {
			pw.println(0);
		} else if (cows[1] == cows[0] + 2 || cows[2] == cows[1] + 2) {
			pw.println(1);
		} else {
			pw.println(2);
		}
 
		// el máximo es la mayor diferencia entre un extremo y el del medio, menos uno.
		pw.println(Math.max(cows[1] - cows[0], cows[2] - cows[1]) - 1);
		pw.close();
	}
}


with open("herding.in", "r") as file_in:
	a, b, c = map(int, file_in.readline().split())
 
"""
La cantidad mínima de movimientos solo puede ser 0, 1 o 2.
0 si ya son consecutivos,
1 si hay una diferencia de 2 entre algún par de números,
y 2 en todos los demás casos.
"""
if c == a + 2:
	minimum = 0
elif b == a + 2 or c == b + 2:
	minimum = 1
else:
	minimum = 2
 
# el máximo es la mayor diferencia entre un extremo y el del medio, menos uno.
maximum = max(b - a, c - b) - 1
 
print(f"{minimum}\n{maximum}", file=open("herding.out", "w"))

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Three Logos	Fácil	Casework	Solución
Bronze	Fence Painting	Normal	Casework	Solución
Bronze	Social Distancing I	Normal	Casework	Solución
Bronze	Hoof Paper Scissors Minus One	Normal	Casework	Solución
Bronze	Leaders	Difícil	Casework	Solución