Problema A: Palíndromos (Anagramas)

Límite de tiempo: 2 Seg Límite de memoria: 10 MB Envíos: 322 Resueltos: 59

Descripción del problema

Un palíndromo (anagrama) es una palabra formada por las mismas letras que otra, como eat y tea. Dada una lista de palabras, se deben encontrar todos los grupos de palíndromos.

Entrada

La entrada consta de dos líneas: la primera indica el número total de palabras. La segunda línea contiene las palabras separadas por espacios. Ambas líneas terminan con un espacio. Todas las palabras están en minúsculas para evitar ambigüedades.

Salida

Primero, se debe imprimir la cadena "wo yi yue du guan yu chao xi de shuo ming" (pinyin de la declaración de integridad). Luego, se imprime el número de grupos de palíndromos que contienen más de una palabra. Finalmente, para cada grupo, se imprime una sola palabra: aquella con el orden lexicográfico más pequeño dentro del grupo. Los grupos también deben imprimirse en orden lexicográfico creciente. No debe haber espacios al final de cada línea de salida.

Ejemplo de entrada

9
a ew vc tea oe eat zoo el le

Ejemplo de salida

wo yi yue du guan yu chao xi de shuo ming
2
eat
el

Pista

Utilice un método con complejidad O(n log n).

Solución

Para lograr la complejidad O(n log n), se puede usar una estructura de datos con inserción O(log n), como un mapa balanceado. La idea es usar la palabra con sus letras ordenadas como clave para agrupar los anagramas. Mientras se procesa cada palabra, se actualiza el representante del grupo (la palabra más pequeña lexicográficamente) y se cuenta su tamaño. Al final, se recopilan los representantes de los grupos con al menos dos palabras y se ordenan.

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

using namespace std;

int main() {
    int num_palabras;
    cin >> num_palabras;
    
    // La clave es la palabra con letras ordenadas.
    // El valor es un par: {representante_mas_pequeño, cuenta}
    map<string, pair<string, int>> grupos;
    int grupos_multiples = 0;
    string palabra;
    
    for (int i = 0; i < num_palabras; ++i) {
        cin >> palabra;
        string clave = palabra;
        sort(clave.begin(), clave.end());
        
        // Actualizar la cuenta
        grupos[clave].second++;
        
        // Actualizar el representante más pequeño
        if (grupos[clave].second == 1) {
            grupos[clave].first = palabra;
        } else {
            if (palabra < grupos[clave].first) {
                grupos[clave].first = palabra;
            }
            // Contar el grupo solo cuando pasa de 1 a 2 elementos
            if (grupos[clave].second == 2) {
                grupos_multiples++;
            }
        }
    }
    
    cout << "wo yi yue du guan yu chao xi de shuo ming" << endl;
    cout << grupos_multiples << endl;
    
    // Recolectar los representantes
    vector<string> representantes;
    representantes.reserve(grupos_multiples);
    for (const auto& par_grupo : grupos) {
        if (par_grupo.second.second >= 2) {
            representantes.push_back(par_grupo.second.first);
        }
    }
    
    // Ordenar los representantes lexicográficamente
    sort(representantes.begin(), representantes.end());
    
    for (const auto& rep : representantes) {
        cout << rep << endl;
    }
    
    return 0;
}

Problema B: Suma de Tres Números

Límite de tiempo: 1 Seg Límite de memoria: 2 MB Envíos: 113 Resueltos: 56

Descripción del problema

Dado un arreglo de enteros sin elementos repetidos y un valor objetivo, determine cuántos tripletes distintos (tres elementos diferentes del arreglo) suman exactamente el valor objetivo.

Entrada

La primera línea contiene la longitud del arreglo y el valor objetivo de la suma. La segunda línea contiene los elementos del arreglo, sin repetidos.

Salida

Primero, se debe imprimir la cadena "wo yi yue du guan yu chao xi de shuo ming". Luego, se imprime el número total de tripletes que cumplen la condición.

Ejemplo de entrada

6 3
8 0 -5 -2 6 -1

Ejemplo de salida

wo yi yue du guan yu chao xi de shuo ming
2

Pista

El problema es una versión simplificada del clásico "3Sum" (ver LeetCode 15). Al no haber elementos repetidos, se evita parte de la complejidad.

Solución

Se ordena el arreglo primero. Luego, se itera con un índice i para fijar el primer número. Para los dos números restantes, se usa un enfoque de dos pnuteros: uno izquierda que empieza después de i y otro derecha al final del arreglo. Si la suma de los tres es menor que el objetivo, se avanza izquierda; si es mayor, se retrocede derecha; si son iguales, se cuenta el triplete y se avanza izquierda (o derecha) para buscar otras combinaciones.

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

using namespace std;

int main() {
    int n, objetivo;
    cin >> n >> objetivo;
    
    vector<int> numeros(n);
    for (int i = 0; i < n; ++i) {
        cin >> numeros[i];
    }
    
    // Ordenar el arreglo es clave para el enfoque de dos punteros
    sort(numeros.begin(), numeros.end());
    
    int conteo_tripletes = 0;
    
    for (int i = 0; i < n - 2; ++i) {
        int izquierda = i + 1;
        int derecha = n - 1;
        
        while (izquierda < derecha) {
            int suma_actual = numeros[i] + numeros[izquierda] + numeros[derecha];
            
            if (suma_actual < objetivo) {
                ++izquierda; // Necesitamos una suma mayor
            } else if (suma_actual > objetivo) {
                --derecha; // Necesitamos una suma menor
            } else {
                // Encontramos un triplete
                ++conteo_tripletes;
                ++izquierda; // Seguir buscando otras combinaciones
                // (No es necesario decrementar derecha aquí porque no hay duplicados)
            }
        }
    }
    
    cout << "wo yi yue du guan yu chao xi de shuo ming" << endl;
    cout << conteo_tripletes << endl;
    
    return 0;
}