Tree Isomorphism Counting

Problem ID: HDU - 7457

Approach

The solution involves counting isomorphic trees using dynamic programming. For a tree with n nodes to be valid, all subtrees of any node must have identical structures. We define dp[i] as the count of valid trees with i nodes. The recurrence relation is dp[i] = sum of dp[d] for all divisors d of (i-1). This is because the root node has one node, and the remaining (i-1) nodes must be equally distributed among the subtrees.

To compute valid forests, we note that all trees in the forest must be identical. Therefore, the answer for i nodes is the sum of dp[d] for all divisors d of i. Both computations can be optimized using harmonic series properties, resulting in O(n log n) time complexity.

Implementation

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int size;
    cin >> size;
    
    const int MOD = 998244353;
    size++;  // Adjusting for 1-based indexing
    
    vector<int> treeCount(size + 1);
    treeCount[1] = 1;  // Base case: single node tree
    
    // Calculate valid tree counts using divisor enumeration
    for (int i = 1; i <= size; i++) {
        for (int j = i * 2; j <= size; j += i) {
            treeCount[j] = (treeCount[j] + treeCount[i]) % MOD;
        }
    }
    
    // Output results
    for (int i = 2; i <= size; i++) {
        cout << treeCount[i] << (i == size ? "\n" : " ");
    }
    
    return 0;
}

Unimodal Sequence Detection

Problem ID: HDU - 7463

Approach

The solution requires checking if a sequence is unimodal using a segment tree. The segment tree maintains interval maximum, minimum, and flags indicating whether the interval is ascending or descending. To determine if all elements are equal, we check if the interval maximum equals the minimum. For unimodal sequence detection, we first find the position of the maximum value using binary search, then verify if the left part is ascending and the right part is descending.

Implementation

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

template<typename NodeType>
struct IntervalTree {
    int capacity, max_size;
    vector<NodeType> nodes;
    
    IntervalTree() : capacity(0) {}
    
    IntervalTree(int n) : capacity(n), max_size(n * 4 + 10) {
        nodes.resize(max_size);
    }
    
    IntervalTree(vector<int> data) : IntervalTree(data.size()) {
        build(1, 1, capacity, data);
    }
    
    void build(int idx, int left, int right, vector<int>& data) {
        nodes[idx].left = left;
        nodes[idx].right = right;
        reset_lazy(nodes[idx]);
        
        if (left == right) {
            nodes[idx] = {left, right, 0, data[left], data[left], true, true};
            return;
        }
        
        int mid = (left + right) / 2;
        build(idx * 2, left, mid, data);
        build(idx * 2 + 1, mid + 1, right, data);
        merge_nodes(nodes[idx], nodes[idx * 2], nodes[idx * 2 + 1]);
    }
    
    void apply_lazy(NodeType& parent, NodeType& child) {
        child.max_val += parent.lazy;
        child.min_val += parent.lazy;
    }
    
    void propagate_lazy(NodeType& parent, NodeType& child) {
        child.lazy += parent.lazy;
    }
    
    void reset_lazy(NodeType& node) {
        node.lazy = 0;
    }
    
    void push_down(int idx) {
        if (nodes[idx].lazy != 0) {
            apply_lazy(nodes[idx], nodes[idx * 2]);
            apply_lazy(nodes[idx], nodes[idx * 2 + 1]);
            propagate_lazy(nodes[idx], nodes[idx * 2]);
            propagate_lazy(nodes[idx], nodes[idx * 2 + 1]);
            reset_lazy(nodes[idx]);
        }
    }
    
    void merge_nodes(NodeType& parent, NodeType& left_child, NodeType& right_child) {
        parent.max_val = max(left_child.max_val, right_child.max_val);
        parent.min_val = min(left_child.min_val, right_child.min_val);
        
        parent.is_ascending = (left_child.max_val < right_child.min_val) && 
                             left_child.is_ascending && right_child.is_ascending;
        
        parent.is_descending = (left_child.min_val > right_child.max_val) && 
                              left_child.is_descending && right_child.is_descending;
    }
    
    void update(int idx, int left, int right, int value) {
        if (nodes[idx].left >= left && nodes[idx].right <= right) {
            nodes[idx].lazy += value;
            nodes[idx].max_val += value;
            nodes[idx].min_val += value;
            return;
        }
        
        push_down(idx);
        int mid = (nodes[idx].left + nodes[idx].right) / 2;
        
        if (left <= mid)
            update(idx * 2, left, right, value);
        if (right > mid)
            update(idx * 2 + 1, left, right, value);
            
        merge_nodes(nodes[idx], nodes[idx * 2], nodes[idx * 2 + 1]);
    }
    
    NodeType query(int idx, int left, int right) {
        if (left <= nodes[idx].left && nodes[idx].right <= right)
            return nodes[idx];
            
        push_down(idx);
        int mid = (nodes[idx].left + nodes[idx].right) / 2;
        
        if (right <= mid)
            return query(idx * 2, left, right);
        if (left > mid)
            return query(idx * 2 + 1, left, right);
            
        NodeType result, left_result = query(idx * 2, left, right), 
                 right_result = query(idx * 2 + 1, left, right);
        merge_nodes(result, left_result, right_result);
        return result;
    }
};

struct TreeNode {
    int left, right;
    long long lazy;
    long long max_val, min_val;
    bool is_ascending, is_descending;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int num_elements;
    cin >> num_elements;
    
    vector<int> sequence(num_elements + 1);
    for (int i = 1; i <= num_elements; i++) {
        cin >> sequence[i];
    }
    
    IntervalTree<TreeNode> segment_tree(sequence);
    
    int num_queries;
    cin >> num_queries;
    
    while (num_queries--) {
        int operation, left, right;
        cin >> operation >> left >> right;
        
        if (operation == 1) {
            int value;
            cin >> value;
            segment_tree.update(1, left, right, value);
        } 
        else if (operation == 2) {
            auto result = segment_tree.query(1, left, right);
            cout << (result.max_val == result.min_val) << '\n';
        } 
        else if (operation == 3) {
            auto result = segment_tree.query(1, left, right);
            cout << result.is_ascending << '\n';
        } 
        else if (operation == 4) {
            auto result = segment_tree.query(1, left, right);
            cout << result.is_descending << '\n';
        } 
        else {
            int low = left + 1, high = right - 1, peak_pos = -1;
            auto max_value = segment_tree.query(1, left + 1, right - 1).max_val;
            
            while (low <= high) {
                int mid = (low + high) / 2;
                if (segment_tree.query(1, left, mid).max_val >= max_value) {
                    high = mid - 1;
                    peak_pos = mid;
                } else {
                    low = mid + 1;
                }
            }
            
            auto left_part = segment_tree.query(1, left, peak_pos);
            auto right_part = segment_tree.query(1, peak_pos, right);
            
            if (peak_pos != -1 && left_part.is_ascending && right_part.is_descending) {
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
            }
        }
    }
    
    return 0;
}

Bitwise Shortest Path

Problem ID: HDU - 7464

Approach

This problem involves finding the shortest path in a graph where edge weights are determined by bitwise OR operations. Since x|y ≥ max(x,y), the optimal path should transition from subsets of y to minimize the weight. When x is a subset of y, x|y = y, which gives the minimal weight.

The solution uses a modified Dijkstra's algorithm that handles multiple connected components. First, we run Dijkstra's algorithm to compute initial distances. Then, we optimize these distances by considering all subsets of each node using a technique called Sum Over Subsets (SOS) dynamic programming. Finally, we run Dijkstra's algorithm again to update the shortest paths based on the optimized distances.

Implementation

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

class ShortestPathFinder {
private:
    using Edge = pair<long long, long long>;
    vector<long long> distances;
    vector<vector<Edge>> adjacency_list;

public:
    ShortestPathFinder() {}
    
    ShortestPathFinder(int node_count) {
        distances.assign(node_count + 1, LLONG_MAX / 2);
        adjacency_list.resize(node_count + 1);
    }
    
    void add_edge(int from, int to, int weight) {
        adjacency_list[from].emplace_back(to, weight);
        adjacency_list[to].emplace_back(from, weight);
    }
    
    void compute_shortest_paths() {
        priority_queue<Edge> queue;
        
        for (int i = 1; i < distances.size(); i++) {
            if (distances[i] != LLONG_MAX / 2) {
                queue.push({-distances[i], i});
            }
        }
        
        while (!queue.empty()) {
            auto current = queue.top();
            queue.pop();
            
            int node = current.second;
            long long current_distance = -current.first;
            
            if (current_distance > distances[node]) continue;
            
            for (auto [neighbor, weight] : adjacency_list[node]) {
                if (distances[neighbor] > distances[node] + weight) {
                    distances[neighbor] = distances[node] + weight;
                    queue.push({-distances[neighbor], neighbor});
                }
            }
        }
    }
    
    vector<long long>& get_distances() {
        return distances;
    }
};

void solve() {
    int nodes, edges, base_cost;
    cin >> nodes >> edges >> base_cost;
    
    ShortestPathFinder path_finder(nodes);
    
    for (int i = 0; i < edges; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        path_finder.add_edge(u, v, w);
    }
    
    auto& dist = path_finder.get_distances();
    dist[1] = 0;
    path_finder.compute_shortest_paths();
    
    for (int i = 2; i <= nodes; i++) {
        // Consider direct connection from node 1
        dist[i] = min(dist[i], 1LL * base_cost * (1 | i));
        
        // Consider all subsets of i
        for (int subset = (i - 1) & i; subset; subset = (subset - 1) & i) {
            dist[i] = min(dist[i], dist[subset] + 1LL * i * base_cost);
        }
    }
    
    path_finder.compute_shortest_paths();
    
    for (int i = 2; i <= nodes; i++) {
        cout << dist[i] << (i == nodes ? "\n" : " ");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        solve();
    }
    
    return 0;
}

Perimeter Optimization

Problem ID: HDU - 7467

Approach

This problem involves finding the minimum perimeter of a bounding box that contains all moving points. The key observation is that the perimeter-time function is unimodal - it first decreases and then increases. This is because when points move in opposite directions, the perimeter initially decreases but eventually increases as they spread apart.

To find the minimum perimeter, we use ternary search on the time variable. For each time value, we calculate the positions of all points and compute the perimeter of the bounding box. The ternary search efficiently finds the minimum value of this unimodal function.

Implementation

#include <iostream>
#include <vector>
#include <tuple>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int num_points;
    cin >> num_points;
    
    vector<tuple<long long, long long, char>> points(num_points);
    
    for (auto& [x, y, direction] : points) {
        cin >> x >> y >> direction;
    }
    
    auto calculate_perimeter = [&](long long time) {
        long long min_x = LLONG_MAX / 2, max_x = LLONG_MIN / 2;
        long long min_y = LLONG_MAX / 2, max_y = LLONG_MIN / 2;
        
        for (auto [x, y, direction] : points) {
            switch (direction) {
                case 'E': x += time; break;
                case 'W': x -= time; break;
                case 'S': y -= time; break;
                case 'N': y += time; break;
            }
            
            min_x = min(min_x, x);
            max_x = max(max_x, x);
            min_y = min(min_y, y);
            max_y = max(max_y, y);
        }
        
        return 2 * ((max_x - min_x) + (max_y - min_y));
    };
    
    long long left = 0, right = 1e15;
    while (left < right) {
        long long mid1 = left + (right - left) / 3;
        long long mid2 = right - (right - left) / 3;
        
        long long perimeter1 = calculate_perimeter(mid1);
        long long perimeter2 = calculate_perimeter(mid2);
        
        if (perimeter2 > perimeter1) {
            right = mid2 - 1;
        } else {
            left = mid1 + 1;
        }
    }
    
    cout << calculate_perimeter(left) << "\n";
    
    return 0;
}

Group Formation Problem

Problem ID: HDU - 7468

Approach

This problem requires determining if we can form a "Group of Death" - a group of four players where the skill difference between any two players is at most D, and at least one player has a skill level of at least L. The solution involves condittional checks based on the value of the first player.

If the first player's skill is ≥ L, we consider the three smallest remaining players. If the first player's skill is < L, we consider the largest remaining player and the two smallest remaining players. If neither configuration satisfies the "Group of Death" conditions, then it's possible to form such a group.

Implementation

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

void solve() {
    int num_players, min_skill, max_diff;
    cin >> num_players >> min_skill >> max_diff;
    
    vector<int> skills(num_players + 1);
    for (int i = 1; i <= num_players; i++) {
        cin >> skills[i];
    }
    
    bool first_player_strong = skills[1] >= min_skill;
    
    // Sort all players except the first one
    sort(skills.begin() + 2, skills.end());
    
    if (first_player_strong) {
        // Check if the four smallest players form a Group of Death
        if (skills[4] >= min_skill || 
            (max({skills[1], skills[2], skills[3], skills[4]}) - 
             min({skills[1], skills[2], skills[3], skills[4]})) <= max_diff) {
            cout << "No\n";
            return;
        }
    } else {
        // Check if the first player with the two smallest and the largest forms a Group of Death
        if ((skills[num_players] >= min_skill && skills[3] >= min_skill) || 
            (max({skills[1], skills[2], skills[3], skills[num_players]}) - 
             min({skills[1], skills[2], skills[3], skills[num_players]})) <= max_diff) {
            cout << "No\n";
            return;
        }
    }
    
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        solve();
    }
    
    return 0;
}