Overview of Contest Solutions

This document provides a technical analysis and optimized implementations for selected problems from the 2024 Chengxin Campus Algorithm Competition. The solutions focus on core algorithmic concepts such as simulation, graph traversal, binary search, and shortest path optimization.

L1-1: Language Environment Constraints

The first problem highlights the importance of checking environment capabilities. The task explicitly restricts the use of PHP, requiring participants to utilize other supported languages like C++ or Java. This serves as a reminder to verify compiler support and library availability before starting the implementation.

L1-2: Utility Billing Calculation

This problem reuqires implementing a tiered pricing model for utility consumption. The fee structure is piecewise: a base rate applies up to a certain threshold, a higher rate for the next bracket, and a maximum rate for consumption beyond that. The solution involves reading the input value and applying conditional logic to calculate the total cost.

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long consumption;
    if (cin >> consumption) {
        long long total_fee = 0;
        
        if (consumption <= 100) {
            total_fee = consumption * 2;
        } else if (consumption < 500) {
            total_fee = 200 + (consumption - 100) * 4;
        } else {
            total_fee = 200 + 1600 + (consumption - 500) * 10;
        }
        
        cout << total_fee << endl;
    }
    return 0;
}

L1-3: Date String Expansion

Participants must parse date strings that use two-digit years. The logic depends on a threshold: years less than or equal to "24" are interpreted as belonging to the 2000s, while others belong to the 1900s. The output requires formatting the expanded year followed by the month and day.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string raw_date;
    cin >> raw_date;

    string expanded_year;
    if (raw_date.length() < 6) {
        string prefix = raw_date.substr(0, 2);
        if (prefix <= "24") {
            expanded_year = "20";
        } else {
            expanded_year = "19";
        }
        raw_date = expanded_year + raw_date;
    }

    cout << raw_date.substr(0, 4) << "-" << raw_date.substr(4) << endl;
    return 0;
}

L1-4: Palindrome Verification

The objective is to determine if a given string reads the same forwards and backwards. A two-pointer approach is efficient here, comparing characters from the start and end moving inward until the pointers meet or a mismatch is found.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void solve() {
    string sequence;
    cin >> sequence;

    bool is_palindrome = true;
    int left = 0;
    int right = sequence.length() - 1;

    while (left < right) {
        if (sequence[left] != sequence[right]) {
            is_palindrome = false;
            break;
        }
        left++;
        right--;
    }

    cout << (is_palindrome ? "true" : "false") << endl;
}

int main() {
    int test_cases;
    if (cin >> test_cases) {
        while (test_cases--) {
            solve();
        }
    }
    return 0;
}

L1-5: Parity-Based Digit Transformation

This problem involves modifying a numeric string based on the parity of the number itself versus the parity of its length. If the parities match, digits starting from the second position (index 1) are replaced with '0' at every step. Otherwise, replacement starts from the first position (index 0). The resulting numbers are summed up.

#include <iostream>
#include <string>
#include <vector>

using namespace std;
using i64 = long long;

int main() {
    int n;
    if (cin >> n) {
        i64 total_sum = 0;
        while (n--) {
            string val_str;
            cin >> val_str;

            i64 numeric_val = stoll(val_str);
            int length = val_str.length();

            bool num_odd = (numeric_val % 2 != 0);
            bool len_odd = (length % 2 != 0);

            int start_index = (num_odd == len_odd) ? 1 : 0;

            for (int i = start_index; i < length; i += 2) {
                val_str[i] = '0';
            }

            total_sum += stoll(val_str);
        }
        cout << total_sum << endl;
    }
    return 0;
}

L1-6: Binary String Addition

Standard integer types cannot hold very large binary numbers. The solution requires simulating binary addition manually. The strings are reversed for easier index alignment, addition is performed with carry handling, and the result is reversed back to the correct order.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

string add_binary_strings(const string& a, const string& b) {
    string op1 = a;
    string op2 = b;
    reverse(op1.begin(), op1.end());
    reverse(op2.begin(), op2.end());

    int len = max(op1.length(), op2.length()) + 1;
    op1.append(len - op1.length(), '0');
    op2.append(len - op2.length(), '0');

    string result = "";
    int carry = 0;

    for (size_t i = 0; i < len; ++i) {
        int sum = (op1[i] - '0') + (op2[i] - '0') + carry;
        result += to_string(sum % 2);
        carry = sum / 2;
    }

    while (result.length() > 1 && result.back() == '0') {
        result.pop_back();
    }

    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string x, y;
    cin >> x >> y;
    cout << add_binary_strings(x, y) << endl;
    return 0;
}

L1-7: Influence Maximization on a Grid

In this grid-based problem, specific locations (marked '*') contribute values to their adjacent empty cells ('-'). The task is to accumulate these values for each empty cell and identify the coordinate with the highest total influence.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int rows, cols, k;
    if (cin >> rows >> cols >> k) {
        vector<string> grid(rows);
        for (int i = 0; i < rows; ++i) {
            cin >> grid[i];
        }

        vector<int> values(k);
        for (int i = 0; i < k; ++i) {
            cin >> values[i];
        }

        vector<vector>> grid_values(rows, vector<int>(cols, 0));
        int max_influence = 0;
        int best_x = 0, best_y = 0;

        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};

        int val_idx = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '*') {
                    for (int dir = 0; dir < 4; ++dir) {
                        int nr = r + dr[dir];
                        int nc = c + dc[dir];

                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                            if (grid[nr][nc] == '-') {
                                grid_values[nr][nc] += values[val_idx];
                                if (grid_values[nr][nc] > max_influence) {
                                    max_influence = grid_values[nr][nc];
                                    best_x = nr + 1;
                                    best_y = nc + 1;
                                }
                            }
                        }
                    }
                    val_idx++;
                }
            }
        }
        cout << best_x << " " << best_y << endl;
        cout << max_influence << endl;
    }
    return 0;
}
</int></vector></int></string>

L1-8: Block Stacking Simulation

This problem simulates placing blocks into stacks. A block can be placed on top of another block only if it is strictly smaller than the top block of that stack. The goal is to minimize the number of stacks while maximizing the hieght of the tallest stack, or simply report the maximum height and total stack count based on specific placement rules.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    if (cin >> n) {
        vector<int> blocks(n);
        for (int i = 0; i < n; ++i) {
            cin >> blocks[i];
        }

        vector<int> stack_tops;
        vector<int> stack_heights;

        for (int current_block : blocks) {
            int best_stack_index = -1;
            int min_diff = 2147483647;
            int max_height = -1;

            for (int i = 0; i < stack_tops.size(); ++i) {
                if (stack_tops[i] > current_block) {
                    int diff = stack_tops[i] - current_block;
                    if (diff < min_diff || (diff == min_diff && stack_heights[i] > max_height)) {
                        min_diff = diff;
                        best_stack_index = i;
                        max_height = stack_heights[i];
                    }
                }
            }

            if (best_stack_index != -1) {
                stack_tops[best_stack_index] = current_block;
                stack_heights[best_stack_index]++;
            } else {
                stack_tops.push_back(current_block);
                stack_heights.push_back(1);
            }
        }

        int max_h = 0;
        for (int h : stack_heights) {
            if (h > max_h) max_h = h;
        }

        cout << max_h << " " << stack_tops.size() << endl;
    }
    return 0;
}
</int></int></int>

L2-1: Graph Component and Cycle Analysis

The problem asks to count the number of connected components in a graph and how many of these components contain at least one cycle. A Depth First Search (DFS) is used to traverse components. A cycle is detected if the search encounters a visited node that is not the immediate parent.

#include <iostream>
#include <vector>

using namespace std;

void explore(const vector<vector>>& adj, int u, int parent, vector<bool>& visited, bool& cycle_found) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (visited[v]) {
            cycle_found = true;
        } else {
            explore(adj, v, u, visited, cycle_found);
        }
    }
}

int main() {
    int n, m;
    if (cin >> n >> m) {
        vector<vector>> adj(n + 1);
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<bool> visited(n + 1, false);
        int components = 0;
        int cyclic_components = 0;

        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                components++;
                bool has_cycle = false;
                explore(adj, i, -1, visited, has_cycle);
                if (has_cycle) {
                    cyclic_components++;
                }
            }
        }
        cout << components << " " << cyclic_components << endl;
    }
    return 0;
}
</bool></vector></bool></vector>

L2-2: Deck Shuffling Simulation

This problem simulates the process of shuffling a deck of cards by splitting it and interleaving, followed by dealing cards. The constraints allow for a direct simulation of the shuffling process using vector manipulations.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int total_cards, shuffle_rounds, deals_per_round, deal_index;
    if (cin >> total_cards >> shuffle_rounds >> deals_per_round >> deal_index) {
        vector<string> current_deck(total_cards);
        for (int i = 0; i < total_cards; ++i) {
            cin >> current_deck[i];
        }

        vector<string> next_deck(total_cards);
        for (int r = 0; r < shuffle_rounds; ++r) {
            int mid = total_cards / 2;
            int left_ptr = 0;
            int right_ptr = mid;

            for (int i = 0; i < total_cards; ++i) {
                if (i % 2 == 0) {
                    next_deck[i] = current_deck[left_ptr++];
                } else {
                    next_deck[i] = current_deck[right_ptr++];
                }
            }
            current_deck = next_deck;
        }

        vector<string> hand;
        int idx = deal_index - 1;
        while (idx < total_cards && hand.size() < 4) {
            hand.push_back(current_deck[idx]);
            idx += deals_per_round;
        }

        if (hand.size() < 4) {
            cout << "Error:cards not enough" << endl;
        } else {
            for (const string& card : hand) {
                // Simplified output logic for card format
                cout << card << endl;
            }
        }
    }
    return 0;
}
</string></string></string>

L2-3: Optimization via Binary Search and MST

This problem requires maximizing the minimum weight threshold ($w$) of edges in a connected graph while minimizing the total cost ($c$). The solution involves binary searching for the optimal threshold $w$, verifying connectivity for that threshold, and then running a Minimum Spanning Tree (MST) algorithm on the valid edges to find the minimum cost.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using i64 = long long;

struct Edge {
    int u, v;
    int w; // Weight
    int c; // Cost
};

struct DisjointSet {
    vector<int> parent;
    DisjointSet(int n) {
        parent.resize(n + 1);
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

bool is_connected(const vector<edge>& edges, int n, int threshold) {
    DisjointSet ds(n);
    int count = 0;
    for (const auto& e : edges) {
        if (e.w >= threshold) {
            if (!ds.connected(e.u, e.v)) {
                ds.unite(e.u, e.v);
                count++;
            }
        }
    }
    return count == n - 1;
}

i64 calculate_mst_cost(const vector<edge>& edges, int n, int threshold) {
    vector<edge> valid_edges;
    for (const auto& e : edges) {
        if (e.w >= threshold) {
            valid_edges.push_back(e);
        }
    }
    sort(valid_edges.begin(), valid_edges.end(), [](const Edge& a, const Edge& b) {
        return a.c < b.c;
    });

    DisjointSet ds(n);
    i64 total_cost = 0;
    int count = 0;
    for (const auto& e : valid_edges) {
        if (!ds.connected(e.u, e.v)) {
            ds.unite(e.u, e.v);
            total_cost += e.c;
            count++;
        }
    }
    return total_cost;
}

int main() {
    int n, m;
    if (cin >> n >> m) {
        vector<edge> edges(m);
        for (int i = 0; i < m; ++i) {
            cin >> edges[i].u >> edges[i].v >> edges[i].w >> edges[i].c;
        }

        int low = 1, high = 1000000000;
        int best_threshold = 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (is_connected(edges, n, mid)) {
                best_threshold = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        cout << best_threshold << endl;
        cout << calculate_mst_cost(edges, n, best_threshold) << endl;
    }
    return 0;
}
</edge></edge></edge></edge></int>

L2-4: Multi-Layer Shortest Path

The final problem involves finding the shortest path in a graph that represents different time periods (Past, Present, Future). The graph is expanded into layers, with edges connecting corresponding nodes across layers at a fixed cost. Dijkstra's algorithm is used to compute the shortest path, considering temporal constraints on node availability.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
using i64 = long long;

const i64 INF = 1e18;

struct Node {
    i64 dist;
    int id;
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

int get_node_id(int u, int layer, int n) {
    return u + layer * n;
}

int main() {
    int n, m, k;
    if (cin >> n >> m >> k) {
        int total_nodes = n * 3; // 3 layers: 0, 1, 2
        vector<vector int="">>> adj(total_nodes + 1);

        for (int i = 0; i < m; ++i) {
            int layer, u, v, w;
            cin >> layer >> u >> v >> w;
            int u_id = get_node_id(u, layer, n);
            int v_id = get_node_id(v, layer, n);
            adj[u_id].push_back({v_id, w});
            adj[v_id].push_back({u_id, w});
        }

        // Connect layers
        for (int u = 1; u <= n; ++u) {
            for (int l = 0; l < 2; ++l) {
                int u_curr = get_node_id(u, l, n);
                int u_next = get_node_id(u, l + 1, n);
                adj[u_curr].push_back({u_next, k});
                adj[u_next].push_back({u_curr, k});
            }
        }

        // Dijkstra
        priority_queue<node vector="">, greater<node>> pq;
        vector<i64> dist(total_nodes + 1, INF);
        
        int start_node = 1; // Assuming layer 0, node 1
        dist[start_node] = 0;
        pq.push({0, start_node});

        while (!pq.empty()) {
            Node curr = pq.top();
            pq.pop();

            if (curr.dist > dist[curr.id]) continue;

            for (auto& edge : adj[curr.id]) {
                int v = edge.first;
                int w = edge.second;
                if (dist[curr.id] + w < dist[v]) {
                    dist[v] = dist[curr.id] + w;
                    pq.push({dist[v], v});
                }
            }
        }

        int q;
        cin >> q;
        i64 min_time = INF;
        for (int i = 0; i < q; ++i) {
            int time_limit, target_node;
            cin >> target_node >> time_limit;
            
            // Check arrival at target_node in any layer
            for (int l = 0; l < 3; ++l) {
                int node_id = get_node_id(target_node, l, n);
                if (dist[node_id] != INF) {
                    if (dist[node_id] <= time_limit) {
                        min_time = min(min_time, (i64)time_limit);
                    } else {
                        min_time = min(min_time, dist[node_id]);
                    }
                }
            }
        }

        if (min_time == INF) cout << -1 << endl;
        else cout << min_time << endl;
    }
    return 0;
}
</i64></node></node></vector>