USACO 2022 US Open Contest Silver Division - Subset Equality

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Important observation: if we can't get done with some letters, adding more letters won't help.

In addition, we can reduce checking to each pair of two letters.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>

using namespace std;

int frq[26], frq2[26];
bool ok[26][26];

int main() {
    string s, t;
    cin >> s >> t;

    for (int i = 0; i < s.size(); i++) 
        frq[s[i] - 'a']++;
    for (int i = 0; i < t.size(); i++) 
        frq2[t[i] - 'a']++;

    for (char x = 'a'; x <= 'z'; x++)
        for (char y = 'a'; y <= 'z'; y++) {
            string s2, t2;
            for (int j = 0; j < s.size(); j++)
                if (s[j] == x || s[j] == y) 
                    s2 += s[j];
            for (int j = 0; j < t.size(); j++)
                if (t[j] == x || t[j] == y)
                    t2 += t[j];
            if (s2 == t2) {
                ok[x - 'a'][y - 'a'] = 1;
            }
        }

    int q;
    cin >> q;
    for (; q; q--) {
        string x;
        cin >> x;

        bool oki = 1;
        for (int j = 0; j < x.size(); j++)
            if (frq[x[j] - 'a'] != frq2[x[j] - 'a']) 
                oki = 0;

        for (int j = 0; j < x.size(); j++)
            for (int k = 0; k < x.size(); k++)
                if (ok[x[j] - 'a'][x[k] - 'a'] == 0) 
                    oki = 0;

        cout << (oki == 0 ? "N" : "Y");
    }

    return 0;
}