Solution 1 - Intended Solution Solution 2 - DFS Edit with LiveUpdate

USACO Silver 2019 January - Grass Planting

Authors: Neo Wang, Aadit Ambadkar

Appears In

Bronze - Introduction to Graphs

Problem Statement

Solution 1 - Intended Solution Solution 2 - DFS

Edit with LiveUpdate

Official Analysis

Solution 1 - Intended Solution

Time Complexity: $\mathcal{O}(N)$

Let $\texttt{deg}[i]$ represent the degree of node $i$ : the number of paths connecting the node. Then, considering that node, and that node alone, you would need $\texttt{deg}[i]+1$ grass types. This is because you would need $\texttt{deg}[i]$ for each of the adjacent nodes, and $1$ for the node itself. It can be shown that the tree can also be colored accordingly in $\max(\texttt{deg}[i])+1$ colors.

Java

import java.io.*;
import java.util.StringTokenizer;

public class GrassPlanting {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("planting");
		int n = io.nextInt();
		int[] deg = new int[n+1];
		for(int i = 0; i < n-1; i++) {
			int a = io.nextInt(), b = io.nextInt();

Solution 2 - DFS

Time Complexity: $\mathcal{O}(N)$

This can also be solved using DFS. The solution is less elegant but generates a valid assignment of grass types in the $\texttt{ans}$ array.

Java

import java.io.*;
import java.util.*;
public class Main {
	public static int[] ans;
	public static List<Integer>[] adj;
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new FileReader("planting.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("planting.out")));
		StringTokenizer st = new StringTokenizer(f.readLine());
		int farms = Integer.parseInt(st.nextToken());

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!