Problem A: Partitioning a String into Segments

This problem requires splitting a string of length n into substrings of length p or q. The solution must determine if such a partition is possible using only these two specific lengths and output the resulting segments.

Approach:

The core logic relies on finding non-negative integers x and y such that the equation x * p + y * q = n holds true. We can iterate through all possible counts of segments with size p (from the maximum possible down to 0). For each iteration, we check if the remaining length (n - count * p) is perfectly divisible by q. If the condition is met, we construct the result by slicing the string accordingly. If the loop completes without finding a valid combination, we return -1.

void solveStringSplit() {
    int n, p, q;
    string text;
    cin >> n >> p >> q >> text;

    vector<string> segments;
    bool possible = false;

    // Iterate potential number of segments of size p
    for (int i = 0; i <= n; ++i) {
        int remaining = n - i * p;
        if (remaining < 0) break;
        
        // Check if remainder can be divided by q
        if (remaining % q == 0) {
            int j = remaining / q;
            string temp = text;
            
            // Extract segments of size p
            for (int k = 0; k < i; ++k) {
                segments.push_back(temp.substr(0, p));
                temp.erase(0, p);
            }
            
            // Extract segments of size q
            for (int k = 0; k < j; ++k) {
                segments.push_back(temp.substr(0, q));
                temp.erase(0, q);
            }
            possible = true;
            break;
        }
    }

    if (possible) {
        cout << segments.size() << "\n";
        for (const auto& seg : segments) {
            cout << seg << "\n";
        }
    } else {
        cout << -1 << "\n";
    }
}

Problem B: Calculating Permutation Index Distances

Given a sequence containing a permutation of integers from 1 to n, the task is to compute the sum of absolute differences between the positions (indices) of consecutive integers.

Approach:

We first map each value in the sequence to its 1-based index. Then, we iterate from 1 to n-1. For each integer i, we add the absolute difference between the index of i and the index of i+1 to our total sum.

void solvePermutationMetric() {
    int n;
    cin >> n;
    map<int, int> valueToIndex;

    for (int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        valueToIndex[val] = i;
    }

    long long totalDistance = 0;
    for (int i = 1; i < n; ++i) {
        totalDistance += abs(valueToIndex[i] - valueToIndex[i + 1]);
    }
    
    cout << totalDistance << "\n";
}

Problem C: Fixing Bracket Sequences

The objective is to determine the minimum number of replacements required to make a string of brackets "regular" (balanced and correctly matched). The string contains four types of brackets: (), [], {}, and <>. If it is impossible to balance the sequence, the solution should return "Impossible".

Approach:

First, we verify if the total number of opening brackets matches the total number of closing brackets. We also ensure that no prefix of the string has more closing brackets than opening ones. If either condition fails, the sequence is impossible to fix. Then, we use a stack to process the string. When encountering a closing bracket, we check if it matches the type of the opening bracket at the top of the stack. If it does not match, we increment the replacement counter.

void solveBracketSequence() {
    string s;
    cin >> s;
    unordered_map<char, int> bracketType;
    // 1 for opening, 0 for closing
    bracketType['('] = bracketType['['] = bracketType['{'] = bracketType['<'] = 1;
    bracketType[')'] = bracketType[']'] = bracketType['}'] = bracketType['>'] = 0;

    int openCount = 0, closeCount = 0;
    for (char c : s) {
        if (bracketType[c]) openCount++;
        else closeCount++;
        if (closeCount > openCount) {
            cout << "Impossible" << endl;
            return;
        }
    }

    if (openCount != closeCount) {
        cout << "Impossible" << endl;
        return;
    }

    stack<char> st;
    int replacements = 0;
    for (char c : s) {
        if (bracketType[c]) {
            st.push(c);
        } else {
            if (!st.empty()) {
                char top = st.top();
                // Check for mismatched types
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{') ||
                    (c == '>' && top != '<')) {
                    replacements++;
                }
                st.pop();
            }
        }
    }
    cout << replacements << endl;
}

Problem D: Union of k-Segments

This problem asks for the union of all segments that are covered by at least k other segments. Given n segments on a line, we must find the total length and the specific intervals where the coverage depth is greater than or equal to k.

Approach:

We utilize a sweep line algorithm. We represent the start and end of every segment as events. These events are sorted by their coordinate. If coordinates are equal, start events are processed before end events to ensure correct interval boundaries. We iterate through the sorted events, maintaining a counter for the number of active segemnts. When the counter reaches k, we record the start of a valid interval. When it drops below k, we record the end of that interval.

struct Event {
    int position;
    int type; // 0 for start, 1 for end
    bool operator<(const Event& other) const {
        if (position != other.position) return position < other.position;
        return type < other.type; // Start (0) comes before End (1)
    }
};

void solveKSegments() {
    int n, k;
    cin >> n >> k;
    vector<Event> events;

    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        events.push_back({l, 0}); // Start event
        events.push_back({r, 1}); // End event
    }

    sort(events.begin(), events.end());

    vector<pair<int, int>> result;
    int activeCount = 0;
    int intervalStart = -1;

    for (const auto& ev : events) {
        if (ev.type == 0) { // Start
            activeCount++;
            if (activeCount == k) {
                intervalStart = ev.position;
            }
        } else { // End
            if (activeCount == k) {
                result.push_back({intervalStart, ev.position});
            }
            activeCount--;
        }
    }

    cout << result.size() << "\n";
    for (const auto& seg : result) {
        cout << seg.first << " " << seg.second << "\n";
    }
}