The Great Revegetation

Pista

¿Qué nos obliga a cambiar a un tipo de pasto distinto?

Solución 1

Explicación

Recorremos todos los pastos, asignándole a cada uno el color más bajo que no entre en conflicto con ninguno de los requisitos.

Implementación

En la implementación de abajo, se asegura que los pastos más bajos queden antes que los más altos en el arreglo cows.

Esto nos permite comprobar solo conflictos en un sentido, ya que asignamos los colores de menor a mayor.

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

C++JavaPython


#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
constexpr int COLORS = 4;
 
int main() {
	std::ifstream read("revegetate.in");
	int pasture_num;
	int cow_num;
	read >> pasture_num >> cow_num;
	vector<pair<int, int>> cows(cow_num);
	for (auto &[p1, p2] : cows) {
		read >> p1 >> p2;
		p1--;  // indexación desde cero de los pastos
		p2--;
		if (p1 > p2) { std::swap(p1, p2); }
	}
 
	// Empiezan todos los pastos sin tipo de pasto (0)
	vector<int> pastures(pasture_num);
	for (int p = 0; p < pasture_num; p++) {
		int color = 1;
		for (; color <= COLORS; color++) {
			// ¿Este color entra en conflicto con algún otro color existente?
			bool conflicts = false;
			for (const auto &[a, b] : cows) {
				if (pastures[a] == color && b == p) {
					conflicts = true;
					break;
				}
			}
			// Si no, podemos dejar de buscar.
			if (!conflicts) { break; }
		}
		pastures[p] = color;
	}
 
	std::ofstream written("revegetate.out");
	for (int p : pastures) { written << p; }
	written << endl;
}


import java.io.*;
import java.util.*;
 
 
public class Revegetate {
	private static final int COLORS = 4;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("revegetate.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int pastureNum = Integer.parseInt(initial.nextToken());
		int cowNum = Integer.parseInt(initial.nextToken());
		int[][] cows = new int[cowNum][2];
		for (int c = 0; c < cowNum; c++) {
			StringTokenizer p = new StringTokenizer(read.readLine());
			int p1 = Integer.parseInt(p.nextToken()) - 1;  // indexación desde cero de los pastos
			int p2 = Integer.parseInt(p.nextToken()) - 1;
			cows[c][0] = Math.min(p1, p2);
			cows[c][1] = Math.max(p1, p2);
		}
 
		// Empiezan todos los pastos sin tipo de pasto (0)
		int[] pastures = new int[pastureNum];
		for (int p = 0; p < pastureNum; p++) {
			int color = 1;
			for (; color <= COLORS; color++) {
				// ¿Este color entra en conflicto con algún otro color existente?
				boolean conflicts = false;
				for (int[] c : cows) {
					if (pastures[c[0]] == color && c[1] == p) {
						conflicts = true;
						break;
					}
				}
				// Si no, podemos dejar de buscar.
				if (!conflicts) { break; }
			}
			pastures[p] = color;
		}
 
		PrintWriter written = new PrintWriter("revegetate.out");
		for (int p : pastures) { written.print(p); }
		written.println();
		written.close();
	}
}


COLORS = 4
 
with open("revegetate.in") as read:
	pasture_num, cow_num = map(int, read.readline().split())
	cows = []
	for _ in range(cow_num):
		p1, p2 = sorted(map(int, read.readline().split()))
		cows.append((p1 - 1, p2 - 1))  # indexación desde cero de los pastos
 
# Empiezan todos los pastos sin tipo de pasto (0)
pastures = [0 for _ in range(pasture_num)]
for p in range(pasture_num):
	for color in range(1, COLORS + 1):
		# ¿Este color entra en conflicto con algún otro color existente?
		if any(pastures[a] == color and b == p for a, b in cows):
			continue
 
		# Si no, podemos dejar de buscar.
		break
 
	pastures[p] = color
 
print("".join(map(str, pastures)), file=open("revegetate.out", "w"))

Solución 2

Explicación

Podemos iterar por los pastos favoritos e incrementar en uno el pasto con el índice mayor, haciendo el resultado mínimo. Todos los pastos empiezan con tipo de pasto 1, y solo incrementamos cuando hace falta para que el resultado sea lo más pequeño posible.

También recorremos los pastos favoritos anteriores para asegurarnos de que los cambios nuevos no arruinen los anteriores.

Implementación

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

C++JavaPython


#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
int main() {
	std::ifstream read("revegetate.in");
 
	// Leemos la entrada de la misma forma que en la otra implementación
	int pasture_num;
	int cow_num;
	read >> pasture_num >> cow_num;
	vector<pair<int, int>> cows(cow_num);
	for (auto &[p1, p2] : cows) {
		read >> p1 >> p2;
		p1--;
		p2--;
		if (p1 > p2) { std::swap(p1, p2); }
	}
 
	vector<int> pastures(pasture_num, 1);
 
	// Asignamos primero los pastos de adelante.
	std::sort(cows.begin(), cows.end());
	for (int c = 0; c < cow_num; c++) {
		const auto &[a, b] = cows[c];
		if (pastures[a] != pastures[b]) { continue; }
 
		// Incrementamos en uno el pasto posterior
		pastures[b]++;
 
		// Todos los pastos favoritos hasta el actual.
		for (int prev_c = 0; prev_c < c; prev_c++) {
			/*
			 * Incrementamos de nuevo si el requisito no se cumple.
			 * Esto también significa que una de las vacas del req. anterior
			 * tiene que ser igual a b, ya que ese es el único
			 * pasto que tocamos.
			 */
			const auto &[i, j] = cows[prev_c];
			if (pastures[i] == pastures[j]) { pastures[b]++; }
		}
	}
 
	std::ofstream written("revegetate.out");
	for (int p : pastures) { written << p; }
	written << endl;
}


import java.io.*;
import java.util.*;
 
 
public class Revegetate {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("revegetate.in"));
 
		// Leemos la entrada de la misma forma que en la otra implementación
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int pastureNum = Integer.parseInt(initial.nextToken());
		int cowNum = Integer.parseInt(initial.nextToken());
		int[][] cows = new int[cowNum][2];
		for (int c = 0; c < cowNum; c++) {
			StringTokenizer p = new StringTokenizer(read.readLine());
			int p1 = Integer.parseInt(p.nextToken()) - 1;  // indexación desde cero de los pastos
			int p2 = Integer.parseInt(p.nextToken()) - 1;
			cows[c][0] = Math.min(p1, p2);
			cows[c][1] = Math.max(p1, p2);
		}
 
		int[] pastures = new int[pastureNum];
		Arrays.fill(pastures, 1);
 
		// Asignamos primero los pastos de adelante.
		Arrays.sort(cows, Arrays::compare);
		for (int c = 0; c < cowNum; c++) {
			int[] cow = cows[c];
			if (pastures[cow[0]] != pastures[cow[1]]) { continue; }
 
			// Incrementamos en uno el pasto posterior
			pastures[cow[1]]++;
 
			// Todos los pastos favoritos hasta el actual.
			for (int prevC = 0; prevC < c; prevC++) {
				/*
				 * Incrementamos de nuevo si el requisito no se cumple.
				 * Esto también significa que una de las vacas del req. anterior
				 * tiene que ser igual a cow[1], ya que ese es el único
				 * pasto que tocamos.
				 */
				if (pastures[cows[prevC][0]] == pastures[cows[prevC][1]]) {
					pastures[cow[1]]++;
				}
			}
		}
 
		PrintWriter written = new PrintWriter("revegetate.out");
		for (int p : pastures) { written.print(p); }
		written.println();
		written.close();
	}
}


# Leemos la entrada de la misma forma que en la otra implementación
with open("revegetate.in") as read:
	pasture_num, cow_num = map(int, read.readline().split())
	cows = []
	for _ in range(cow_num):
		p1, p2 = sorted(map(int, read.readline().split()))
		cows.append((p1 - 1, p2 - 1))
 
pastures = [1] * pasture_num
 
# Asignamos primero los pastos de adelante.
cows.sort()
for c, (a, b) in enumerate(cows):
	if pastures[a] != pastures[b]:
		continue
 
	# Incrementamos en uno el pasto posterior
	pastures[b] += 1
 
	# Todos los pastos favoritos hasta el actual.
	for i, j in cows[:c]:
		"""
		Incrementamos de nuevo si el requisito no se cumple.
		Esto también significa que una de las vacas del req. anterior
		tiene que ser igual a b, ya que ese es el único
		pasto que tocamos.
		"""
		if pastures[i] == pastures[j]:
			pastures[b] += 1
 
print("".join(map(str, pastures)), file=open("revegetate.out", "w"))

Solución 3

Solución 3 (más rápida)

Explicación

Como en la solución 1, recorremos todos los pastos, asignándole a cada uno el color más bajo que no entre en conflicto con ninguno de los requisitos. Sin embargo, en lugar de recorrer todos los requisitos, solo iteramos por aquellos requisitos para los que el pasto actual es el mayor.

Podemos hacer esto de forma eficiente guardando la entrada con listas de adyacencia.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ifstream fin("revegetate.in");
	ofstream fout("revegetate.out");
 
	int N, M;
	fin >> N >> M;
	vector<vector<int>> adj(N);
	for (int e = 0; e < M; ++e) {
		int a, b;
		fin >> a >> b;
		--a, --b;
		adj.at(max(a, b)).push_back(min(a, b));
	}
 
	const int MAX_COLORS = 4;
	vector<int> color(N, 1);
	for (int b = 0; b < N; ++b) {
		assert(size(adj.at(b)) < MAX_COLORS);
		vector<bool> used(MAX_COLORS + 1);
		for (int a : adj.at(b)) { used.at(color.at(a)) = true; }
		while (used.at(color.at(b))) { ++color.at(b); }
		fout << color.at(b);
	}
	fout << "\n";
}


import java.io.*;
import java.util.*;
 
public class Revegetate {
 
	static final int MAX_COLORS = 4;
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("revegetate");
		int n = io.nextInt();
		int m = io.nextInt();
 
		ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
		for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); }
 
		for (int i = 0; i < m; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj.get(Math.max(a, b)).add(Math.min(a, b));
		}
 
		int[] color = new int[n];
		for (int i = 0; i < n; i++) { color[i] = 1; }
 
		for (int b = 0; b < n; b++) {
			boolean[] used = new boolean[MAX_COLORS + 1];
			for (int a : adj.get(b)) { used[color[a]] = true; }
			while (used[color[b]]) { color[b]++; }
			io.print(color[b]);
		}
		io.println();
		io.close();
	}
 
	// CodeSnip{Kattio}
}


MAX_COLORS = 4
 
with open("revegetate.in", "r") as read:
	n, m = map(int, read.readline().split())
 
	adj = [[] for _ in range(n)]
	for _ in range(m):
		a, b = map(int, read.readline().split())
		a -= 1
		b -= 1
		adj[max(a, b)].append(min(a, b))
 
 
color = [1] * n
 
with open("revegetate.out", "w") as write:
	for b in range(n):
		used = [False] * (MAX_COLORS + 1)
 
		for a in adj[b]:
			used[color[a]] = True
 
		while used[color[b]]:
			color[b] += 1
 
		write.write(str(color[b]))

Solución en video

Por Jay Fu

Video de YouTube (GT9PEJbJjxo)

Código de la solución en video

C++Java


#include <fstream>
#include <iostream>
using namespace std;
 
int main(void) {
	// N es la cantidad de pastos
	int N;
	// M es la cantidad de vacas de FJ
	// o sea, la cantidad de pares de pastos que no pueden tener el mismo tipo de pasto
	// entre sí
	int M;
	// A y B contienen los números de pasto de cada par de pastos
	// A contiene el número de pasto más bajo y B el más alto
	// A[i] y B[i] indica que el pasto número A[i] y el pasto
	// número B[i] no pueden tener el mismo tipo de pasto. G contiene el tipo de pasto
	// asignado a cada pasto. G[i] = x significa que al i-ésimo pasto se le asignó
	// el tipo de pasto x
	int A[151], B[151], G[101];
	ifstream fin("revegetate.in");
	// leemos la entrada
	fin >> N >> M;
	for (int i = 0; i < M; i++) {
		fin >> A[i] >> B[i];
 
		// esto asegura que A siempre contenga el número de pasto más bajo y B
		// siempre el más alto para cada par
		if (A[i] > B[i]) swap(A[i], B[i]);
	}
 
	ofstream fout("revegetate.out");
 
	// i indica el pasto actual
	// el bucle itera por cada pasto
	for (int i = 1; i <= N; i++) {
		// g indica el tipo de color actual
		int g;
 
		// el bucle itera por los 4 tipos de color
		for (g = 1; g <= 4; g++) {
			// ok indica si el tipo de color actual funciona en el pasto
			// actual
			bool ok = true;
 
			// j indica el par actual de pastos A[j] y B[j]
			// el bucle itera por cada par de pastos
			for (int j = 0; j < M; j++)
				// si el número de pasto más alto del par es el número de pasto
				// actual y al otro pasto del par ya se le asignó
				// el tipo de color actual, esto significa que el tipo de color
				// actual no funciona en el pasto actual, así que ok se pone en false
				if (B[j] == i && G[A[j]] == g) ok = false;
 
			// si ok es true, podemos pasar al siguiente pasto
			// en caso contrario, hay que probar el siguiente tipo de color
			if (ok) break;
		}
		// asignamos el tipo de color al pasto actual
		G[i] = g;
		fout << g;
	}
	fout << "\n";
	return 0;
}


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class revegetate {
	// N es la cantidad de pastos
	static int N;
	// M es la cantidad de vacas de FJ
	// o sea, la cantidad de pares de pastos que no pueden tener el mismo tipo de pasto
	// entre sí
	static int M;
	// A y B contienen los números de pasto de cada par de pastos
	// A contiene el número de pasto más bajo y B el más alto
	// A[i] y B[i] indica que el pasto número A[i] y el pasto
	// número B[i] no pueden tener el mismo tipo de pasto. G contiene el tipo de pasto
	// asignado a cada pasto. G[i] = x significa que al i-ésimo pasto se le asignó
	// el tipo de pasto x
	static int[] A, B, G;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("revegetate.in"));
		StringTokenizer s = new StringTokenizer(br.readLine());
		N = Integer.parseInt(s.nextToken());
		M = Integer.parseInt(s.nextToken());
		A = new int[151];
		B = new int[151];
		G = new int[101];
		// leemos la entrada
		for (int i = 0; i < M; i++) {
			s = new StringTokenizer(br.readLine());
			A[i] = Integer.parseInt(s.nextToken());
			B[i] = Integer.parseInt(s.nextToken());
			// esto asegura que A siempre contenga el número de pasto más bajo y
			// B siempre el más alto para cada par
			if (A[i] > B[i]) {
				int temp = A[i];
				A[i] = B[i];
				B[i] = temp;
			}
		}
		PrintWriter out = new PrintWriter("revegetate.out");
		// i indica el pasto actual
		// el bucle itera por cada pasto
		for (int i = 1; i <= N; i++) {
			// g indica el tipo de color actual
			int g;
			// el bucle itera por los 4 tipos de color
			for (g = 1; g <= 4; g++) {
				// ok indica si el tipo de color actual funciona en el
				// pasto actual
				boolean ok = true;
				// j indica el par actual de pastos A[j] y B[j]
				// el bucle itera por cada par de pastos
				for (int j = 0; j < M; j++)
					// si el número de pasto más alto del par es el número de
					// pasto actual y al otro pasto del par ya se le
					// asignó el tipo de color actual, esto significa que el
					// tipo de color actual no funciona en el pasto actual, así que
					// ok se pone en false
					if (B[j] == i && G[A[j]] == g) ok = false;
				// si ok es true, podemos pasar al siguiente pasto
				// en caso contrario, hay que probar el siguiente tipo de color
				if (ok) break;
			}
			// asignamos el tipo de color al pasto actual
			G[i] = g;
			out.print(g);
		}
		out.println();
		out.close();
	}
}