D - Path Traversal

A straightforward depth-first search approach can solve this traversal problem.

int nodes, edges, max_steps, min_cost, max_cost;
vector<int> valid_endpoints;
vector<pair<int, int>> graph[MAX_NODES];

void traverse(int current_node, int current_cost, int steps_taken) {
    if (current_cost > max_cost) return;
    if (steps_taken == max_steps) {
        if (current_cost >= min_cost && current_cost <= max_cost) {
            valid_endpoints.push_back(current_node);
        }
        return;
    }
    for (auto [neighbor, weight] : graph[current_node]) {
        traverse(neighbor, current_cost + weight, steps_taken + 1);
    }
}

void solve() {
    cin >> nodes >> edges >> max_steps >> min_cost >> max_cost;
    int u, v, w;
    for (int i = 1; i <= edges; i++) {
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    traverse(1, 0, 0);
    sort(valid_endpoints.begin(), valid_endpoints.end());
    valid_endpoints.erase(unique(valid_endpoints.begin(), valid_endpoints.end()), valid_endpoints.end());
    for (auto endpoint : valid_endpoints) cout << endpoint << " ";
}

E - Character Sequnece Ranking

We can map this problem to a 2D plane where 'A' is +1 and 'B' is -1. For a fixed starting position, we need to count how many subsequent values are greater than our current value. This naturally suggests using a balanced binary search tree.

int length;
string sequence;
int prefix_values[MAX_LEN];
struct TreapDataStructure {
    int node_count = 0, root = 0;
    struct node {
        int left_child, right_child;
        int key, priority;
        int size;
    } tree[MAX_NODES];
    
    void create_node(int x) {
        node_count++;
        tree[node_count].size = 1;
        tree[node_count].left_child = tree[node_count].right_child = 0;
        tree[node_count].key = x;
        tree[node_count].priority = rand();
    }
    
    void update_size(int k) {
        tree[k].size = tree[tree[k].left_child].size + tree[tree[k].right_child].size + 1;
    }
    
    void split(int u, int x, int &left_tree, int &right_tree) {
        if (u == 0) {
            left_tree = right_tree = 0;
            return;
        }
        if (tree[u].key <= x) {
            left_tree = u;
            split(tree[u].right_child, x, tree[u].right_child, right_tree);
        } else {
            right_tree = u;
            split(tree[u].left_child, x, left_tree, tree[u].left_child);
        }
        update_size(u);
    }
    
    int merge(int left_tree, int right_tree) {
        if (left_tree == 0 || right_tree == 0) return left_tree + right_tree;
        if (tree[left_tree].priority > tree[right_tree].priority) {
            tree[left_tree].right_child = merge(tree[left_tree].right_child, right_tree);
            update_size(left_tree);
            return left_tree;
        } else {
            tree[right_tree].left_child = merge(left_tree, tree[right_tree].left_child);
            update_size(right_tree);
            return right_tree;
        }
    }
    
    void insert(int x) {
        int left_tree, right_tree;
        split(root, x, left_tree, right_tree);
        create_node(x);
        root = merge(merge(left_tree, node_count), right_tree);
    }
    
    void remove(int x) {
        int left_tree, right_tree, middle_tree;
        split(root, x, left_tree, right_tree);
        split(left_tree, x-1, left_tree, middle_tree);
        middle_tree = merge(tree[middle_tree].left_child, tree[middle_tree].right_child);
        root = merge(merge(left_tree, middle_tree), right_tree);
    }
    
    int get_rank(int x) {
        int left_tree, right_tree;
        split(root, x-1, left_tree, right_tree);
        int rank = tree[left_tree].size + 1;
        root = merge(left_tree, right_tree);
        return rank;
    }
    
    int find_kth(int u, int k) {
        if (k == tree[tree[u].left_child].size + 1) return u;
        if (k <= tree[tree[u].left_child].size) return find_kth(tree[u].left_child, k);
        else return find_kth(tree[u].right_child, k - tree[tree[u].left_child].size - 1);
    }
    
    int get_predecessor(int x) {
        int left_tree, right_tree;
        split(root, x-1, left_tree, right_tree);
        int pred = tree[find_kth(left_tree, tree[left_tree].size)].key;
        root = merge(left_tree, right_tree);
        return pred;
    }
    
    int get_predecessor_strict(int x) {
        int left_tree, right_tree;
        split(root, x, left_tree, right_tree);
        int pred = tree[find_kth(left_tree, tree[left_tree].size)].key;
        root = merge(left_tree, right_tree);
        return pred;
    }
    
    int get_successor(int x) {
        int left_tree, right_tree;
        split(root, x, left_tree, right_tree);
        int succ = tree[find_kth(right_tree, 1)].key;
        root = merge(left_tree, right_tree);
        return succ;
    }
    
    int get_size() {
        return tree[root].size;
    }
    
    int get_nearest(int x) {
        int pred = get_predecessor_strict(x), succ = get_successor(x);
        if (x - pred > succ - x) return succ;
        else return pred;
    }
} treap;

void solve() {
    cin >> length >> sequence;
    sequence = " " + sequence;
    for (int i = 1; i <= length; i++) {
        if (sequence[i] == 'A') prefix_values[i] = prefix_values[i-1] + 1;
        if (sequence[i] == 'B') prefix_values[i] = prefix_values[i-1] - 1;
        if (sequence[i] == 'C') prefix_values[i] = prefix_values[i-1];
        treap.insert(prefix_values[i]);
    }
    int result = 0, remaining = length;
    for (int i = 1; i <= length; i++) {
        result += remaining - treap.get_rank(prefix_values[i-1] + 1) + 1;
        treap.remove(prefix_values[i]);
        remaining--;
    }
    cout << result;
}

F - Optimal Shopping Strategy

A classic approach involves computing prefix and suffix solutions separately.
Note that there's a subtle difference between 2D and 1D knapsack problems - values from previous items need to be inherited.

int items, capacity;
int forward_dp[1005][MAX_CAPACITY], backward_dp[1005][MAX_CAPACITY];
int prices[1050], values[1050];

void solve() {
    cin >> items >> capacity;
    for (int i = 1; i <= items; i++) {
        cin >> prices[i] >> values[i];
    }
    
    // Forward DP (from first item to current item)
    for (int i = 1; i <= items; i++) {
        for (int j = capacity; j >= 0; j--) {
            forward_dp[i][j] = max(forward_dp[i][j], forward_dp[i-1][j]);
            if (j >= prices[i]) {
                forward_dp[i][j] = max(forward_dp[i-1][j-prices[i]] + values[i], forward_dp[i][j]);
            }
        }
    }
    
    // Backward DP (from current item to last item)
    for (int i = items; i >= 1; i--) {
        for (int j = capacity; j >= 0; j--) {
            backward_dp[i][j] = max(backward_dp[i][j], backward_dp[i+1][j]);
            if (j >= prices[i]) {
                backward_dp[i][j] = max(backward_dp[i+1][j-prices[i]] + values[i], backward_dp[i][j]);
            }
        }
    }
    
    int optimal_value = forward_dp[items][capacity];
    for (int i = 1; i <= items; i++) {
        int max_with_item = 0, max_without_item = 0;
        for (int j = 0; j <= capacity; j++) {
            max_without_item = max(max_without_item, forward_dp[i-1][j] + backward_dp[i+1][capacity-j]);
            if (j >= prices[i]) {
                max_with_item = max(max_with_item, values[i] + forward_dp[i-1][j-prices[i]] + backward_dp[i+1][capacity-j]);
            }
        }
        if (max_with_item == optimal_value && max_without_item < optimal_value) cout << "A";
        if (max_with_item == optimal_value && max_without_item == optimal_value) cout << "B";
        if (max_without_item == optimal_value && max_with_item < optimal_value) cout << "C";
    }
}