Official Analysis (C++)

Video Solution

By Nikhil Chatterjee

Video Solution Code

Explanation

We compare each pair of animals and check how many characteristics they share. If they share XX characteristics, then we need at least X+1X + 1 questions. Taking the maximum of the number of questions across all pairs gives us our answer.

Implementation

Time Complexity: O(N2K)\mathcal{O}(N^2K)

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <set>
#include <string>
#include <vector>


using std::cout;
using std::endl;
using std::set;

Java

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


public class Guess {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("guess.in"));
		int animalNum = Integer.parseInt(read.readLine());


		HashSet<String>[] animals = new HashSet[animalNum];
		for (int a = 0; a < animalNum; a++) {

Python

animals = []
with open("guess.in") as read:
	animal_num = int(read.readline())
	for _ in range(animal_num):
		line = read.readline().split()
		# We don't care about the 1st or 2nd token.
		animals.append(set(line[2:]))


max_yes = 0
for a1 in range(animal_num):

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