Grass Planting

Solución en video

Por Nikhil Chatterjee

Código de la solución en video

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("planting.in", "r", stdin);
	freopen("planting.out", "w", stdout);
	int N;
	cin >> N;
	vector<int> degree(N);
	int a, b;
	for (int i = 1; i < N; i++) {
		cin >> a >> b;
		degree[a - 1]++, degree[b - 1]++;
	}
	int result = 0;
	for (int i = 0; i < N; i++) result = max(result, degree[i]);
	cout << result + 1 << '\n';
}


import java.io.*;
import java.util.StringTokenizer;
 
 
public class Sol {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(
		    new InputStreamReader(new FileInputStream("planting.in")));
		PrintWriter writer = new PrintWriter(
		    new OutputStreamWriter(new FileOutputStream("planting.out")));
		int N = Integer.parseInt(reader.readLine());
		int[] degree = new int[N];
		for (int i = 1; i < N; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			degree[Integer.parseInt(tokenizer.nextToken()) - 1]++;
			degree[Integer.parseInt(tokenizer.nextToken()) - 1]++;
		}
		int max = 0;
		for (int i = 0; i < N; i++) { max = Math.max(max, degree[i]); }
		writer.println(max + 1);
 
		reader.close();
		writer.flush();
		writer.close();
	}
}


with open("planting.in", "r") as input_file:
	N = int(input_file.readline())
	degree = [0] * N
	a = 0
	b = 0
	for i in range(1, N):
		line = input_file.readline().split(" ")
		a = int(line[0])
		b = int(line[1])
		degree[a - 1] += 1
		degree[b - 1] += 1
 
 
result = 0
for i in range(N):
	result = max(result, degree[i])
 
 
with open("planting.out", "w") as output_file:
	output_file.write(str(result + 1))
	output_file.write("\n")

Pista 1

¿Cuántos tipos de pasto necesitará un nodo con $x$ vecinos?

Solución prevista

Análisis oficial (C++)

Explicación

Sea $\texttt{deg}[i]$ el grado del nodo $i$ : la cantidad de caminos que conectan el nodo. Entonces, considerando ese nodo, y solo ese nodo, se necesitarían $\texttt{deg}[i]+1$ tipos de pasto. Esto es porque se necesitarían $\texttt{deg}[i]$ para cada uno de los nodos adyacentes, y $1$ para el nodo en sí. Se puede mostrar que el árbol también se puede colorear en consecuencia con $\max(\texttt{deg}[i])+1$ colores.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
// FastIO: ver General -> Fast Input and Output
void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
int main() {
	setIO("planting");
 
	int field_num;
	cin >> field_num;
 
	vector<int> deg(field_num + 1);  // indexación desde uno
	for (int p = 0; p < field_num - 1; p++) {
		int field1, field2;
		cin >> field1 >> field2;
 
		deg[field1]++;
		deg[field2]++;
	}
 
	int max_deg = 0;
	for (int f = 1; f <= field_num; f++) { max_deg = max(max_deg, deg[f]); }
 
	cout << max_deg + 1 << endl;
}


import java.io.*;
import java.util.StringTokenizer;
 
public class Planting {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("planting");
 
		int fieldNum = io.nextInt();
		int[] deg = new int[fieldNum + 1];  // indexación desde uno
		for (int p = 0; p < fieldNum - 1; p++) {
			int field1 = io.nextInt();
			int field2 = io.nextInt();
			deg[field1]++;
			deg[field2]++;
		}
 
		int maxDeg = 0;
		for (int f = 1; f <= fieldNum; f++) { maxDeg = Math.max(maxDeg, deg[f]); }
 
		io.println(maxDeg + 1);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


with open("planting.in") as read:
	field_num = int(read.readline())
	deg = [0 for _ in range(field_num + 1)]  # indexación desde uno
	for _ in range(field_num - 1):
		field1, field2 = [int(i) for i in read.readline().split()]
		deg[field1] += 1
		deg[field2] += 1
 
max_deg = max(deg)
print(max_deg + 1, file=open("planting.out", "w"))

Solución alternativa

Esto también se puede resolver usando DFS. Aunque es menos elegante, tiene la ventaja subjetiva de dar realmente una disposición válida de plantación para los campos.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 10000;
 
// FastIO: ver General -> Fast Input and Output
void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
vector<int> grass_type;
vector<vector<int>> neighbors;
 
void process_fields(int at, int prev) {
	// Empezamos con el tipo de pasto 1.
	int type_num = 1;
	for (int n : neighbors[at]) {
		if (n == prev) { continue; }
		// Mientras el tipo de pasto actual esté en uso, lo incrementamos.
		while (type_num == grass_type[at] || type_num == grass_type[prev]) {
			type_num++;
		}
 
		// Asignamos el tipo de pasto del campo vecino.
		grass_type[n] = type_num;
 
		// Coloreamos recursivamente los otros campos.
		process_fields(n, at);
 
		// No podemos volver a usar este tipo de pasto.
		type_num++;
	}
}
 
int main() {
	setIO("planting");
 
	int field_num;
	cin >> field_num;
 
	grass_type = vector<int>(field_num);
	neighbors = vector<vector<int>>(field_num);
	for (int f = 0; f < field_num - 1; f++) {
		int field1, field2;
		cin >> field1 >> field2;
		neighbors[--field1].push_back(--field2);
		neighbors[field2].push_back(field1);
	}
 
	// Asignamos el tipo 1 a nuestro campo inicial.
	grass_type[0] = 1;
	process_fields(0, 0);
 
	int min_type = 0;
	for (int t : grass_type) { min_type = max(min_type, t); }
 
	cout << min_type << endl;
}


import java.io.*;
import java.util.*;
 
public class Planting {
	static int[] grassType;
	static List<Integer>[] neighbors;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("planting");
 
		int fieldNum = io.nextInt();
 
		neighbors = new List[fieldNum];
		for (int f = 0; f < fieldNum; f++) { neighbors[f] = new ArrayList<>(); }
		for (int i = 0; i < fieldNum - 1; i++) {
			int field1 = io.nextInt();
			int field2 = io.nextInt();
			neighbors[--field1].add(--field2);
			neighbors[field2].add(field1);
		}
 
		grassType = new int[fieldNum];
		// Asignamos el tipo 1 a nuestro campo inicial.
		grassType[0] = 1;
		processFields(0, 0);
 
		int minType = 0;
		for (int t : grassType) { minType = Math.max(minType, t); }
 
		io.println(minType);
		io.close();
	}
 
	static void processFields(int at, int prev) {
		// Empezamos con el tipo de pasto 1.
		int typeNum = 1;
		for (int n : neighbors[at]) {
			if (n == prev) { continue; }
			// Mientras el tipo de pasto actual esté en uso, lo incrementamos.
			while (typeNum == grassType[at] || typeNum == grassType[prev]) {
				typeNum++;
			}
 
			// Asignamos el tipo de pasto del campo vecino.
			grassType[n] = typeNum;
 
			// Coloreamos recursivamente los otros campos.
			processFields(n, at);
 
			// No podemos volver a usar este tipo.
			typeNum++;
		}
	}
 
	// CodeSnip{Kattio}
}


with open("planting.in") as read:
	field_num = int(read.readline())
	neighbors = [[] for _ in range(field_num)]
	for _ in range(field_num - 1):
		field1, field2 = [int(i) - 1 for i in read.readline().split()]
		neighbors[field1].append(field2)
		neighbors[field2].append(field1)
 
grass_type = [0 for _ in range(field_num)]
# Asignamos el tipo 1 a nuestro campo inicial.
grass_type[0] = 1
 
todo = [(0, 0)]
while todo:
	at, prev = todo.pop()
	# Empezamos con el tipo de pasto 1.
	type_num = 1
	for n in neighbors[at]:
		if n == prev:
			continue
 
		# Mientras el tipo de pasto actual esté en uso, lo incrementamos.
		while type_num in [grass_type[at], grass_type[prev]]:
			type_num += 1
 
		# Asignamos el tipo de pasto del campo vecino.
		grass_type[n] = type_num
 
		# Coloreamos recursivamente los otros campos.
		todo.append((n, at))
 
		# No podemos volver a usar este tipo.
		type_num += 1
 
print(max(grass_type), file=open("planting.out", "w"))