USACO 2016 December Contest, Bronze
Problem 2. Block Game
Contest has ended.
To help the cows with their spelling, Farmer John wants to fashion a number of wooden blocks, each embossed with a single letter of the alphabet. He wants to make sufficiently many blocks of each letter so that no matter which set of $N$ words is exposed on the upward-facing boards, the cows will be able to spell all of these words using the blocks. For example, if $N=3$ and the words 'box', 'cat', and 'car' were facing upward, the cows would need at least one 'b' block, one 'o' block, one 'x' block, two 'c' blocks, two 'a' blocks, one 't' block, and one 'r' block.
Please help the Farmer John determine the minimum number of blocks for each letter of the alphabet that he needs to provide, so that irrespective of which face of each board is showing, the cows can spell all $N$ visible words.
INPUT FORMAT (file blocks.in):Line 1 contains the integer $N$.
The next $N$ lines each contain 2 words separated by a space, giving the two words on opposite sides of a board. Each word is a string of at most 10 lowercase letters.
OUTPUT FORMAT (file blocks.out):Please output 26 lines. The first output line should contain a number specifying the number of copies of 'a' blocks needed. The next line should specify the number of 'b' blocks needed, and so on.
3 fox box dog cat car bus
2 2 2 1 0 1 1 0 0 0 0 0 0 0 2 0 0 1 1 1 1 0 0 1 0 0
In this example, there are $N = 3$ boards, giving $2^3 = 8$ possibilities for the set of upward-facing words:
fox dog car fox dog bus fox cat car fox cat bus box dog car box dog bus box cat car box cat busWe need enough blocks for each letter of the alphabet so that we can spell all three words, irrespective of which of these eight scenarios occurs.
Problem credits: Viktoriia Schwartz