USACO Bronze 2018 Open - Family Tree

Authors: Danh Ta Chi Thanh, Ryan Chou, Chuyang Wang, Kevin Sheng, Amogha Pokkulandra

Edit This Page

Video Solution

By Amogha Pokkulandra

Video Solution Code

Solution

Official Analysis (C++)

By finding the closest common ancestor and the distances from the ancestor to the two cows, we can uniquely identify their relationship.

Implementation

Time Complexity: O(N3)\mathcal{O}(N^3)

Python

import sys


sys.stdin = open("family.in", "r")
sys.stdout = open("family.out", "w")


rel_num, cow_a, cow_b = input().split()
relations = []


for i in range(int(rel_num)):
	relations.append(input().split())

Java

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


public class FamilyTree {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader("family.in"));
		PrintWriter out = new PrintWriter("family.out");


		StringTokenizer st = new StringTokenizer(in.readLine());
		int relNum = Integer.parseInt(st.nextToken());

C++

#include <fstream>
#include <string>
#include <vector>


using std::string;
using std::vector;
using Relation = std::pair<string, string>;


// finds the mother of given child among those pairs (returns null if no mother)
string mother(const string &child, const vector<Relation> &relations) {

Alternative Solution - BFS

Note: This is an alternative solution and makes use of concepts outside the scope of Bronze. Breadth-first search is not necessary to know for the bronze division.

Time Complexity: O(Nlog⁡N)\mathcal{O}(N \log N)

This problem can also be solved by using BFS to find the common ancestors and the distance between the two cows and their nearest common ancestor.

Warning!

No Bronze / Silver problem has required knowledge of BFS, so feel free to skip this solution if you find it unfamiliar and come back later.

Java

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


public class Family {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("family.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int N = Integer.parseInt(initial.nextToken());
		String[] cows = new String[] {initial.nextToken(), initial.nextToken()};

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	freopen("family.in", "r", stdin);
	int N;
	vector<string> cows(2);
	cin >> N >> cows[0] >> cows[1];


	map<string, string> edge;

Python

with open("family.in") as read:
	cows = [None, None]
	N, cows[0], cows[1] = read.readline().split()
	N = int(N)


	edge = {}
	for _ in range(N):
		v, u = read.readline().split()
		edge[u] = v

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!

Join Forum