TOPCODER SRM 487

Posted: November 15, 2010 in TopCoder

El SRM 487 ah finalizado y hubo una gran cantidad de participantes peruanos, entre ellos de la UNI, UNSA, UNSACC, PUCP, UCSM. En cuanto a la división 1 el primer lugar lo obtuvo rng_58 y en la división 2 el ganador fue jevi. En cuanto a participaciones del Perú la mayoría pudo realizar el problema de 250 (Div 2), el problema de 500 (Div 2) fue el mismo que el 250 (Div 1) y pudieron resolverlo la mayoría que estaban en Div 1. A continuación procederemos a mostrarles algunas ideas para que puedan programarlas y resolver los problemas respecto a la division 2:

Problema de 250 Puntos

El problema es bastante sencillo, con decirnos que el conejo negro obtuvo 0 puntos nos indica que todas sus respuestas no son correctas entonces solo bastará verificar aquellas respuestas que sean diferentes del conejo negro, pero recuerda que para cada pregunta solo una respuesta del conejo blanco o plomo diferente que del negro puede se correcta. Si ambas son diferentes que del negro e iguales ambas cuentan.

El algoritmo es como sigue. Sea:

N=longitud de la cadena.                                                                                                                            G=respuesta a la pregunta i del conejo plomo.                                                                                           W=respuesta a la pregunta i del conejo blanco.                                                                                             B=respuesta a la pregunta i del  conejo negro.

Para todo i desde 0 hasta N.

Iteramos sobre N y hacemos las verificaciones:

Si G o W, alguno de ellos, es diferente de B entonces cualquiera de ellos es respuesta correcta.

Ahora si G es igual que W entonces se tiene que ambos tienen respuesta correcta por lo tanto incremente en  2 la suma total. De otro modo incremento en 1 la suma total

Problema de 500 Puntos – 250 Puntos (DIV I)

El enunciado puede que este un poco difícil de entender pero si se observa el ejemplo 0 claramente se sabrá de que trata el problema y que es lo que nos pide.

La solución mostrada continuación lo que hará será ir hallando el máximo para cada posible posición del conejo. Mejor explicare el algoritmo a través de las imagenes:

Sea:

N la longitud del arreglo ingreso.

k longitud de saltos del conejo.

i indice de la posición inicial del conejo.

j indice de la posición final luego que el conejo salto “k” unidades.

Como se puede ver en la imagen se sacan todas las posibles formas, pero solo necesitamos iterar desde i=0 hasta k.

A partir de esa posición “i” veo los posibles movimientos del conejo, para ello, Itero desde j igual i+k hasta N con “j” incrementando en “k” unidades, veamos las imágenes que muestran cada iteración.

Para  i = 0

Obtenemos máximo 8 eso aumentamos a nuestra respuesta total.

Para i = 1Para i = 2Respuesta total

Solución Alterna usando DP (Programación Dinámica).

Problema de 900 Puntos

La descripción del problema es entendible, dado lo siguiente:

Input:

N = el máximo valor que puede tener “y”.

Z = valor para operaciones en la ecuación.

Start = valor de inicial de “x”.

Goal = El valor de “y” cuando se cumple la condición de la ecuación.

De la descripción del problema:

Ecuación =  x + y^2 + z^3. Nos pide encontrar el número de pasos para llegar de un entero Start a un entero Goal.

Sabiendo que los valores posibles de “y” pueden estar entre 1 y N,  además un “y” será valido si cumple con que la ecuación antes descrita sea múltiplo de N  ( x + y^2 + z^3  %  N = 0 ), si no hay valor para “y” retornar -1. En cada iteración cada vez que se cumpla la condición el nuevo valor de “x” será el “y” que cumplió la condición.

Un ejemplo es como sigue:

Si tengo N = 5, Z = 1, Start = 5, Goal = 1

Valor de X será Start = 5.  Valores de Y = 1, 2, 3, 4 ,5

Para Y = 1:5

5 + 1*1 + 1*1*1 = 7,  3 no es múltiplo de 5.

5 + 2*2 + 1*1*1 = 10,  10 si es múltiplo de 5, en y = 2 tenemos un posible avance.

5 + 3*3 + 1*1*1 = 15, 10 si es múltiplo de 5, en y = 3 tenemos un posible avance.

5 + 4*4 + 1*1*1 = 22,  22 no es múltiplo de 5.

5 + 5*5 + 1*1*1 = 31,  31 no es múltiplo de 5.

Valores posibles son 2 y 3, los valores de “y” también son 2 y 3  y ninguno es igual a Goal por lo que tendré que probar con esos valores, entonces mi nuevo “x” será 2 y 3.

Para Y = 1:5, X = 2

2 + 1*1 + 1*1*1 = 4,  4 no es múltiplo de 5.

2 + 2*2 + 1*1*1 = 7,  7 no es múltiplo de 5.

2 + 3*3 + 1*1*1 = 12, 12 no es múltiplo de 5.

2 + 4*4 + 1*1*1 = 19,  19 no es múltiplo de 5.

2 + 5*5 + 1*1*1 = 28,  28 no es múltiplo de 5.

No llegamos a la solución con X=2, pero tenemos aún X=3.

Para Y = 1:5, X = 3

3 + 1*1 + 1*1*1 = 5,  5 es múltiplo de 5.

El valor de  “y” es 1, y es igual al valor de Goal, entonces hemos encontrado la respuesta en dos conversiones, X = 5, X = 3. Retornamos la respuesta

Solución

Básicamente nos pide encontrar un “y” que sea igual a “goal”. Hasta que se cumpla eso contar el número de pasos y retornarlo. La forma en que se resolvió el problema fue la siguiente:

Supongo que “y” siempre tendrá un resultado y ese resultado será “goal”, entonces a partir de ese resultado averiguaré cuales son los posibles valores de “x” y los guardare en un arreglo, recuerda que esos posibles valores de “x” han sido el valor previo de “y” que cumpla la ecuación como se vio en el ejemplo.

Para averiguar los valores posibles de “x” veo la ecuación:

Ecuación =  x + y^2 + z^3

Como supuse que “y” es “goal” la ecuación es múltiplo de N. Entonces se cumple que:

( x +  y^2 + z^3) % N = 0

Entonces si reemplazo en la ecuación se tendrá:

(x + goal^2 + z^3) % N = 0

Como en el input nos dan goal, z y N. Tomemos el ejemplo explicado anteriormente

Tengo N = 5, Z = 1, Start = 5, Goal = 1

(x + 1 * 1 + 1 * 1 * 1) % 5 = 0

(x + 2) % 5 = 0

Como deseo el menor numero de conversiones, tomo el menor valor para “x” que cumpla la condición y este entre 1 y N en ese caso será x=3

(3+ 2) % 5 = 0

Mi nuevo “goal” será 3, por que dijimos que “x” es un “y” anterior.

De lo anterior “x” puede ser hallado de la siguiente manera:

X = N – y^2 + z^3

Como los valores de efectuar potencia de 3, y potencia de 2 puede llegar a ocasionar desborde, y su valor puede exceder N lo cual no puede ser, aplicamos aritmética modular sobre la ecuación antes de hacer los calculos:

Recordemos la propiedad: ( A + B + C ) % N -> ( A % N + B % N + C % N ) % N

( x % N + ( y%N * y%N ) % N + (z % N * z %N * z % N ) % N ) % N = 0

La manera final de hallar “x” seria:

x = N – ( ( y%N * y%N)% N + (z%N * z%N * z%N) % N ) % N

Ahora seguimos tenemos nuevo goal = 3

(x + 3*3 + 1*1*1)% 5 = 0

(x + 9 + 1)%5 = 0

(x + 10)%5 = 0, x tiene q estar entre 1 y N

(5 + 10)%5 = 0, el x más cercano es 5 comprendido entre 1 y N.

Usando aritmética modular:

X = 5 – ( 3*3 % 5 + 1*1*1% 5)% 5

X = 5 – (9% 5 + 1 ) % 5

X = 5 – (4+1)%5

X = 5 – 0

X= 5

El nuevo “goal” es 5 y es igual a “start”, por lo tanto hemos llegado a la solución en 2 conversiones. Recomendable usar long long (C++), long (Java) en las operaciones. Una forma de programar la idea anterior es guardando en una array los posibles valores de “x” y luego apartir de “goal” ver si llego a “start” por medio del arreglo, si se tiene un ciclo (se vuelve a la posición visitada del arreglo) es -1.

Solución Alterna usando BFS (Breath First Search).

Cualquier aporte, duda o consulta pueden hacerlo en el foro -> http://codebreakerscorp.foroperu.org/srm-487-f5/

Si no sabes que es el topcoder y deseas participar ingresa aqui -> http://codebreakerscorp.foroperu.org/nuevos-usuarios-f37/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s