Problem A: Is It a Cat?

Givan a string and its length, output "YES" if the string satisfies the following conditions; otherwise, output "NO":

• The string consists of exactly four segments.
• Each segment contains only one letter (case-insensitive), in the exact sequence: 'm', 'e', 'o', 'w'.

There are t test cases.

Approach

The solution checks whether the string contains only the allowed letters (case-insensitive) and weather these letters appear in four contiguous blocks in the required order. It also verifies that no other characters are present.

Code

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int len;
        string inputStr;
        cin >> len >> inputStr;
        int positions[4][2];
        memset(positions, -1, sizeof(positions));
        int validCount = 0;
        for (int idx = 0; idx < len; idx++) {
            char current = tolower(inputStr[idx]);
            if (current == 'm') {
                if (positions[0][0] == -1) positions[0][0] = idx;
                positions[0][1] = idx;
                validCount++;
            } else if (current == 'e') {
                if (positions[1][0] == -1) positions[1][0] = idx;
                positions[1][1] = idx;
                validCount++;
            } else if (current == 'o') {
                if (positions[2][0] == -1) positions[2][0] = idx;
                positions[2][1] = idx;
                validCount++;
            } else if (current == 'w') {
                if (positions[3][0] == -1) positions[3][0] = idx;
                positions[3][1] = idx;
                validCount++;
            }
        }
        bool validOrder = positions[0][0] == 0 &&
                         positions[1][0] == positions[0][1] + 1 &&
                         positions[2][0] == positions[1][1] + 1 &&
                         positions[3][0] == positions[2][1] + 1 &&
                         positions[3][1] == len - 1 &&
                         validCount == len;
        cout << (validOrder ? "YES" : "NO") << endl;
    }
    return 0;
}

Problem B: Count the Number of Pairs

Given n, k, and a string s of length n, determine the maximum score achievable after at most k operations. Each operation changes the case of a letter. A pair of same letters in opposite cases can be merged, increasing the score by 1.

Approach

For each letter, calculate the counts of its uppercase and lowercase forms. The initial score is the minimum of these counts. The maximum additional pairs achievable per letter is floor((upperCount + lowerCount)/2) - min(upperCount, lowerCount). The total operations used cannot exceed k.

Code

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n, k;
        string s;
        cin >> n >> k >> s;
        int upper[26] = {0}, lower[26] = {0};
        for (char ch : s) {
            if (islower(ch)) lower[ch - 'a']++;
            else upper[ch - 'A']++;
        }
        int totalScore = 0;
        for (int i = 0; i < 26; i++) {
            totalScore += min(upper[i], lower[i]);
            int potential = abs(upper[i] - lower[i]) / 2;
            int used = min(potential, k);
            totalScore += used;
            k -= used;
        }
        cout << totalScore << endl;
    }
    return 0;
}

Problem C: Powering the Hero

Given n cards with energy values, where hero cards have value 0 and bonus cards have positive values. Draw cards from the top. For bonus cards, you may add them to a stack or discard. For hero cards, assign the top bonus card's energy to the hero and discard that bonus card. Maximize the total energy of all heroes.

Approach

Use a max-heap to always assign the largest available bonus card to each hero card encountered. This ensures optimal energy allocation.

Code

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        priority_queue<int> maxHeap;
        long long totalEnergy = 0;
        for (int i = 0; i < n; i++) {
            int value;
            cin >> value;
            if (value > 0) {
                maxHeap.push(value);
            } else if (!maxHeap.empty()) {
                totalEnergy += maxHeap.top();
                maxHeap.pop();
            }
        }
        cout << totalEnergy << endl;
    }
    return 0;
}

Problem D: Remove Two Letters

Given a string s of length n, find the number of distinct strings obtained by removing any two consecutive characters.

Approach

If s[i] == s[i+2], then removing (i, i+1) and (i+1, i+2) produces the same result. The total distinct strings is n-1 minus the number of such indices i.

Code

#include <iostream>
#include <string>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        string s;
        cin >> n >> s;
        int duplicates = 0;
        for (int i = 2; i < n; i++) {
            if (s[i] == s[i-2]) duplicates++;
        }
        cout << n - 1 - duplicates << endl;
    }
    return 0;
}

Problem E: Unforgivable Curse

Given n, k, and two strings a and b, determine if a can be transformed into b by swapping characters at indices differing by k or k+1.

Approach

First, check if the frequency of each character is the same in both strings. Then, verify that for every position that cannot be moved (i.e., indices that are not within k or k+1 of any swapable index), the characters in a and b match.

Code

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n, k;
        string a, b;
        cin >> n >> k >> a >> b;
        int freqA[26] = {0}, freqB[26] = {0};
        for (char ch : a) freqA[ch - 'a']++;
        for (char ch : b) freqB[ch - 'a']++;
        bool possible = true;
        for (int i = 0; i < 26; i++) {
            if (freqA[i] != freqB[i]) {
                possible = false;
                break;
            }
        }
        if (!possible) {
            cout << "NO" << endl;
            continue;
        }
        for (int i = 0; i < n; i++) {
            if (i - k < 0 && i + k >= n && a[i] != b[i]) {
                possible = false;
                break;
            }
        }
        cout << (possible ? "YES" : "NO") << endl;
    }
    return 0;
}