Descubriendo ADN

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

leo

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

Los biólogos han descubierto una extraña molécula de ADN, mejor descrita como una secuencia de N caracteres del conjunto ${A, B}$ ~{A, B}~. Una secuencia improbable de mutaciones ha dado como resultado una cadena de ADN que consiste únicamente en A. Los biólogos lo encontraron muy extraño, así que comenzaron a estudiar las mutaciones con mayor detalle.

Descubrieron dos tipos de mutaciones. Un tipo resulta en cambiar un solo carácter de la secuencia $(A → B)$ o $(B → A)$. El segundo tipo cambia un prefijo completo de la secuencia, reemplazando específicamente todos los caracteres de las posiciones de 1 a K (para algunos K entre 1 y N, inclusive) con el otro carácter (A con B, B con A).

Calcular el menor número posible de mutaciones que podrían convertir la molécula inicial a su estado final (conteniendo sólo caracteres A). Las mutaciones pueden ocurrir en cualquier orden.

ENTRADA

La primera línea de entrada contiene el número entero positivo $N (1 \le N \le 1 000 000)$ ~N (1 \le N \le 1 000 000)~, la longitud de la molécula. La segunda línea de entrada contiene una cadena con N caracteres, siendo cada carácter A o B. Esta cadena representa el estado inicial de la molécula.

SALIDA

La primera y única línea de salida debe contener el número mínimo de mutaciones requerido.

Entrada Ejemplo

4
ABBA

Salida Ejemplo

Entrada Ejemplo

BBABB

Salida Ejemplo

Entrada Ejemplo

12
AAABBBAAABBB

Salida Ejemplo

Comments

1

linkyless commented on June 19, 2022, 6:09 p.m.

El ejercicio se puede realizar sin uso de Programación Dinámica con complejidad algorítmica de O(N) en tiempo y memoria.

2

PedroPabloAB commented on May 24, 2021, 5:22 p.m.

y por qué puede salir std::bad_alloc?

-1

eblabrada commented on May 27, 2021, 10:00 p.m.

Quizás sea MLE

2

PedroPabloAB commented on May 24, 2021, 1:46 a.m.

Ah, muchas gracias por su ayuda. Aún no he logrado hacerlo bien, pero entendí su explicación.

2
PedroPabloAB commented on May 20, 2021, 11:15 p.m.
Saludos. Pueden revisar mi código?, con los casos de prueba funciona. Lo hice con una función recursiva que dada la longitud n de la cadena cad, sea i la posición actual, si cad[i] es diferente de 'A' (o sea, cad[i] =='B'), realizar dos cambios:

cambiar cad[i] de B a A, es lo mismo que "cad[i]='A';" y llamar a la función nuevamente pero con parámetro n-1

intercambiar cad[j] desde j=0 hasta j=i por el otro valor (por ejemplo, si cad[j] es 'A' cambiarlo por 'B' y viceversa) y luego llamar a la función con parámetro n-1 (f(n-1)).

Cada vez que llamo a la función me encargo de haber sacado una copia de la cadena actual y voy sumando en una variable el número de cambios realizados y cuando n==0, (f(0)), añado ese valor a un arreglo, finalmente doy como salida, al valor mínimo del arreglo. Está claro que consume mucha memoria, son muchas llamadas recursivas y las copias de las cadenas son varias. Es por eso, que les pregunto si pueden recomendarme alguna alternativa a esto, estoy seguro de que en mi código la respuesta a cada caso es correcta. Muchas gracias por su atención.

6
eblabrada commented on May 21, 2021, 2:47 p.m. ← edit 4 →
Te explico mi solución con DP. Definamos a $dp(i,inv)$ ~dp(i,inv)~ como la mínima cantidad de movimientos que necesitamos para que el prefijo hasta la posición $i$ ~i~ sea $AAA..AA$ ~AAA..AA~, $inv$ ~inv~ sólo va tomar dos valores $0$ ~0~ si estamos analizando la cadena original, y $1$ ~1~ si estamos analizando la cadena original invertida (o sea, todas las $A$ ~A~ se transforman en $B$ ~B~ y viceversa, por ejemplo, la cadena invertida de $ABBA$ ~ABBA~ es $BAAB$ ~BAAB~).

Podemos ver fácilmente que si no tenemos a ningún caracter en el prefijo entonces no es necesario hacer ningún movimiento por tanto: $\displaystyle dp(0,0) = 0, dp(0,1) = 0$

Si estamos evaluando la cadena original y el caracter que evaluamos es una $A$ ~A~ entonces no necesitamos hacer ningún movimiento extra, por lo que la cantidad de movimientos que tenemos que hacer para que el prefijo hasta $i$ ~i~ sea $AAA..AA$ ~AAA..AA~ es la misma cantidad de movimientos para que el prefijo $i-1$ ~i-1~ sea $AAA..A$ ~AAA..A~, por lo que en este caso $\displaystyle dp(i,0) = dp(i-1,0)$ $$\displaystyle dp(i,0) = dp(i-1,0)$$

Si estamos evaluando la cadena invertida y el caracter en la posición $i$ ~i~ de la cadena original es $A$ ~A~ significa que estamos evaluando el caracter $B$ ~B~ en la cadena invertida, entonces hay dos movimientos posibles: $(1)$ ~(1)~ cambiar un caracter, aquí la solución sería la misma cantidad de movimientos que teníamos para que el prefijo $i-1$ ~i-1~ sea $AAA..A$ ~AAA..A~ en la cadena invertida más el movimiento extra de cambiar la $B$ ~B~ por la $A$ ~A~; $(2)$ ~(2)~ invertir el prefijo donde la solución sería la misma cantidad de movimientos que teníamos en el prefijo $i-1$ ~i-1~ en la cadena original más el movimiento extra de invertir el prefijo $i$ ~i~, como queremos quedarnos con la mínima cantidad de movimientos nos quedaremos con el mínimo de estos dos casos: $\displaystyle dp(i,1) = min(dp(i-1,0),dp(i-1,1))+1$

Si estamos evaluando la cadena original y el caracter en la posición $i$ ~i~ es $B$ ~B~ hacemos un análisis similar al del caso $3$ ~3~ y nos queda que: $\displaystyle dp(i,0) = min(dp(i-1,0),dp(i-1,1))+1$

Si estamos evaluando la cadena invertida y el caracter en la posición $i$ ~i~ de la cadena original es $B$ ~B~ significa que en la cadena invertida estamos evaluando el caracter $A$ ~A~, realizando un análisis similar al del caso $2$ ~2~ nos queda que: $\displaystyle dp(i,1) = dp(i-1,1)$ $$\displaystyle dp(i,1) = dp(i-1,1)$$

La solución nos queda en $dp(N,0)$ ~dp(N,0)~. Esto tiene una complejidad $O(N)$ ~O(N)~ en tiempo y memoria. Se pueden hacer optimizaciones en memoria para que quede $O(1)$ ~O(1)~ pero no es necesario en este problema.