Problem A

Determine if a given character is one of the vowels a, e, i, o, u.

A simple approach uses a hash map to store the vowels. For efficiency, characters are hashed by subtracting 'a', and a custom hash table implementation handles lookups.

template <class T, int P = 314159>
struct hashmap {
    u64 id[P];
    T val[P];
    int rec[P];
    hashmap() { memset(id, -1, sizeof id); }

    T get(const u64 &x) const {
        for (int i = int(x % P), j = 1; ~id[i]; i = (i + j) % P, j = (j + 2) % P)
            if (id[i] == x) return val[i];
        return 0;
    }

    T& operator[](const u64 &x) {
        for (int i = int(x % P), j = 1; ; i = (i + j) % P, j = (j + 2) % P) {
            if (id[i] == x) return val[i];
            else if (id[i] == -1llu) {
                id[i] = x;
                rec[++rec[0]] = i;
                return val[i];
            }
        }
    }

    void clear() {
        while (rec[0]) {
            id[rec[rec[0]]] = -1;
            val[rec[rec[0]]] = 0;
            --rec[0];
        }
    }
};

hashmap<int> vowelMap;

void solve() {
    vowelMap.clear();
    std::string vowels = "aeiou";
    for (char c : vowels) vowelMap[c - 'a']++;
    
    char input;
    std::cin >> input;
    bool isVowel = vowelMap.get(input - 'a');
    std::cout << (isVowel ? "vowel" : "consonant") << "\n";
}

Problem B

Given an image of size H × W, vertically stretch it to 2H × W such that each original row apppears twice consecutively.

The mapping from new row index i (1-based) to original row is ⌈i/2⌉. Equivalently, using 0-based indexing: new row i corresponds to original row ⌊i/2⌋.

void solve() {
    int H, W;
    std::cin >> H >> W;
    std::vector<std::string> original(H);
    for (int i = 0; i < H; ++i) {
        std::cin >> original[i];
    }

    for (int i = 0; i < H; ++i) {
        std::cout << original[i] << "\n";
        std::cout << original[i] << "\n";
    }
}

Problem C

Check if string S can be formed by concatenating any number of words from the set {"dream", "dreamer", "erase", "eraser"}.

A greedy forward scan fails due to prefix overlaps (e.g., "dream" is a prefix of "dreamer"). Instead, process the string from right to left, matching valid suffixes.

void solve() {
    std::set<std::string> validWords = {"dream", "dreamer", "erase", "eraser"};
    std::string s;
    std::cin >> s;
    int n = s.size();
    int pos = n;

    for (int i = n - 1; i >= 0; --i) {
        if (validWords.count(s.substr(i, pos - i))) {
            pos = i;
        }
    }

    std::cout << (pos == 0 ? "YES" : "NO") << "\n";
}

For large alphabets or performance-critical cases, rolling hashes with multiple mod bases can replace string comparisons. Alternative, dynamic programming tracks reachable positions:

std::vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 0; i <= n; ++i) {
    if (!dp[i]) continue;
    for (const auto& word : validWords) {
        int len = word.length();
        if (i + len <= n && s.substr(i, len) == word) {
            dp[i + len] = true;
        }
    }
}
std::cout << (dp[n] ? "YES" : "NO") << "\n";

Problem D

Given two undirected graphs (road and rail) over N cities, for each city count how many cities are connceted to it in both graphs.

Use union-find to compute connected components for each graph separately. For each city i, let (root_road, root_rail) be its component roots in the two graphs. The answer for all cities sharing the same pair is the size of their intersection, which equals the frequency of that pair across all cities.

const int MAXN = 200010;
int parentRoad[MAXN], parentRail[MAXN];

int find(int x, int* parent) {
    if (x != parent[x])
        parent[x] = find(parent[x], parent);
    return parent[x];
}

void unite(int a, int b, int* parent) {
    a = find(a, parent);
    b = find(b, parent);
    if (a != b) parent[a] = b;
}

void solve() {
    int N, K, L;
    std::cin >> N >> K >> L;

    for (int i = 1; i <= N; ++i) {
        parentRoad[i] = parentRail[i] = i;
    }

    for (int i = 0; i < K; ++i) {
        int u, v;
        std::cin >> u >> v;
        unite(u, v, parentRoad);
    }

    for (int i = 0; i < L; ++i) {
        int u, v;
        std::cin >> u >> v;
        unite(u, v, parentRail);
    }

    std::map<std::pair<int, int>, int> componentCount;
    for (int i = 1; i <= N; ++i) {
        int r1 = find(i, parentRoad);
        int r2 = find(i, parentRail);
        componentCount[{r1, r2}]++;
    }

    for (int i = 1; i <= N; ++i) {
        int r1 = find(i, parentRoad);
        int r2 = find(i, parentRail);
        std::cout << componentCount[{r1, r2}] << " \n"[i == N];
    }
}