TOPCODER SRM 497

Posted: February 11, 2011 in TopCoder

El SRM 497 se llevo a cabo este 10 de febrero. En cuanto a la división 1 el primer lugar lo obtuvo Petr y por pocos puntos menos ACRush en segundo lugar y en la división 2 el ganador fue el nuevo participante HDU_Lost. 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 hubo participantes tanto en Div 1 como en Div 2 que pudieron resolverlo.

A continuación procederemos a mostrarles un detalle de las soluciones de la división 2. Se recomienda leer antes los enunciados para mejor entendimiento, las soluciones serán dadas en Java:

Problema de 250 Puntos

Input:

  • Arreglo o vector de enteros, que viene a ser el tamaño de los objetos, ( Java – int [ ] sizes, C++ – vector<int> sizes).
  • Una cadena con caracteres ‘A’ y ‘R’, si se tiene ‘A’ los objetos de ese tamaño son aceptados sino son rechazados. ( Java – String outcome, C++ – string outcome)

Output

Si se lee el enunciado quizás no este bastante claro pero lo que se pide es encontrar el valor de A y B que son el mínimo y máximo valor de la cadena que contiene ‘A’ consecutivos, si existe un ‘R’ en medio de esa cadena de ‘A’ entonces retornar un arreglo vació. De otro modo retornar el valor de A y B en un arreglo.

Ejemplos:

0)

sizes = {3, 4, 5, 6, 7}

outcome = “AAAAA”

En este caso se tiene puras ‘A’ por ello el mínimo y máximo será 3 y 7 entonces

Retorna: {3, 7 }

1)

sizes = {3, 4, 5, 6, 7}

outcome = “AARAA”

En este caso vemos que hay una ‘R’ en medio de lo que vendría hacer la cadena de ‘A’ consecutivas por ello

Retorna: { }

2)

sizes = {3, 4, 5, 6, 7}

outcome = “RAAAA”

En este caso la única ‘R’ se encuentra al inicio y no interviene en la cadena de ‘A’ consecutivas por lo que el mínimo y máximo es 4 y 7

Retorna: {4, 7}

Solución

Una forma es poner ambos sizes[ i ] con su respectivo outcome[ i ] en una vector y ordenarlo por sizes. De esta manera simplemente bastaria verificar si antes de una ‘R’ y después de una ‘R’ existen ‘A’ entonces se retornaría vació, de otro modo el mínimo y máximo.

Otra forma es sin necesidad de ordenar y esa el la que les mostraré, lo que se hace es hallar el valor mínimo y máximo para ‘A’ eso en una iteración. Luego en otra iteración si tengo un ‘R’ veo si esa en el rango de ese mínimo y máximo ( if( sizes[ i ] >= min && sizes[ i ]<= max) ) si se cumple retorno vacío, de otro modo retorno el arreglo con máximo y mínimo.

Adjunto mi código: Problema 250 – Filtering

Problema de 500 Puntos – 250 Puntos (DIV I)

Input:

  • Una cadena con caracteres ‘I’ y ‘D’ referenciando al incremento y decremento respectivamente. ( String signature- string signature )

Output:

  • La permutación menor lexicograficamente que cumpla con la cadena de ingreso dada.

Ejemplos:

0)

signature = “IIIII”

En este caso todos son incremento por lo que la permutación debe retornar

Retorna : { 1, 2 , 3 , 4 , 5 , 6 }

1)

signature = “DI”

En este caso tenemos un decremento y un incremento por lo que retorna.

Retorna: { 2 , 1 , 3 }

2)

signature = “DIDDID”

En este caso lo primero que tenemos es decremento por lo que tenemos { 2, 1 } luego un incremento por lo que tenemos { 1, 5 } luego 2 decrementos ello seria { 5 , 4 , 3}

Luego un incremento {3 , 7 } finalmente un decremento { 7, 6 }

Retorna: {2, 1, 5, 4, 3, 7, 6}

Solución

Para obtener la permutación lexicograficamente menor simplemente es ubicar la permutación usando los enteros desde 1 hasta n.

La forma en como realice el problema es primeramente asumir que mi respuesta estará compuesta de puro incremento ( ‘I’ ), ello me ayuda a solo verificar los decrementos ya que para incrementos cumple. Por lo que mi arreglo de respuestas tendrá valores por ejemplo para el último caso ejemplo:

signature = “DIDDID”

resp = { 1 , 2, 3 , 4 , 5, 6 , 7}

Ahora itero sobre signature si encuentro un decremento ‘D’, cuento cuantos decrementos consecutivos se tiene a partir del indice actual de signature:

while( j < signature.length() && signature.charAt( j ) == 'D' ) j++;

Una vez obtenido la cantidad de decrementos tengo que invertir esa subarreglo para que todos cumplan. Para ello si tengo por ejemplo un arreglo { 3 , 4 , 5 , 6} para invertirlo simplemente itero hasta la mitad y cambio el primero con el ultimo, el segundo con el penúltimo y así sucesivamente. Hay que tener en cuenta que ese subarreglo se encuentra en cualquier posición inicial en “i” ( i = indice actual de signature ) y terminando en “j” por lo que para ver el tamaño de ese subarreglo será: ( j – i + 1 ).

Finalmente como ya use los decrementos consecutivos actualizo i = j.

Para el ejemplo, en la primera iteración tengo un decremento ‘D’, j = 1, i = 0

  • Tamaño = j – i + 1 = 1- 0 +1 = 2
  • Subarreglo = { 1 , 2 }
  • Mitad y cambio = { 2 , 1}
  • resp = { 2 , 1 , 3 , 4 , 5 , 6 , 7} actualizo i = j = 1

Iteración 2: Incremento, no ocurre nada.

Iteración 3: Decremento, i = 2, se tiene 2 decrementos consecutivos, j = 4

  • Tamaño = j – i + 1 = 4 – 2  + 1 = 3
  • Subarreglo = { 3 , 4 , 5 }
  • Mitad y Cambio = { 5 , 4 , 3}
  • resp = { 2 , 1 , 5 , 4 , 3 , 6 , 7 } actualizo i = j = 4

Iteración 4: Incremento, no ocurre nada.

Iteración 5: Decremento, i = 5, j = 6

  • Tamaño = j – i + 1 = 6 – 5  + 1 = 2
  • Subarreglo = { 6 , 7 }
  • Mitad y Cambio = { 7, 6 }
  • resp = { 2 , 1 , 5 , 4 , 3 , 7 , 6 } actualizo i = j = 6

Entonces retorno la respuesta final = { 2 , 1 , 5 , 4 , 3 , 7 , 6 }

Adjunto mi código: Problema 500 – PermutationSignature

Problema de 1000 puntos

Input

  • Una cadena conteniendo caracteres ‘a’ – ‘z’ ( Java – String S, C++ – string s).

Output

  • El menor numero de cambios ( agregar, borrar o cambiar un carácter) para que la cadena S sea cuadrada ( Es cuadrada si es la concatenación de dos copias del mismo string ).

Ejemplos

0)

S = “abcdabgcd”

En este caso para que sea cuadrada basta con borrar la “g”, tendríamos “abcdabcd”

Retorna: 1

1)

S = “abcdeabce”

En este caso para tener el menor numero de pasos basta con insertar la “d” entre la “c” y “e”, teniendo “abcdeabcde”

Retorna: 1

2)

S = “abcdeabxde”

En este caso es necesario un cambio de la letra “x” por la letra “c”, teniendo “abcdeabcde”

Retorna: 1

Solución:

Este problema es bastante sencillo si se conoce el algoritmo de programación dinámica “Edit Distance”, más específicamente la distancia de Levenshtein. Ya que es simple aplicación sin modificación del algoritmo. El algoritmo recibe dos cadenas para realizar los pasos de agregar o borrar o cambiar caracteres. En este caso tendremos que iterar sobra la cadena S desde i hasta N ( longitud de S) e ir verificando el EditDistance de substrings de S(0,i) y S(i). Obteniendo el mínimo que es lo que nos pide.

Una explicación breve del algoritmo:

Dado el string inicial compuesto por los caracteres S1,S2,S3,….,Si y un string final compuesto por los caracteres  T1,T2,T3,….,Tj , defimos a D(i,j) al minimo número de operaciones necesarias para transformar S en T, tomando en cuenta hasta el caracter i de S y hasta el caracter j de T.

Dicho esto la formula recursiva seria:

Donde:

  • DC: Costo de la operación de eliminación de un caracter.
  • IC: Costo de la operación de inserción de un caracter.
  • SC: Costo de la operación de sustitución de un caracter.

Generalmente DC, IC, y SC toman el valor de 1.

EJEMPLO

Hallar el mínimo número de operaciones para convertir el string “kitten” en “sitting”. Utilizando la formula recursiva a modo de programación Dinámica llegariamos a construir  la siguiente tabla:

Para lo cual el minimo de operaciones seria 3, siendo estas:

  1. kitten → sitten (sustitución de ‘s’ por ‘k’)
  2. sitten → sittin (sustitución de ‘i’ por ‘e’)
  3. sittin → sitting (inserción de ‘g’ al final).

Adjunto mi código: Problema 1000 – MakeSquare

Jhosimar George Arias Figueroa

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