profile picture
Yash Singh
USACO Blocks

USACO Blocks

In this blog post I'll go over the USACO Blocks Bronze February 2022 Problem 3 using other resources and solutions.


We are given four dice with letters on them and a list of words to spell. We have to print out "YES" if the word can be spelled by arranging the dice in a specific order and "NO" otherwise.


We can have a recursive function that moves from letter to letter and gives the avaliable dice that can be used for each one. This will take in worst case O(4!×N)O(4!\times N) which takes 10×24=24010\times24=240 operations.


Let's go through an implementation in C++:

#include <bits/stdc++.h>

using namespace std;

string die[4];

// Recursive function to check if can make word
// r: already used dice
// word: left part of word to spell
bool can_make(string word, map<int, bool> r) {
    if (word.size() == 0) {
        return true;
    // Chop off first part of word
    char first{word[0]};
    word = word.substr(1, word.size() - 1);
    bool canmakeinend{false};
    // Iterate over the dice
    for (int i{0}; i < 4; ++i) {
        // If dice not already used
        if (r.find(i) == r.end()) {
            // Check if the dice contains the character we are looking for
            bool g{false};
            for (auto ch: die[i]) {
                if (ch == first) {
                    g = 1;
            if (g) {
                // Recursively check if we can make the rest of the word
                r[i] = 1;
                if (can_make(word, r)) {
                    canmakeinend = true;
    if (canmakeinend) {
        return true;
    return false;

int main() {
  int n;
  cin >> n;
  cin >> die[0] >> die[1] >> die[2] >> die[3];
  // Run the can_make function on each test case
  while (n--) {
    string word;
    cin >> word;
    map<int, bool> r;
    if (can_make(word, r)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;

Lessons Learnt

Not too many lessons learned from this problem, just an implementation problem assessing whether you understand recursive programming.