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 1

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) {

Solution 2

Similar to solution 1, but we find the common ancestor of the two cows more efficiently.

Implementation

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

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

Solution 3

Let's first create a map from each cow to its parent. Now let's handle this case by case.

  1. XX and YY being siblings is equivalent to them having the same parent.

  2. YY being a *-mother of XX is equivalent to YY equaling some ancestor of XX. We can iterate over the ancestors of XX by starting with our current cow being XX and then repeatedly setting the current cow to its parent.

  3. YY being a *-aunt of XX is equivalent YY and some ancestor of XX being siblings. We can handle this by combining cases 1 and 2.

  4. We can handle XX being a *-mother of YY and XX being a *-aunt of YY by swapping XX and YY and applying the same logic.

  5. If XX and YY's oldest ancestors are the same, then they are related.

  6. Otherwise, if none of the cases above apply, then XX and YY are not related.

Implementation

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

C++

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


int main() {
	ifstream fin("family.in");
	ofstream fout("family.out");


	int N;
	string c1, c2;
	fin >> N >> c1 >> c2;

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