Creo que no puede sobresalir en la programación competitiva sin tener una sólida formación en matemáticas, pero no haber recibido ninguna educación formal en matemáticas no es un problema cuando hay tantos recursos disponibles en la web.
¿Entero de 32 bits significa algo para ti? Quiero decir, ¿realmente entiendes la siguiente declaración?
La entrada es un número entero, N tal que 0
Si su respuesta es NO, aprenda sobre los diferentes sistemas numéricos y sus representaciones. La entrada podría ser tan grande que una variable entera de 64 bits (tipo de datos largo en Java) no podría mantener esa constante. Como eres un desarrollador de Java, creo que debes haber escuchado sobre la clase BigInteger. Aquellos que codifican en C / C ++ (como yo) generalmente tienen que diseñar un algoritmo para almacenar números tan grandes, usando una matriz para almacenar cada uno de ellos. dígitos
A veces pueden dar una constante, digamos CONST 10 ^ 10 + 7 y pedirle que imprima el resultado% CONST. Si intenta un enfoque ingenuo calculando primero el resultado y luego realizando la operación de módulo, es posible que obtenga WA o Respuesta incorrecta. La razón es que su resultado podría ser mayor que un entero de 64 bits. La propiedad distributiva del módulo podría ser útil en tales casos. Eso es matemática. Vea, debe intentar hacer algunas compensaciones entre la memoria y el tiempo para finalmente lograr que un AC tenga buenos problemas. Siento que no es una buena práctica usar BigInteger cada vez .
Debes haber escuchado acerca de la programación dinámica y, tal vez, de la memorización también.
“Uno que no recuerda su pasado está condenado a repetirlo
– Programación dinámica ”
Leí esta cita en una plataforma competitiva hace unos meses. Explica DP de una manera simple. Memoization es un término que describe una técnica de optimización en la que almacena en caché los resultados calculados previamente y devuelve el resultado en caché cuando se necesita el mismo cálculo nuevamente. El PD con la memorización es una técnica muy poderosa. Esto requerirá matemáticas. Los problemas PD también se resuelven haciendo tablas , y eso también generalmente involucra matemáticas.
Las estructuras de datos como Gráficos (y árboles) son simplemente matemáticas de nivel secundario / universitario. Los algoritmos son técnicas matemáticas. Hay algunas cosas llamadas “Análisis asintótico” que nuevamente requieren una buena comprensión de las funciones y gráficos. En realidad, puede estimar si su el código / algoritmo se ejecutará en las limitaciones de tiempo dadas o no, haciendo el análisis asintótico antes de enviar la solución.
Solo quería darte una idea de lo importante que son las matemáticas cuando se trata de CP. No es necesario ser matemático, pero no creo que haya un excelente programador competitivo que probablemente no sea bueno en matemáticas.
Te recomiendo que hagas este curso completo en MIT OpenCourseware:
Matemáticas para la informática
Lea las respuestas en este hilo: Matemáticas para informática
Puede encontrar útiles estos tutoriales de TopCoder: Tutoriales de ciencia de datos
Si es posible, siga esta guía:
Estudiantes – Guía para el desarrollo técnico – Google Careers
Tiene enlaces a algunos excelentes cursos en la web, puede ir específicamente a los cursos de matemáticas discretas.
Espero que esto ayude.