Mensajes

Yo participé ayer y si no me he equivocado en mis soluciones estoy clasificado, puesto que aún no han salido los resultados oficiales.

Me dio bastante rabia participar puesto que ya lo hice en la que les petó el sistema y me había clasificado, pero qué se le va hacer...

¿Tú o alguien más ha participado?

Yo también estoy interesado. Participé en su día en la OIE y ahora con la universidad participo en el SWERC.

Para el segundo ayer descubrí que la solución cuadrática que había implementado sí era correcta, tan sólo tenía un pequeño bug que ya he corregido en el código. La idea era empezar por abajo y propagar hacia arriba.

Respecto al tercero, también me comentó un amigo ayer que aunque ordenar las palabras a saco y concatenar no era correcto (puede fallar cuando una palabra es prefijo de otra), sí que se puede hacer usando como función de comparación la siguiente:

Código (cpp) [Seleccionar] Expandir

bool cmp(const string &a, const string &b){
    return (a+b) < (b+a);
}

Sobre la competición, es cierto que han tenido bastantes fallos. Yo para estar al día iba mirando en los foros de Topcoder, donde un par de empleados de Facebook iban contestando a las dudas de la gente, puesto que en la página del concurso no decían nada.

Gracias, a ver hasta donde se puede llegar

Para los que han participado, me gustaría saber si alguien ha hecho alguna solución cuadrática para el segundo problema. Estuve pensando un rato pero no se me ocurrió ninguna y programé la dinámica cúbica estándar, que era igualmente instantánea con la entrada que se daba.

Por si a alguien le sirve, comento un poco mis soluciones.

Problema 1: Simplemente precalculo los cuadrados de todos los números hasta 50000 (cuyo cuadrado es sobradamente mayor que el máximo que te dan ellos) y los guardo en un AVL. Una vez hecho esto, con cada número de la entrada itero hasta su raíz y miro si la diferencia entre el número y el iterador al cuadrado está en mi AVL, incrementando en uno el contador en dicho caso. Por lo tanto, la complejidad para cada caso es de O(sqrt(x)*log(50000)), es decir, iterar*(coste de buscar en el AVL).

Problema 2: La idea es dada una posición de inicio, saber con qué probabilidad llega al objetivo. Para esto hago una dinámica cuadrática sobre la matriz del juego y en cada posición guardo la probablidad de llegar a dicha casilla. Por lo tanto, inicializo la primera fila todo a 0 excepto la de inicio, que le pongo 1. El resto de la matriz se inicializa también toda a cero. Una vez hecho esto, voy iterando fila a fila. Si en una posición tengo probabilidad mayor que cero, la propago a la fila inferior siguiendo las normas del enunciado. Tras hacer esto, en la casilla destino tengo la probabilidad buscada. Teniendo hecha esta dinámica en función de la casilla inicial, basta iterar sobre todas las posibles (tantas como columnas haya - 1). Así, acaba quedado una complejidad de O(filas*columnas^2), es decir, cúbica.

Problema 3: Aunque después vi que un backtracking a saco entraba, por si acaso programé una solución algo más rápida. Suponiendo que comparar las strings es constante (algo no muy descabellado puesto que tenían como mucho 10 carácteres), si había n strings el backtracking tiene coste O(n!), es decir, todas las posibles permutaciones. Mi solución, usando programación dinámica tiene complejidad O(n*2^n). La idea es hacer que el estado sea una máscara que indica qué strings he utilizado hasta el momento y que devuelva la menor string lexicográficamente que se puede obtener con las strings restantes. Así, tan sólo hace falta iterar sobre la máscara y probar a poner las strings que no están usadas.

Yo también he pasado de ronda. He hecho los tres problemas correctamente.

La distribución que comentas es la geométrica. Esta distribución contempla el caso en el que tenemos una sucesión de repeticiones independientes de una experiencia aleatoria con una cierta probabilidad de acierto p en que se para al primer acierto. Entonces la probabilidad de acierto a la (k + 1)-ésima vez es p*(1 - p)^k, es decir, fallo las k primeras y acierto después, por lo que sale esa probabilidad por el principio de multiplicación.

Pese a esto, yo lo veo más bien como una binomial, que lo que supone es que hacemos n repeticiones de forma independiente de una experiencia aleatoria con dos únicos resultados posibles (acierto o fallo) y se busca la probabilidad de acertar k veces. En este caso, n sería el número de trozos cogidos y la probabilidad de acierto, según el modelo que hemos cogido, sería 1/2. La función genérica de la binomial es P[X = k] = (n sobre k)*p^k(1 - p)^{n - k}, es decir, se consideran los posibles subconjuntos con k elementos y se multiplica por las respectivas probabilidades de acierto y fallo.

Me he estado mirando lo de Wikipedia y en efecto es eso, sólo que la información que tiene es más bien escasa, puesto que la clasificación se suele profundizar un poco más habitualmente.

La cónica ax² + bxy + cy² + dx + ey + f = 0, habitualmente se suele poner matricialmente de la forma (X 1)A(X 1)^T, donde

Código [Seleccionar] Expandir

X = (x y)
    (a      b/2     d/2 )
A = (b/2    c       e/2 )
    (d/2    e/2     f   )


Si llamamos B a la submatriz cuadrada que consta de las dos primeras filas y columnas de A y calculamos sus respectivos polinomios característicos, es decir,
det(B - x*Id) = x² - d₁x + d₂
det(A - x*Id) = -x³ + D₁x² - D₂x + D₃

Entonces se cumple:

- Si D₃ != 0:
       * Si d₂ = 0 es una parábola
       * Si d₂ < 0 es una hipérbola (hipérbola equilátera si d₁ = 0)
       * Si d₂ > 0 es una elipse:
                - Si D₃d₁ < 0 es real (es una circunferencia si d₁² = 4d₂)
                - Si D₃d₁ > 0 es imaginaria
- Si D₃ = 0 (cónica degenerada):
       * Si d₂ > 0 es un par de rectas imaginarias
       * Si d₂ < 0 es un par de rectas reales
       * Si d₂ = 0:
                - Si D₂ < 0 es un par de rectas paralelas reales
                - Si D₂ > 0 es un par de rectas paralelas imaginarias
                - Si D₂ = 0 es un par de rectas coincidentes

Donde queda incluida la clasificación de Wikipedia.

El caso es que parece que mezcla conceptos diferentes. Por el post se entiende que se refiere a la ecuación de segundo grado de toda la vida, que sin contar los casos degenerados siempre es una parábola como bien se ha dicho.

Sin embargo, por lo que dice sobre decir si es una parábola, hipérbola o elipse, me hace pensar que quizá lo que quiera hacer sea clasificar una cónica según sus invariantes métricos, cuyas ecuaciones también son funciones cuadráticas, sólo que de dos variables.

Básicamente, te piden que dada una secuencia de números encuentres la longitud de la subsecuencia consecutiva creciente más larga y digas en qué posición empieza si no lo he entendido mal.

El problema es fácil, ya que además te permiten hacerlo cuadráticamente, dado que la longitud de la secuencia te dicen que como mucho será 1000.

Pongo una versión recursiva un poco más corta:

Código (python) [Seleccionar] Expandir

x=1000,500,100,50,10,5,1
c='MDCLXVI'
def f(n,p):
return n/x[p]*c[p]+f(n%x[p],p+1)if n else''
print f(input(),0)
Son 113 carácteres según wc.

Para lo de leer un número indefinido de números, una manera muy simple de hacerlo es ir leyendo hasta encontrar un EOF, es algo que se usa mucho en concursos de programación. Para hacerlo en C, puedes hacerlo de la siguiente manera:

Código (c) [Seleccionar] Expandir

#include <stdio.h>

const int INF = 1000000000;

int main() {
    int maxim = -INF, minim = INF, a;
    while (scanf("%d", &a) != EOF) {
        if (maxim < a) maxim = a;
        if (minim > a) minim = a;
    }
    printf("%d %d\n", maxim, minim);
}

Y si lo pruebas por teclado, puedes enviar un EOF haciendo Control+D en Linux y Control+Z en WIndows.