Problem D - Take ABC 2

An efficient approach involves processing the string from the end to identify and count valid "ABC" sequences.

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

void processString() {
    string input;
    cin >> input;
    vector<int> posA, posB, posC;
    
    for (int idx = 0; idx < input.length(); idx++) {
        if (input[idx] == 'A') posA.push_back(idx);
        else if (input[idx] == 'B') posB.push_back(idx);
        else if (input[idx] == 'C') posC.push_back(idx);
    }
    
    int result = 0;
    while (!posC.empty()) {
        int cPos = posC.back();
        posC.pop_back();
        
        while (!posB.empty() && posB.back() > cPos)
            posB.pop_back();
        if (posB.empty()) break;
        
        int bPos = posB.back();
        posB.pop_back();
        
        while (!posA.empty() && posA.back() > bPos)
            posA.pop_back();
        if (posA.empty()) break;
        
        posA.pop_back();
        result++;
    }
    cout << result;
}

Problem E - Divide Graph

This solution uses a union-find data structure to determine the minimum edges needed to split the graph into two connected components.

#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 100005;
const int MOD = 998244353;

struct Edge {
    int from, to, weight;
};

int parent[MAX_N];
long long power[MAX_N];

int findRoot(int x) {
    if (x == parent[x]) return x;
    return parent[x] = findRoot(parent[x]);
}

bool compareEdges(Edge x, Edge y) {
    return x.weight > y.weight;
}

void solveGraph() {
    int n, m;
    cin >> n >> m;
    
    power[0] = 1;
    for (int i = 1; i <= m; i++)
        power[i] = (power[i-1] * 2) % MOD;
    
    vector<Edge> edges(m+1);
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v, i};
    }
    
    sort(edges.begin() + 1, edges.end(), compareEdges);
    
    int components = n;
    long long answer = 0;
    
    for (int i = 1; i <= m; i++) {
        int rootU = findRoot(edges[i].from);
        int rootV = findRoot(edges[i].to);
        
        if (rootU != rootV) {
            if (components > 2) {
                parent[rootU] = rootV;
                components--;
            } else {
                answer = (answer + power[edges[i].weight]) % MOD;
            }
        }
    }
    cout << answer;
}

Problem F - Centipede Graph

A tree dynamic programming solution that comuptes the maximum centipeed path length in a tree structure.

#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 200005;
vector<int> tree[MAX_N];
int dp[MAX_N][2], children[MAX_N];

void countChildren(int node, int parent) {
    for (int neighbor : tree[node]) {
        if (neighbor == parent) continue;
        children[node]++;
        countChildren(neighbor, node);
    }
}

void computeDP(int node, int parent) {
    int firstMax = 0, secondMax = 0;
    
    if (children[node] >= 2) {
        dp[node][1] = 1;
        dp[node][0] = 1;
    }
    if (children[node] >= 1 && parent != 0)
        dp[node][0] = 1;
    
    for (int neighbor : tree[node]) {
        if (neighbor == parent) continue;
        computeDP(neighbor, node);
        
        if (dp[neighbor][1] >= firstMax) {
            secondMax = firstMax;
            firstMax = dp[neighbor][1];
        } else if (dp[neighbor][1] > secondMax) {
            secondMax = dp[neighbor][1];
        }
        dp[node][0] = max(dp[node][0], dp[neighbor][0]);
    }
    
    if (node == 1) {
        if (children[node] >= 4)
            dp[node][0] = max(dp[node][0], firstMax + secondMax + 1);
        if (children[node] == 3)
            dp[node][0] = max(dp[node][0], firstMax + 1);
    } else {
        if (children[node] >= 3)
            dp[node][0] = max(dp[node][0], firstMax + secondMax + 1);
        if (children[node] == 2)
            dp[node][0] = max(dp[node][0], firstMax + 1);
    }
    
    if (children[node] >= 3)
        dp[node][1] = firstMax + 1;
}

void solveCentipede() {
    int n;
    cin >> n;
    
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    countChildren(1, 0);
    computeDP(1, 0);
    cout << dp[1][0] << endl;
}