L a programación competitiva ( PC ) no suele requerir conocimientos de cálculo de alto nivel o ciencia espacial. Pero hay algunos conceptos y trucos que son suficientes la mayoría de las veces. Definitivamente puede comenzar a codificar competitivamente sin ningún conocimiento matemático. Pero las matemáticas se vuelven esenciales a medida que te sumerges profundamente en el mundo de CP. La mayoría de los problemas de codificación competitiva que encontrará tendrán algún truco o lógica matemática. Todos los algoritmos que aprendemos se derivan desde un punto de vista matemático. La mayoría de las veces, las matemáticas nos ayudan a resolver la pregunta dentro de las limitaciones de tiempo necesarias.
No se pueden cubrir todos los temas en un solo artículo, pero analizaremos algunos de los conceptos matemáticos más comunes en la codificación competitiva. Algunos de estos conceptos pueden parecer demasiado difíciles a primera vista, pero aplicarlos en los problemas los aliviará.
Una cosa más es que solo he mencionado las cosas que necesita cubrir y algunos trucos para hacerlo, pero puede obtener ayuda de los otros recursos en línea para aprenderlos y practicarlos.
1. BigInteger
Para, por ejemplo , calcular factoriales de números grandes (digamos 100) o tomar grandes números de entrada de alrededor de 100000 dígitos de longitud. En c ++, no es posible almacenar estos números incluso si usamos long long int. Una forma de tomar este tipo de número es, llevándolos a una array de manera más sabia, use el vector … cada número tendrá un índice de array, como si el número fuera 12345, entonces 12345% 10 = 5 estará en el índice [4] y el número ahora=12345/10=1234. ahora 1234%10=4 estará en [3] y así hasta 1%10=1 en [0], o también puede usar una string, es más fácil ya que la array de caracteres solo permite 1 byte para cada índice, por lo que no necesita esas operaciones de modulación para ajustar el número en el índice.
Java proporciona la clase Biginteger para manejar esto.
2. MCD ,LCM , Algoritmo Euclidiano, Algoritmo Euclidiano Extendido
Las definiciones de GCD y LCM son bien conocidas (y se enseñan en la escuela secundaria). Omitiré las definiciones. Además, como mcm(a, b) * mcd(a, b) = a*b, calcular MCD es equivalente a calcular MCM.
Ahora, ¿cómo calculamos el MCD de dos números?
Por supuesto, podemos encontrar los factores de los dos números y luego determinar el máximo común divisor. Sin embargo, a medida que los números aumentan (por ejemplo, 155566328819), la factorización se vuelve ineficaz.
Aquí es donde el algoritmo de Euclides viene a nuestro rescate. Este algoritmo utiliza el hecho fácil de probar mcd(a, b)=mcd(b, r), donde r es el resto cuando a se divide por b, o simplemente a%b.
C
int GCD(int A, int B)
{
if (B == 0)
return A;
else
return GCD(B, A % B);
}
Java
static int GCD(int A, int B)
{
if (B == 0)
return A;
else
return GCD(B, A % B);
}
// This code is contributed by susmitamittal1329.
Python3
def GCD(A, B): if (B == 0): return A else: return GCD(B, A % B) # This code is contributed by subham348.
C#
static int GCD(int A, int B)
{
if (B == 0)
return A;
else
return GCD(B, A % B);
}
// This code is contributed by subham348.
Javascript
function GCD(A, B)
{
if (B === 0)
return A;
else
return GCD(B, A % B);
}
// This code is contributed by subham348.
¿Podemos encontrar los números (x, y) tales que ux + vy = mcd(u, v)?. Existen infinitos pares: este es el Lema de Bezout. El algoritmo para generar tales pares se llama Algoritmo Euclidiano Extendido.
3. Tamiz de Eratóstenes y Tamiz segmentado
La generación rápida de números primos es muy importante en algunos problemas. Vayamos al grano e introduzcamos el Tamiz de Eratóstenes. Puedes usar la Criba de Eratóstenes para encontrar todos los números primos que son menores o iguales que un número N dado o para averiguar si un número es un número primo.
La idea básica detrás de la Criba de Eratóstenes es que en cada iteración se toma un número primo y se eliminan todos sus múltiplos. Una vez que se completa el proceso de eliminación, todos los números sin marcar que quedan son primos. Supongamos que queremos encontrar todos los primos entre 2 y 50. Iteramos de 2 a 50. Empezamos con 2. Como no está marcado, es un número primo. Ahora marca todos los números que son múltiplos de excepto 2. Ahora pasamos al número 3. No está marcado, por lo que es un número primo. Ahora marca todos los números que son múltiplos de 3, excepto 3. Ahora pasa al 4. Vemos que está marcado, ¡es un múltiplo de 2! Entonces 4 no es un número primo. Seguimos haciendo esto.
CPP
void sieve(int N)
{
bool isPrime[N + 1];
for (int i = 0; i& lt; = N; ++i) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= N; ++i) {
// Mark all the multiples of i as composite numbers
if (isPrime[i] == true) {
for (int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
}
Java
// Java program for above approach
import java.util.*;
class GFG
{
public static void sieve(int N)
{
boolean isPrime[] = new boolean[N + 1];
for (int i = 0; i <= N; ++i) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= N; ++i) {
// Mark all the multiples of i as composite numbers
if (isPrime[i] == true) {
for (int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
}
}
¿Qué sucede si el número es grande (por ejemplo, 10^16), en ese caso requerimos un tamiz segmentado?
La idea del tamiz segmentado es dividir el rango [0..n-1] en diferentes segmentos y calcular números primos en todos los segmentos uno por uno. Este algoritmo primero usa Simple Sieve para encontrar números primos menores o iguales a ?(n). A continuación se muestran los pasos utilizados en el tamiz segmentado.
1. Use Simple Sieve para encontrar todos los números primos hasta la raíz cuadrada de ‘n’ y almacene estos números primos en una array «primo[]». Almacene los primos encontrados en una array ‘prime[]’.
2. Necesitamos todos los primos en el rango [0..n-1]. Dividimos este rango en diferentes segmentos, de modo que el tamaño de cada segmento sea como máximo ?n
3. Haga lo siguiente para cada segmento [bajo..alto]
• Crear una marca de array [alto-bajo+1]. Aquí solo necesitamos el espacio O(x) donde x es el número de elementos en el rango dado.
• Repita todos los números primos encontrados en el paso 1. Para cada número primo, marque sus múltiplos en el rango dado [bajo…alto].
En Simple Sieve, necesitábamos un espacio O(n) que puede no ser factible para n grande. Aquí necesitamos el espacio O(?n) y procesamos rangos más pequeños a la vez
4. Aritmética de módulo, exponenciación de módulo y inversa
de módulo Cuando un número se divide por otro, la operación de módulo encuentra el resto. Se indica con el símbolo %.
Ejemplo
Suponga que tiene dos números 10 y 3. 10%3 es 1 porque cuando 10 se divide por 3, el resto es 1.
Propiedades
1. (a+b)%c = (a%c+b%c)% C
2. (a?b)%c = ((a%c)?(b%c))%c
3. (a?b)%c = ((a%c)?(b%c)+c) %c
4. (a/b)%c = ((a%c)?(b%c))%c
¿Cuándo se usan estas propiedades?
Suponga que a = 10^12, b = 10^12 y c = 10^9+7. Tienes que encontrar (a?b)%c. Cuando multiplica a con b, la respuesta es 10^24, lo que no se confirma con los tipos de datos enteros estándar. Por lo tanto, para evitar esto usamos las propiedades. (a?b)%c = ((a%c)?(b%c))%c
Exponenciación de módulo rápido
Calcular a^b en m modular en O(log b),
utiliza la expansión binaria de b, y es muy directo.
CPP
ll expo(ll a, ll b, ll m)
{
if (b == 0)
return 1;
ll p = expo(a, b / 2, m) % m;
p = (p * p) % m;
return (b % 2 == 0) ? p : (a * p) % m;
}
Ahora, hablemos de la inversa modular .
Usando el Algoritmo Euclidiano Extendido, podemos obtener el inverso de un módulo m.
CPP
// Returns modulo inverse of a with respect
// to m using extended Euclid Algorithm
// Assumption: a and m are coprimes, i.e.,
// gcd(a, m) = 1
int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process same as
// Euclid's algo
m = a % m, a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
x += m0;
return x;
}
El pequeño teorema de Fermat da a^(p-1)==a (mod p) si mcd(a, p)=1, donde p es un número primo. Por lo tanto, podemos calcular el inverso modular de a como a^(p-2), también mediante exponenciación rápida.
5. Teorema de Lucas
Podemos calcular nCr en módulo p (p es un primo) muy rápido usando el Teorema de Lucas. El teorema de Lucas básicamente sugiere que el valor de nCr se puede calcular multiplicando los resultados de n(i)Cr(i) donde n(i) y r(i) son dígitos individuales en la misma posición en representaciones base p de n y r respectivamente. Esto es muy eficiente cuando p es pequeño y n, r es enorme. Podemos precalcular los factoriales y el inverso de los factoriales módulo p usando el código anterior.
6. Teorema chino del resto<
Dos números (enteros positivos) a y b son primos relativos (primos entre sí), si no tienen factores primos comunes. Los números m1, m2, ….mr, son pares relativamente primos si dos números distintos en esa colección son relativamente primos. El teorema chino del resto dice que dado cualquier par de números primos m1, m2, ….mr, y cualquier número b1, b2, b3, ..br, siempre podemos encontrar un número M que deje los restos b1, b2, b3 , ..br cuando se divide por m1, m2, …mr respectivamente.
Resolvamos x == r (mod mi), donde mi son coprimos por pares.
(Si no son coprimos, divídalos en potencias primas, y si algunos son contradictorios, no hay soluciones).
7. Series y Secuencias
Solo necesita saber algunos conceptos básicos como:
• ¿Qué es una serie y converge a algún valor?
• Saber sobre series famosas como trigonométricas, hiperbólicas… etc.
• Cómo calcular el límite finito de series famosas como (series geométricas, series armónicas)
y básicamente lo mismo para las secuencias, solo necesitas saber lo básico.
(Truco: use el sitio OEIS )
A veces nos encontramos en una situación en la que varios problemas de codificación se pueden simplificar a una fórmula matemática, pero a menudo encontrar esa fórmula no es tan sencillo. Aquí viene, OEIS para el rescate. Podemos calcular los términos para los índices iniciales, es decir, n=0, 1, 2, 3, …….. y luego podemos usar OEIS para encontrar la expresión matemática.
8. Números catalanes
Los números catalanes son una secuencia de números naturales que ayuda a resolver muchos problemas de conteo. Los términos que comienzan con n=0 son: 1, 1, 2, 5, 14, 42, 132, 429, 1430… y así sucesivamente.
Las preguntas basadas en el número catalán pueden aparecer en muchos concursos de codificación. Por lo que siempre es un punto a favor conocer en profundidad el número catalán.
Los números catalanes encuentran amplias aplicaciones en la formación de soluciones cerradas a problemas de combinatoria. Algunos de los ejemplos son:
1. El número de árboles binarios de búsqueda que se pueden formar utilizando ‘n’ Nodes es el n-ésimo número catalán.
2. El número de formas en que un polígono convexo de n+2 lados se puede cortar en 2 o más triángulos uniendo 2 aristas cualesquiera es el n-ésimo número catalán.
3. La solución cerrada al número de paréntesis posibles que coinciden dados ‘n’ pares es el n-ésimo catalán.
9. Principio del
casillero El principio del casillero es una poderosa herramienta utilizada en las matemáticas combinatorias. Pero la idea es simple y puede explicarse mediante el siguiente problema peculiar. Imagina que hay que colocar 3 palomas en 2 casilleros. Se puede hacer? La respuesta es sí, pero hay una trampa. El problema es que no importa cómo se coloquen las palomas, uno de los casilleros debe contener más de una paloma.
La lógica se puede generalizar para números más grandes. El principio del casillero establece que si se colocan más de n palomas en n casilleros, algún casillero debe contener más de una paloma. Si bien el principio es evidente, sus implicaciones son asombrosas.
Por ejemplo, considere esta declaración «Si elige cinco números de los números enteros del 1 al 8, entonces dos de ellos deben sumar nueve».
Explicación: Cada número se puede emparejar con otro para sumar nueve. En total, hay cuatro de estos pares: los números 1 y 8, 2 y 7, 3 y 6 y, por último, 4 y 5. Cada uno de los cinco números pertenece a uno de esos cuatro pares. Por el principio del casillero, dos de los números deben ser del mismo par, que por construcción suma 9.
10. Principio de exclusión de inclusión El principio de exclusión de inclusión es un teorema de conteo muy básico y muchos problemas en varios concursos de programación se basan en él. una explicación formal del principio de exclusión de inclusión es la siguiente:
Considere A como una colección de objetos y |A| como el número de objetos en A y de manera similar para B, entonces la cardinalidad de la colección de objetos de ambos conjuntos A y B (cuando tanto A como B son disjuntos) se puede establecer como (para 2 conjuntos finitos):
|AUB| = |A| + |B|
Pero, ¿y si los conjuntos no son disjuntos?
Luego, debemos restar los objetos comunes contados dos veces mientras calculamos la cardinalidad de A y B y la nueva forma se convertirá en:
|AUB| = |A| + |B| – |A∩B|
Esta es la forma más básica del principio de inclusión-exclusión.
Pero lo que hay son más de 2 conjuntos, digamos n conjuntos.
Entonces se puede establecer como:
(Incluir=sumar, excluir=restar)
|A1 U A2 U A3 …..U AN| = (Incluir el conteo de cada conjunto, Excluir el conteo del conjunto por pares, Incluir el conteo de conjuntos de tripletes, excluir el conteo de conjuntos de cuatrillizos… hasta que se incluya la enésima tupla (si es impar) o se excluya (si es par))
, es decir, |A1 U A2 U A3 …..U AN| = (|A1| + |A2| + |A3| + |A4| … + |AN|) – ( |A1 ∩ A2| + |A1 ∩ A3| + |A1 ∩ A4|.. + todas las combinaciones) + ( |A1 ∩ A2 ∩ A3| … todas las combinaciones)………. y así.
Esta lista no es exhaustiva pero los conceptos te serán muy útiles en concursos en codeforces, codechef, etc. Así que coge tu bolígrafo, papel y portátil y empieza a practicar.
¡Feliz codificación!