Lea las restricciones y elija la complejidad

Cada problema indica límites para n y para los valores. Esas restricciones le indican discretamente qué complejidad espera quien diseñó el problema. 🔍

Antes de diseñar nada, busque el valor máximo de n en las restricciones. El tamaño de n determina si se necesita una solución cuadrática, lineal o logarítmica.

Cuando n es como máximo 20, incluso una fuerza bruta exponencial cabe en el límite. Los límites pequeños invitan a probar todas las combinaciones sin miedo.

Si n llega a unos cientos, una solución O(n^3) todavía pasa. Los bucles triples o una DP básica sobre pares son opciones válidas en este caso.

Para n = 5000 aproximadamente, aspire a O(n^2). Los bucles anidados sobre el array cuestan unos 2,5 × 10^7 pasos, lo que todavía cabe en el presupuesto.

Cuando n alcanza 10^5 o 10^6, necesita O(n log n) u O(n). La ordenación, las sumas prefijas y los dos punteros se convierten en sus herramientas habituales.

Si n es mil millones, ningún bucle sobre n puede funcionar. Debe usar O(log n) u O(1), mediante matemáticas o búsqueda binaria sobre la respuesta.

Las restricciones de los valores también importan. Los números grandes advierten de un posible desbordamiento en otros lenguajes y pueden sugerir el uso de aritmética modular.

Los problemas con varias pruebas suelen limitar la suma de n, no cada valor de n. Léalo con atención, porque cambia el tamaño que pueden tener sus bucles de forma segura.

Elija la complejidad objetivo a partir de n y, después, seleccione un algoritmo que la alcance. Dejar que n guíe el diseño es mejor que adivinar y reescribir más tarde.

Conserve esta tabla en la memoria. El mapa de restricciones a complejidad convierte una rápida mirada a los límites en un plan inmediato durante las competiciones.

Deje que n le indique la complejidad adecuada.

Ahora interpreta las restricciones como un objetivo: un n pequeño permite la fuerza bruta, 10^5 necesita n log n y 10^9 exige logaritmos o matemáticas. Deje que n elija el enfoque. 🗺️