Dada una array A[] de tamaño N , la tarea de cada elemento de la array es contar los elementos de la array a su derecha que son más pequeños que él y son primos . Ejemplos: Entrada: N = 10, A[] = {5, 5, 17, 9, 12, 15, 11, 7, 39, 3} Salida: 2 … Continue reading «Cuente los números primos más pequeños a la derecha de cada elemento de la array»
Dada una array de tamaño N. Puede haber múltiples consultas de los siguientes tipos. actualizar (l, r) : en la actualización, voltea (multiplica a[i] por -1) el valor de a[i] donde l <= i <= r . En términos simples, cambie el signo de a[i] para el rango dado. consulta (l, r) : en la … Continue reading «Problema de señal de volteo | Árbol de segmentos de propagación diferida»
Dada una array de enteros, evalúe consultas de la forma LCM(l, r). Puede haber muchas consultas, por lo tanto, evalúe las consultas de manera eficiente. LCM (l, r) denotes the LCM of array elements that lie between the index l and r (inclusive of both indices) Mathematically, LCM(l, r) = LCM(arr[l], arr[l+1] , ……… , … Continue reading «Programa Python3 para consultas LCM de rango»
Un Trie se utiliza para almacenar palabras del diccionario para que se puedan buscar de manera eficiente y se pueda realizar una búsqueda de prefijos. La tarea es escribir una función para contar el número de palabras. Ejemplo : Input : root / \ \ t a b | | | h n y | … Continue reading «Contando el número de palabras en un Trie»
Requisito previo: Fenwick Tree Sabemos que para responder consultas de suma de rango en una array 1-D de manera eficiente, el árbol indexado binario (o Fenwick Tree) es la mejor opción (incluso mejor que el árbol de segmentos debido a que requiere menos memoria y es un poco más rápido que el árbol de segmentos). … Continue reading «Árbol indexado binario bidimensional o árbol Fenwick»
Dada una string , la tarea es construir una array de sufijos para la string dada. Una array de sufijos es una array ordenada de todos los sufijos de una string dada. La definición es similar a Suffix Tree , que se comprime de todos los sufijos del texto dado. Ejemplos: Entrada: str = “banana” … Continue reading «Array de sufijos | Conjunto 2 (algoritmo nLogn)»
Consideremos el siguiente enunciado del problema y pensemos en diferentes soluciones para él. Dado un conjunto S de elementos tales que los elementos se toman del universo {0, 1, …. u-1}, realice las siguientes operaciones de manera eficiente. insert(x) : Agrega un elemento x al conjunto+ S. isEmpty() : Devuelve verdadero si S está vacío, … Continue reading «proto de Emde Boas Árboles | Conjunto 1 (Antecedentes e Introducción)»
B-Tree : B-Tree se conoce como un árbol autoequilibrado ya que sus Nodes se ordenan en orden transversal. En B-tree, un Node puede tener más de dos hijos. B-tree tiene una altura de logM N (donde ‘M’ es el orden del árbol y N es el número de Nodes). Y la altura se ajusta automáticamente … Continue reading «Diferencia entre árbol B y árbol B+»
Prerrequisito: Problema del viajante de comercio , NP Difícil Dado un conjunto de ciudades y la distancia entre cada par de ciudades, el problema del vendedor ambulante encuentra el camino entre estas ciudades de modo que sea el camino más corto y atraviese cada ciudad una vez, regresando al punto de partida. Problema: dada una … Continue reading «Prueba de que el problema del viajante de comercio es NP Difícil»
Dado un número entero N y una array asientos[] donde N es el número de personas que hacen fila para comprar un boleto de cine y asiento[i] es el número de asientos vacíos en la i -ésima fila del cine. La tarea es encontrar la cantidad máxima que el propietario de un cine puede ganar … Continue reading «Encuentre la cantidad máxima que se puede recaudar vendiendo boletos de cine»