USACO 2022 February Contest Bronze Division - Blocks

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

For each query, we brute force every permutation and check if we can find the suitable letter there for each position.

Source codes

The source codes in C++ and Python can be seen below.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string v[4];

    int n;
    cin >> n;

    cin >> v[0] >> v[1] >> v[2] >> v[3];

    while(n--)
    {
        string s;
        cin >> s;

        vector<int> vv = {0, 1, 2, 3};

        bool okoverall = 0;
        do{
            bool ok = 1;
            for(int j = 0; ok && j < s.size(); j++)
            {
                ok = 0;
                for(int x = 0; x < v[vv[j]].size(); x++)    
                    if(v[vv[j]][x] == s[j])
                        ok = 1;
            }
            okoverall |= ok;
        }while(next_permutation(vv.begin(), vv.end()));

        cout << (okoverall == 1 ? "YES" : "NO") << '\n';
    }
    return 0;
}

import itertools

n = int(input())
v = [input().strip() for _ in range(4)]
for _ in range(n):
    s = input().strip()
    okoverall = False
    for perm in itertools.permutations(range(4)):
        ok = True
        for j in range(len(s)):
            ok = False
            for x in range(len(v[perm[j]])):
                if v[perm[j]][x] == s[j]:
                    ok = True
                    break
            if not ok:
                break
        okoverall |= ok
    print("YES" if okoverall else "NO")