Dragon Slayer Pathfinding with Binary Enumeration

Coordinate scaling converts decimal start/end points to integers for grid processing. Binary enumeration efficiently searches all possible wall removal combinations.

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

struct Barrier {
    int x_start, y_start, x_end, y_end;
};

const int DIR_X[] = {0, 2, 0, -2};
const int DIR_Y[] = {2, 0, -2, 0};

class DragonMap {
    int width, height, barrier_count;
    int start_x, start_y, target_x, target_y;
    vector<Barrier> barriers;
    vector<vector<bool>> visited;
    
    bool is_valid(int x, int y) {
        return x >= 0 && x < width && y >= 0 && y < height && !visited[x][y];
    }
    
    void explore_path(int x, int y, int active_walls) {
        visited[x][y] = true;
        
        for (int d = 0; d < 4; d++) {
            int nx = x + DIR_X[d];
            int ny = y + DIR_Y[d];
            int mid_x = x + DIR_X[d] / 2;
            int mid_y = y + DIR_Y[d] / 2;
            
            if (!is_valid(nx, ny)) continue;
            
            bool blocked = false;
            for (int i = 0; i < barrier_count; i++) {
                if (!(active_walls & (1 << i))) continue;
                Barrier b = barriers[i];
                
                if (b.x_start == b.x_end) {
                    if (mid_x == b.x_start && mid_y >= b.y_start && mid_y <= b.y_end) {
                        blocked = true;
                        break;
                    }
                } else {
                    if (mid_y == b.y_start && mid_x >= b.x_start && mid_x <= b.x_end) {
                        blocked = true;
                        break;
                    }
                }
            }
            
            if (!blocked) explore_path(nx, ny, active_walls);
        }
    }
    
public:
    int find_minimal_removals() {
        int min_remove = barrier_count;
        int total_combinations = 1 << barrier_count;
        
        for (int combo = 0; combo < total_combinations; combo++) {
            int removals = barrier_count - __builtin_popcount(combo);
            if (removals > min_remove) continue;
            
            visited.assign(width, vector<bool>(height, false));
            explore_path(start_x, start_y, combo);
            
            if (visited[target_x][target_y]) {
                min_remove = min(min_remove, removals);
            }
        }
        
        return min_remove;
    }
    
    void process_test_case() {
        cin >> width >> height >> barrier_count;
        cin >> start_x >> start_y >> target_x >> target_y;
        
        width *= 2; height *= 2;
        start_x = start_x * 2 + 1; start_y = start_y * 2 + 1;
        target_x = target_x * 2 + 1; target_y = target_y * 2 + 1;
        
        barriers.resize(barrier_count);
        for (int i = 0; i < barrier_count; i++) {
            cin >> barriers[i].x_start >> barriers[i].y_start 
                >> barriers[i].x_end >> barriers[i].y_end;
            barriers[i].x_start *= 2; barriers[i].x_end *= 2;
            barriers[i].y_start *= 2; barriers[i].y_end *= 2;
            
            if (barriers[i].x_start > barriers[i].x_end) 
                swap(barriers[i].x_start, barriers[i].x_end);
            if (barriers[i].y_start > barriers[i].y_end) 
                swap(barriers[i].y_start, barriers[i].y_end);
        }
        
        cout << find_minimal_removals() << endl;
    }
};

Backpack Optimizaton with XOR Maximization

Find maximum XOR value when exactly filling a backpack capacity. Bitset optimization handles state transitions efficiently.

Transition formula: [f_{i,j,k} = f_{i-1,j,k} \mid f_{i-1,j \oplus w_i,k \ll v_i}]

#include <bits/stdc++.h>
using namespace std;

const int MAX_BITS = 1024;
bitset<MAX_BITS> dp[MAX_BITS], temp[MAX_BITS];

int backpack_xor(int n, int capacity, vector<pair<int, int>>& items) {
    dp[0][0] = 1;
    
    for (auto& item : items) {
        int value = item.first, weight = item.second;
        
        for (int j = 0; j < MAX_BITS; j++) {
            temp[j] = dp[j];
            temp[j] <<= value;
        }
        
        for (int j = 0; j < MAX_BITS; j++) {
            dp[j] |= temp[j ^ weight];
        }
    }
    
    int result = -1;
    for (int j = 0; j < MAX_BITS; j++) {
        if (dp[j][capacity]) {
            result = j;
        }
    }
    
    for (int i = 0; i < MAX_BITS; i++) {
        dp[i].reset();
        temp[i].reset();
    }
    
    return result;
}

Median Distance Counting with Prime Constraints

Count triplets where median Manhattan distance is prime. Precompute primes and use bitset operations for efficient counting.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2000;
const int MAX_DIST = 200000;

struct Point { int x, y; };
struct Edge { int u, v, distance; };

bitset<MAX_N> adjacency[MAX_N];
bool is_prime[MAX_DIST + 1];

void sieve_primes(int n) {
    fill_n(is_prime, n + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * 2; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

long long count_prime_median_triplets(vector<Point>& points) {
    int n = points.size();
    vector<Edge> edges;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist = abs(points[i].x - points[j].x) + abs(points[i].y - points[j].y);
            edges.push_back({i, j, dist});
        }
    }
    
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.distance < b.distance;
    });
    
    for (int i = 0; i < n; i++) adjacency[i].reset();
    
    long long count = 0;
    for (auto& edge : edges) {
        int u = edge.u, v = edge.v, dist = edge.distance;
        
        if (is_prime[dist]) {
            count += (adjacency[u] ^ adjacency[v]).count();
        }
        
        adjacency[u][v] = adjacency[v][u] = true;
    }
    
    return count;
}

Special Edge Pathfinding with Teleportation

Dijkstra with layered graph handles special edges that enable teleportation to non-adjacent nodes with cost adjustment for adjacent nodes.

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct Edge {
    int target, weight, is_special;
};

struct Node {
    int vertex, type;
    long long distance;
    bool operator<(const Node& other) const {
        return distance > other.distance;
    }
};

vector<long long> layered_dijkstra(int n, int start, int discount, vector<vector<Edge>>& graph) {
    vector<vector<long long>> dist(2, vector<long long>(n + 1, INF));
    vector<vector<bool>> visited(2, vector<bool>(n + 1, false));
    vector<int> last_visit(n + 1, 0);
    
    set<int> unvisited;
    for (int i = 1; i <= n; i++) {
        if (i != start) unvisited.insert(i);
    }
    
    priority_queue<Node> pq;
    dist[0][start] = 0;
    pq.push({start, 0, 0});
    
    int visit_count = 0;
    
    while (!pq.empty()) {
        Node current = pq.top(); pq.pop();
        int u = current.vertex, type = current.type;
        
        if (visited[type][u]) continue;
        visited[type][u] = true;
        
        if (type == 0) {
            unvisited.erase(u);
        } else {
            visit_count++;
            for (auto& edge : graph[u]) {
                last_visit[edge.target] = visit_count;
            }
            
            vector<int> teleport_nodes;
            for (int node : unvisited) {
                if (last_visit[node] != visit_count) {
                    teleport_nodes.push_back(node);
                    dist[0][node] = dist[1][u];
                    pq.push({node, 0, dist[0][node]});
                }
            }
            
            for (int node : teleport_nodes) {
                unvisited.erase(node);
            }
        }
        
        long long cost_adjust = type ? -discount : 0;
        
        for (auto& edge : graph[u]) {
            int v = edge.target, w = edge.weight, special = edge.is_special;
            long long new_dist = dist[type][u] + w + cost_adjust;
            
            if (new_dist < dist[special][v]) {
                dist[special][v] = new_dist;
                pq.push({v, special, new_dist});
            }
        }
    }
    
    vector<long long> result(n + 1);
    for (int i = 1; i <= n; i++) {
        result[i] = min(dist[0][i], dist[1][i]);
        if (result[i] == INF) result[i] = -1;
    }
    
    return result;
}

Laser Coverage Validation

Check if all points can be covered by laser beams in horizontal, vertical, or diagonal directions from a single weapon placement.

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

bool is_covered(int dx, int dy) {
    return dx == 0 || dy == 0 || dx == dy || dx == -dy;
}

bool check_coverage(int weapon_x, int weapon_y, const vector<pair<int, int>>& points) {
    for (auto& point : points) {
        int dx = weapon_x - point.first;
        int dy = weapon_y - point.second;
        if (!is_covered(dx, dy)) return false;
    }
    return true;
}

bool can_cover_all_points(vector<pair<int, int>>& points) {
    int n = points.size();
    
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        x[i] = points[i].first;
        y[i] = points[i].second;
    }
    
    for (int i = 1; i < n; i++) {
        if (x[i] == x[0]) continue;
        
        if (check_coverage(x[0], y[i], points)) return true;
        if (check_coverage(x[0], y[i] + (x[i] - x[0]), points)) return true;
        if (check_coverage(x[0], y[i] - (x[i] - x[0]), points)) return true;
        break;
    }
    
    return false;
}

bool solve_laser_problem(vector<pair<int, int>>& points) {
    if (can_cover_all_points(points)) return true;
    
    for (auto& point : points) swap(point.first, point.second);
    if (can_cover_all_points(points)) return true;
    
    for (auto& point : points) {
        int a = point.first, b = point.second;
        point.first = a + b;
        point.second = a - b;
    }
    if (can_cover_all_points(points)) return true;
    
    for (auto& point : points) {
        int a = point.first, b = point.second;
        point.first = a - b;
        point.second = a + b;
    }
    return can_cover_all_points(points);
}

Modular Probability Caclulation

Compute (n - m) / 2 mod 10^9+7 using modular inverse of 2.

#include <iostream>
using namespace std;

const int MOD = 1000000007;
const int INV_2 = 500000004; // 2^{-1} mod MOD

int compute_probability(int n, int m) {
    return (1LL * (n - m) * INV_2) % MOD;
}

Alice and Bob Game Theory

Game dteermined by whether the cumulative sum of a[i]/2^i exceeds zero.

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

string determine_winner(vector<int>& counts) {
    int n = counts.size() - 1;
    for (int i = n; i > 0; i--) {
        counts[i - 1] += counts[i] / 2;
    }
    return counts[0] > 0 ? "Alice" : "Bob";
}