Puntos en los que centrarse al hacer Programación Competitiva

La programación competitiva es vital para el desarrollo de uno en el campo de la codificación. Este artículo discutirá algunos puntos básicos que uno debe tener en cuenta al competir.

• Haga una lista de funciones para realizar tareas que se encuentran con frecuencia en las preguntas y agréguelas a su código en forma de plantilla . Esto ahorra tiempo durante los concursos y ayuda a enviar rápidamente las soluciones. Algunas funciones valiosas que deben agregarse en la plantilla son las siguientes:
  • Función de potencia ( a ^N %M , donde a, b, N son números enteros y M es un número primo )
  • Impresión de factores primos
  • Impresión de números primos
  • Función para encontrar nCr usando mod
  • Función para calcular MCD .
• Concéntrese en las restricciones mientras piensa en un enfoque para resolver el problema. Según las restricciones, verifique si la solución ideada puede pasar por todos los casos de prueba calculando la complejidad de tiempo de su enfoque.
• Piense en la máscara de bits o la fuerza bruta solo si las restricciones son lo suficientemente pequeñas (digamos 2 ^N ) que no excedan el límite de tiempo. Por lo tanto, el enfoque debe implicar la verificación de todas las combinaciones posibles de resultados.
• Si hay una pregunta que involucre datos ordenados en forma de entrada, piense en un enfoque que utilice la búsqueda binaria .
• Si hay una pregunta relacionada con árboles , gráficos ( detección de ciclos y otros), desarrolle una mentalidad para pensar en un enfoque que gire en torno a la búsqueda primero en profundidad o la búsqueda primero en amplitud , que es el requisito básico para resolver ese tipo de problemas. 
• Teoría de números :
  • La suma de dos o más números primos impares siempre dará como resultado un número par ( Ej. 13 + 3 = 16, 19 + 5 = 24).
  • La conjetura de Goldbach es uno de los problemas no resueltos más conocidos en matemáticas (la teoría de números para ser más precisos). Nota: No está probado para números más grandes.
  • Hay varios otros conceptos en la teoría de números que se requieren comprender para hacerlo bien en CP.
• Si un estado depende del estado futuro, entonces no es posible resolver el problema con una solución codiciosa . Además, no se puede recurrir al enfoque ingenuo, ya que excederá el límite de tiempo. Por lo tanto, para todos estos problemas, siempre trate de acercarse con una solución  de Programación Dinámica .
  Es muy simple si uno puede escribir una solución recursiva simple que funcione en una complejidad exponencial. Almacene cada ruta visitada en la memoria que podría usarse más tarde para ir en la dirección de la solución, esto se llama memorización . Una vez aprendido el método de memorización, aprenda gradualmente el método de tabulación .
• Si hay una pregunta relacionada con los operadores bit a bit como XOR , OR y AND , puede cambiar la array por esas operaciones, entonces, a veces, el enfoque ingenuo funcionará, ya que habrá como máximo 64 números con diferentes MSB (2 ⁶⁴ ) . Pero en este enfoque, la tarea principal es identificar el caso base.
  Tomemos un ejemplo en el que se proporciona una array ordenada en orden creciente y la tarea es hacer que no aumente reemplazando dos elementos adyacentes con su Bitwise XOR de la cantidad mínima de dos veces.
  

  Entrada: arr[] = {2, 5, 6, 8}
  Salida: 1
  Explicación:
  Operación 1: Elija los elementos 2 y 5, y reemplácelos con 2⊕5 = 7.
  Ahora, la array será {7, 6 , 8} que no es creciente.
  Por lo tanto, el recuento de operaciones es 1.

  Enfoque: Esto también se puede resolver de manera ingenua, es decir, encuentre un subarreglo cuyo XOR sea menor que el elemento antes del punto inicial del subarreglo o sea menor que el elemento después del punto final del subarreglo.

  Pero, antes de manejar un caso base, es decir, si existen 3 elementos continuos donde MSB es el mismo ( por ejemplo, MSB de arr[i – 1] = arr[i] = arr[i + 1] ), entonces se obtiene el resultado reemplazándolo por arr[i] ⊕ arr[i + 1] . 

  Entonces, para un enfoque ingenuo en una array solo cuando N > 60 porque 2*(⌊log ₂ 10 ⁹ ⌋ + 1) = 60 . (Sea, a[i] <= 10 ⁹ ). Multiplica 2 porque ese es el único último caso posible. Si se multiplica por 3, seguramente habrá 3 elementos continuos con el mismo MSB (bit más significativo).

• El GCD de los elementos de la array también se puede expresar como:
  

  mcd(un ₁ , un ₂ , ⋯, un _{norte – 2} , un _{norte – 1} , un _norte ) = mcd(un ₁ , un ₂ – un ₁ , ⋯, un _{norte – 1} – un _{norte – 2} , un _norte – un _{norte – 1} )

  Prueba:

  mcd(a, b) = mcd(a, b – a)
  mcd(a, b, c) = mcd(a, mcd(b, c)) = mcd(mcd(a, b), c)
  Entonces, se puede generalizar como: 
  mcd(a ₁ , a ₂ , ⋯, a _n−1 , a _n ) = mcd(a ₁ , a ₂ , ⋯, a _n−2 , mcd(a _n−1 , a _n ))
                                                       = mcd(a ₁ , a ₂ , ⋯, a _n−2 , mcd(a _n−1 , a _n −a _n−1 ))
                                                       = mcd(a ₁ , a ₂ , ⋯, a_n−2 , a _n−1 , a _n −a _n−1 )
                                                       = mcd(a ₁ , a ₂ , ⋯, mcd(a _n−2 , a _n−1 ), a _n −a _n−1 )
                                                       = mcd(a ₁ , a ₂ , ⋯, mcd(a _n−2 , a _n−1 −a _n−2 ), a _n −a _n−1 ) 
                                                           …
                                                       = mcd(a ₁ , a₂ , ⋯, un _norte−2 , un _norte−1 −un _norte−2 , un _norte −un _norte−1 )

• Algunas de las propiedades del Operador Bitwise más utilizadas pueden ser:
  • un ⊕ segundo = un | segundo – un y segundo
  • a + b = a ⊕ b + 2*(a y b)
  • un + segundo = un | b + a & b

  Aquí ‘a’ y ‘b’ son números enteros, ⊕ significa XOR, & significa AND y | significa O.