En especial, este es el problema que me dió una buena combinación de errores: Compile Error, Time Limit Exceeded, Runtime Error y Wrong Answer. Costó pero ahora al menos me dio WA. La mayoria de las otras corridas en el juez me daba TLE.
El problema es una variante del clásico Longest Common Subsequence Problem. La primer versión que intenté fué una recursiva usando Memoization en una matriz, y era muy lenta. La siguiente version era iterativa, usando una matriz y dos bucles anidados.
La matriz al principio la implementé como un vector de vector en C++, (vector<vector< int > >), pero el tiempo de acceso deja mucho que desear. Lo cambié a un vector
La segunda optimización fue eliminar todas las llamadas a todas las funciones, y usar variables locales temporales. Métodos y funciones como string::c_str(), string::length() y vector::size() compilando con gcc sin optimización de código suelen ser muy lentas.
El resultado: ¡de 30 segundos de ejecución pasé a tener 18, y de tener un TLE pasé a tener WA!
En el caso de la versión recursiva, intenté hacer un test usando el mismo juego de datos para ver cuánto tardaba, pero lo corté a los 7 minutos.
Probé con una version mas chica de datos de prueba y, donde la versión recursiva tarda 40 segundos, la interativa con todas las optimizaciones anteriores tarda 0.5 segundos.
En ningún caso estoy usando la opción -O (de optimizaciones de compilación) de gcc, ya que no tengo muy en claro si el juez la usa o no. De usarla, la versión iterativa en vez de tardar 18 segundos, tarda 8.
