USACO Bronze 2016 December - Block Game

Authors: Óscar Garries, Franek Antoniak, Dong Liu, David Guo

Appears In

Bronze - Simulation

Explanation

We use a frequency array to keep track of the minimum number of blocks needed for each letter. For each pair of words, we count the occurrences of each letter in both words.

Since we can only see one side of the block at a time, we take the larger of the two frequencies for each letter and add it to the total count. Finally, after processing all pairs, we output the frequency array, which represents the total number of blocks needed for each letter.

Implementation

Time Complexity: $\mathcal{O}(NS)$ , where $S$ is the maximum length of a string.

C++

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

using std::cout;
using std::endl;
using std::string;
using std::vector;

Java

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

public class Blocks {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("blocks");
		int n = io.nextInt();
		String[][] words = new String[n][];
		for (int i = 0; i < n; i++) { words[i] = new String[] {io.next(), io.next()}; }

Python

from typing import List


def count_freq(s: str) -> List[int]:
	"""
	:return: An array of length 26, containing the frequency
	of each character in the given string.
	"""
	freq = [0] * 26
	for c in s:

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!