Google Internship 2020 – Desafío en línea de Google (primera ronda de codificación)

Recientemente recibí un correo electrónico de Google informándome que fui seleccionado de la ronda de revisión de currículum para la ronda de desafío en línea de Google. El 29 de agosto me he dado ese reto y me enfrento a estos dos problemas, que quiero compartir con todos…

1. Una string especial: se le da una string S que consiste en el alfabeto latino en minúsculas, a – z. 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 siguiente condición es verdadera:

   S[i] > S[j]
   S[i] < S[j]
   S[i] = S[j]
   S[i]: Represents the ith character of string S(1-based indexing)

   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 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 ≤ N ≤ 103
   N is Even

   Ejemplo de entrada:

   1
   6
   aababc

   Salida de muestra:

   2

   Explicación:

   Change S[4] = ‘d’(1 – based indexing)
   Change S[5] = ‘d’
   New String  = ‘aabddc’
   Now all Pairs (S[i],S[j]) 
   Satisfy the second condition, S[i] < S[j].

2. Una array especial: se le da una array A de N × N. La array consta de números enteros positivos. En un solo movimiento, puede aplicar la siguiente transformación única a la array:

   Seleccione un elemento arbitrario de la array y auméntelo o disminúyalo en 1. Cada elemento puede aumentar o disminuir cualquier número arbitrario de veces.

   Un número especial P es un número entero no negativo para el cual la siguiente ecuación cuadrática tiene al menos una raíz entera negativa:

   X2 - 2 × P + x = 0

   Una array se llama especial si se cumple al menos una de las siguientes condiciones:

   1. La array tiene una fila con números especiales únicamente.
   2. La array tiene una columna con números especiales solamente.

   Su tarea es contar el número mínimo de movimientos requeridos para obtener la array especial A

   Formato de entrada

   • La primera línea contiene 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 el número de filas y columnas.
   • Las siguientes N líneas de cada caso de prueba contienen N enteros que denotan la array inicial A.

   Formato de salida

   Para cada caso de prueba, imprima un solo entero en una nueva línea que indique el número mínimo de movimientos necesarios para obtener una array especial de la array proporcionada. si ya obtuvo una array especial, imprima 0.

   Restricciones:

   1 ≤ T ≤ 10
   1 ≤ N ≤ 500  
   1 ≤ A[i][j] ≤ 1011(1 ≤ i ≤ N, 1 ≤ j ≤ N)

   Ejemplo de entrada:

   1
   3
   1 2 3
   4 5 6
   7 8 9

   Salida de muestra:

   1

   Explicación: Se puede modificar la primera fila o la tercera columna para convertir la array en una array especial con un número mínimo de movimientos. La primera fila se puede transformar en [1,3,3] aumentando una vez el segundo elemento de la primera fila.