GOCC15: Desafío en línea de Google para pasantías (India)

Me enteré de la oportunidad a través del sitio web de Google https://careers.google.com/jobs/results/. Solicité lo mismo con mi currículum. Después de dos semanas, recibí una invitación por correo electrónico para participar en la ronda de codificación. El correo tenía una identificación única y obtuvo la clave de acceso (para iniciar sesión) el día de la ronda de codificación 1 (29 de agosto de 2020). El espacio estuvo abierto de 15:00 a 17:00 IST. 

Se realizó una ronda de codificación en la plataforma HackerEarth. La duración de la prueba fue de 60 minutos y constaba de dos preguntas de codificación, cada 30 puntos. Resolví parcialmente el segundo, la solución no fue suficiente para casos de prueba con grandes entradas.

Una string especial: se le da una string S que consta de letras latinas minúsculas az. Encuentre el número mínimo de caracteres que deben cambiarse para hacer que S sea especial. Se dice que una string S es especial si y solo si para todo (S[i], S[j] ) donde (1 ≤ I ≤ N/2) y (N/2 + 1 ≤ j ≤ N) uno de los siguientes condiciones es verdadera 

• S[i] > S[j]
• S[i] < S[j]
• S[i] = S[j]

S[i] representa el i-ésimo carácter de la string S (indexación basada en 1).

Formato de entrada:

• La primera línea contiene un número entero T que indica el número de casos de prueba.
• La primera línea de cada caso de prueba contiene un número entero N que indica la longitud de S.
• La segunda línea de cada caso de prueba contiene una string S.

Formato de salida: imprime un número entero que indica el número mínimo de cambios requeridos para cada caso de prueba en una nueva línea.

Restricciones 

1 ≤ T ≤ 5

1 ≤ norte ≤ 10 ³ 

n es par

Ejemplo :

Input:  1
    6
    aababc 
Output: 2

Explicación: Cambiar S[4] = ‘d’ (indexación basada en 1) Cambiar S[5] = ‘d’ Nueva string = ‘aabddc’ Ahora todos los pares (S[i],S[j]) satisfacen la segunda condición, S[i] < S[j]

Secuencia de generación: se le dan dos strings A de longitud N y B de longitud M. Estas strings contienen alfabetos ingleses en minúsculas. También recibe un número entero K. Puede cambiar el carácter de x en la string A por cualquier otro carácter y . El costo de esta conversión es abs ( ASCII( x )- ASCII( y ) ). Encuentre el costo mínimo requerido para que la longitud de la subsecuencia común más larga (LCS) de A y B sea al menos K. 

Nota: 

• Se puede obtener una subsecuencia de una string eliminando cero o más caracteres en A.
• La subsecuencia común más larga de dos strings de A y B es una subsecuencia de A y B y tiene la longitud máxima entre todas las strings que son una subsecuencia de A y B que serían subsecuencias múltiples para dos strings proporcionadas, por ejemplo, un LCS de vera y come es ea .

Formato de entrada:

• La primera línea contiene un número entero T que denota el número de casos de prueba para cada caso de prueba.
• La primera línea de cada caso de prueba contiene tres números enteros N, M y K separados por espacios.
• La siguiente línea de cada caso de prueba contiene una string A.
• La siguiente línea de cada caso de prueba contiene una string B.

Formato de salida: Para cada caso de prueba, imprima el costo mínimo requerido en una nueva línea.

Restricciones 

1 ≤ T ≤ 10

1 ≤ norte, metro ≤ 200

0 ≤ K ≤ min ( norte, metro )

Ejemplo:

Input:  2
    5 4 3
    abcba
    acyx
    3 3 3
    abc
    abc
Output: 22
    0