Problema 1: Segmentación de Cadenas y Optimización

El objetivo de este problema es procesar una cadena binaria y encontrar el valor mínimo entre la mitad del segmento más largo de unos consecutivos y el segundo segmento más largo. La estrategia implica recorrer la cadena para identificar y almacenar las longitudes de todos los bloques contiguos de unos, ordenarlos de forma descendente y aplicar la fórmula matemática requerida.

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string binary_str;
    if (!(std::cin >> binary_str)) return 0;
    
    int total_ones = 0;
    for (char c : binary_str) {
        if (c == '1') total_ones++;
    }
    
    if (total_ones <= 1) {
        std::cout << 0 << "\n";
        return 0;
    }
    
    std::vector<int> segments;
    int current_len = 0;
    for (char c : binary_str) {
        if (c == '1') {
            current_len++;
        } else {
            if (current_len > 0) segments.push_back(current_len);
            current_len = 0;
        }
    }
    if (current_len > 0) segments.push_back(current_len);
    
    std::sort(segments.rbegin(), segments.rend());
    
    int max_seg = segments[0] / 2;
    int second_max_seg = (segments.size() > 1) ? segments[1] : 0;
    
    std::cout << std::min(max_seg, second_max_seg) << "\n";
    return 0;
}

Problema 2: Estrategia Voraz con Agrupación

Para minimizar el costo de reducir un conjunto de números a cero, se emplea un enfoque voraz. Primero, se agrupan los valores idénticos y se ordenan de mayor a menor. Al procesar cada grupo, si hay múltiples instancias de un valor, se reduce el grupo a una sola instancia con un costo de 1. Posteriormente, el costo de transición hacia el siguiente valor inferior se calcula multiplicando la diferencia por la cantidad de elementos restantes, propagando el conteo al siguiente grupo.

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    if (!(std::cin >> n)) return 0;
    
    std::map<int, int, std::greater<int>> freq;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        freq[val]++;
    }
    
    std::vector<std::pair<int, int>> groups(freq.begin(), freq.end());
    long long total_cost = 0;
    
    for (size_t i = 0; i < groups.size(); ++i) {
        int current_val = groups[i].first;
        int count = groups[i].second;
        int next_val = (i + 1 < groups.size()) ? groups[i + 1].first : 0;
        
        if (count > 1) {
            total_cost += 1; 
            count = 1; 
        }
        
        total_cost += static_cast<long long>(current_val - next_val) * count;
        
        if (i + 1 < groups.size()) {
            groups[i + 1].second += count;
        }
    }
    
    std::cout << total_cost << "\n";
    return 0;
}

Problema 3: Modelado de Grafo y Búsqueda de Alcanzabilidad

Este problema se modela como un grafo dirigido donde las transiciones entre nodos dependen de restar y sumar valores específicos. El nodo de origen es n, y las aristas se construyen dinámicamente. Para encontrar el nodo alcanzable con el índice mínimo, se utiliza un algoritmo de Búsqueda en Anchura (BFS) que explora todos los caminos posibles desde el origen.

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    if (!(std::cin >> n >> m)) return 0;
    
    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int sub, add;
        std::cin >> sub >> add;
        for (int j = sub; j <= n; ++j) {
            int target = j - sub + add;
            if (target >= 0 && target <= n) {
                adj[j].push_back(target);
            }
        }
    }
    
    std::vector<bool> visited(n + 1, false);
    std::queue<int> q;
    q.push(n);
    visited[n] = true;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (int nxt : adj[curr]) {
            if (!visited[nxt]) {
                visited[nxt] = true;
                q.push(nxt);
            }
        }
    }
    
    for (int i = 0; i <= n; ++i) {
        if (visited[i]) {
            std::cout << i << "\n";
            return 0;
        }
    }
    
    return 0;
}

Problema 4: BFS Multi-fuente en Matrices con Podas

Se construye un grafo en una cuadrícula basándose en distancias de Chebyshev. El objetivo es encontrar el componente conectado más grande mediante un BFS multi-fuente. Para optimizar el tiempo de ejecución y evitar redundancias, se utiliza una matriz de visitados global. Si una celda ya fue explorada en un BFS anterior, se omite como punto de partida, ya que cualquier componente que la incluya ya fue evaluado, garantizando que el tamaño máximo no se vea afectado negativamente.

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

using namespace std;

struct Point { int x, y; };

int grid_size;
int grid[105][105];
bool globally_visited[105][105];
vector<Point> adj[105][105];

int bfs(int start_x, int start_y) {
    vector<vector<bool>> locally_visited(grid_size + 1, vector<bool>(grid_size + 1, false));
    queue<Point> q;
    
    q.push({start_x, start_y});
    locally_visited[start_x][start_y] = true;
    int component_size = 1;
    
    while (!q.empty()) {
        Point curr = q.front();
        q.pop();
        
        for (const auto& nxt : adj[curr.x][curr.y]) {
            if (!locally_visited[nxt.x][nxt.y]) {
                locally_visited[nxt.x][nxt.y] = true;
                component_size++;
                q.push(nxt);
            }
        }
    }
    
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            if (locally_visited[i][j]) {
                globally_visited[i][j] = true;
            }
        }
    }
    
    return component_size;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> grid_size)) return 0;
    
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            cin >> grid[i][j];
        }
    }
    
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            for (int x = 1; x <= grid_size; ++x) {
                for (int y = 1; y <= grid_size; ++y) {
                    if (i == x && j == y) continue;
                    int dist = max(abs(i - x), abs(j - y));
                    if (dist == grid[i][j]) {
                        adj[i][j].push_back({x, y});
                    }
                }
            }
        }
    }
    
    int max_size = 0;
    for (int i = 1; i <= grid_size; ++i) {
        for (int j = 1; j <= grid_size; ++j) {
            if (!globally_visited[i][j]) {
                max_size = max(max_size, bfs(i, j));
            }
        }
    }
    
    cout << max_size << "\n";
    return 0;
}

Problema 5: Componentes Conectados y Comparación de Fracciones

Este problema requiere identificar componentes conectados en una cuadrícula permitiendo movimientos en 8 direcciones. Para cada componente, se calcula la proporción de elementos especiales respecto al área total. Para evitar errores de precisión inherentes a los tipos de punto flotante, la comparación de fracciones se realiza mediante multiplicación cruzada de enteros, asegurando exactitud matemática durante el ordenamiento.

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

using namespace std;

struct Fraction {
    long long num, den;
    bool operator<(const Fraction& other) const {
        long long cross1 = num * other.den;
        long long cross2 = other.num * den;
        if (cross1 == cross2) return num < other.num;
        return cross1 < cross2;
    }
};

int n;
string board[505];
bool visited[505][505];
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

Fraction bfs(int r, int c) {
    long long area = 0, guards = 0;
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = true;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        area++;
        if (board[x][y] == '@') guards++;
        
        for (int i = 0; i < 8; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                if (board[nx][ny] != '#' && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
    return {guards, area};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) cin >> board[i];
    
    vector<Fraction> regions;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] != '#' && !visited[i][j]) {
                regions.push_back(bfs(i, j));
            }
        }
    }
    
    sort(regions.begin(), regions.end());
    
    cout << regions.size() << " " << regions[0].num << "\n";
    return 0;
}

Problema 6: Búsqueda Interactiva con Divide y Vencerás

En este problema interactivo, se debe encontrar la posición del valor máximo en un arreglo utilizando un límite estricto de consultas. Cada consulta devuelve la posición del segundo valor máximo en un subarreglo. La solución óptima consiste en encontrar primero la posición global del segundo máximo y, basándose en su ubicación (inicio, final o medio), aplicar búsqueda binaria en los intervalos resultantes para aislar la posición del máximo absoluto.

#include <iostream>

using namespace std;

int query(int l, int r) {
    cout << "? " << l << " " << r << endl;
    int res;
    cin >> res;
    return res;
}

void answer(int pos) {
    cout << "! " << pos << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    
    int second_max_pos = query(1, n);
    
    if (second_max_pos == 1) {
        int left = 1, right = n + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (query(1, mid) == second_max_pos) {
                right = mid;
            } else {
                left = mid;
            }
        }
        answer(right);
    } 
    else if (second_max_pos == n) {
        int left = 0, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (query(mid, n) == second_max_pos) {
                left = mid;
            } else {
                right = mid;
            }
        }
        answer(left);
    } 
    else {
        int check = query(1, second_max_pos);
        if (check == second_max_pos) {
            int left = 0, right = second_max_pos;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (query(mid, second_max_pos) == second_max_pos) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            answer(left);
        } else {
            int left = second_max_pos, right = n + 1;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (query(second_max_pos, mid) == second_max_pos) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            answer(right);
        }
    }
    
    return 0;
}