Por lo general, puedo encontrar un enfoque de fuerza bruta muy rápidamente para resolver un problema, pero a menudo no son los mejores. ¿Cómo puedo encontrar el mejor algoritmo para un problema?

Answer 1

Nota: Esta respuesta está escrita con respecto a la programación competitiva y no en general.

Bueno, viene con práctica, pero intentaré explicar cómo lo pienso.

Preparación
Antes que nada, debe tener un repertorio de algoritmos estándar. Debe conocer la mayoría de los algoritmos estándar, su complejidad, trucos de implementación, etc. Además, practique MUCHOS problemas.

Busque pistas
Mire las restricciones, le dirá algo sobre la complejidad esperada de la solución. Tal vez si N = 10 ^ 6, no puede ser N ^ 2, por lo que es mejor tener al menos un método NlogN. Además, piense si el problema actual es similar a algo que hizo en el pasado. Si puede recordar un problema similar, entonces genial, tiene un “acceso directo” a la solución.

Sin embargo, al fallar todo eso, simplemente “fuerza bruta” a través de varias técnicas como dp, graph, codicioso, etc. y veo si puedo reducir el problema dado a una de estas técnicas estándar.

Si no puede resolver un problema en el concurso, búsquelo después del concurso y descubra en qué parte del proceso se equivocó. Por ejemplo, si constantemente no resuelve problemas de DP, entonces necesita practicar más problemas de DP.

Finalmente, tenga en cuenta que si puede codificar rápidamente una solución de fuerza bruta, codifique eso. Esto es útil especialmente en concursos más largos como el concurso largo de spoj o codechef (donde probablemente incluso puede enviar la solución de fuerza bruta y obtener algunos puntos debido a la puntuación parcial recién introducida). Esto te ayudará a asegurarte de que has entendido el problema correctamente y también tendrás algo para probar tus soluciones más adelante cuando vengas con un algoritmo mejor. Por supuesto, esta no es una buena estrategia para concursos cortos.

Buena lectura sobre este tema:
Cómo encontrar una solución
Planificación de un enfoque para un problema de TopCoder: Sección 1

Answer 2

En la programación competitiva no podemos resolver todos los problemas con una técnica … 🙂 Algunos problemas se pueden resolver mediante el uso de un enfoque de fuerza bruta simple y algunos necesitan una estructura de datos y algoritmos de alto nivel.

Para resolver problemas en concursos, debe practicar más sobre problemas anteriores y si no resuelve un problema, intente encontrar una solución para ese problema y comprenderlo completamente. Luego aplique la técnica aprendida en problemas relacionados.

Para que resuelvas más problemas durante los concursos.