Las siguientes observaciones son claves para resolver el problema.
- Si
, entonces
%
. Así que el máximo residuo posible es
.
- Si
satisface la condición del enunciado, entonces hay
diferentes residuos, luego los residuos son un subconjunto de
elementos, de la colección
.
- El mínimo común múltiplo de
es mayor o igual al producto de los primos menores o iguales a
.
- El producto de los primos menores o iguales a
es mayor a
Veamos el caso donde no forma parte de los residuos. De 1, vemos que
%
%
%
.
Entonces es un común múltiplo de
.
Luego, de la observación 3 vemos que
Donde es el producto de los primos menores o iguales a
.
Pero
. Así que si
es un común múltiplo de
entonces
.
Ahora el caso donde sí forma parte de los residuos. Se sigue que existe
tal que
%
. Con la misma lógica, de 1, vemos qué
%
%
.
Con ayuda de , vemos que
. ¿Cuál es el orden de los residuos mayores a
?. Para esto, consideremos el mismo orden que usamos en el caso donde
no forma parte de los residuos.
El residuo que originalmente pertenecía a
tiene dos direcciones: ser el residuo de un numero mayor que
, o
es el residuo que queda descartado.
Sea el residuo que queda descartado, entonces
debe ser común múltiplo de
, y para esto,
Lo cual sería imposible si .
Ahora, si no descartamos los residuos de , entonces
lo cual sería de nuevo imposible.
Por lo tanto, y
.
De modo que, si , la respuesta es “No”. El problema ahora se limíta a
y
.
Para éste problema, podemos guardar todos los residuos de con los números menores o iguales a
en una estructura que nos maneje operaciones básicas de conjuntos, como un set. Usando el set, la respuesta es “Si”, si el tamaño del set después de añadir los residuos es
, y “No” en caso contrario.
Tratemos cada query de manera independientemente, y nos tomamos como los puntos dados en la query.
El problema es equivalente a encontrar un círculo con el menor radio posible, tal que todos los puntos de la query están dentro de él. La respuesta sería el radio
.
Él cuál es un problema equivalente a encontrar el menor radio tal que existe al menos un punto contenido en cada círculo con centro
y radio
.
Si dicho punto existe, entonces existe al menos un par de círculos que se intersecten en algun punto
. Por supuesto, la distancia de
a
es menor o igual a
.
Por lo tanto, la respuesta puede ser encontrada con una búsqueda binaria.
- Fíjamos el radio
, el cual mandamos a la búsqueda binaria.
- Enumeramos los
círculos.
- Encontramos y enumeramos las intersecciones para cada par de círculos.
- Para cada intersección, recorremos cada centro. Si hay un centro
que tiene una distancia menor o igual a
entonces el menor radio que buscamos sí es menor o igual a
.
El costo de cada chequeo en la búsqueda binaria es . Y la búsqueda binaria tiene un costo de aproximádamente
operaciones. Pero precalculando las soluciones, de 4, para todos los
puntos antes de contestar las preguntas, reducimos el costo del chequeo a
, lo cual ya es suficiente para resolver el problema.
Lo que buscamos, es la cantidad de subconjuntos tales que su es igual a
. Esta cantidad puede verse como la cantidad de subconjuntos totales, menos la cantidad de subconjuntos tales que su
es diferente de
. Ahora, esta cantidad puede verse como la cantidad de subconjuntos cuyo
tienen exactamente un bit prendido, más la cantidad de subconjuntos cuyo
tienen exactamente dos bits prendidos,
, más la cantidad de subconjuntos cuyo
tienen exactamente
bits prendidos (esto ya que
).
Para esto usaremos el principio de inclusión – exclusión. De modo que la cantidad que buscamos esta dada por
Donde nos dice cuantos subconjuntos tienen un ~and~ con al menos
bits prendidos.
Ahora, puede ser calculado con la ayuda de una SOS (Sum Over Subsets) DP.
Para esto, sea alguna máscara de bits en
, y definamos
como el ~and~ de algún subconjunto del arreglo, tal que
. Es decir,
es una submáscara de
. Entonces, DP[mask] nos dice cuántas diferentes
existen. (dos
se consideran diferentes, si las posiciones de los elementos en el arreglo que la componen no son todas iguales). Está DP puede calcularse de la siguiente manera.
- Los casos base los formamos añadiendo la cantidad de ocurrencias de
en el arreglo, a
.
- Fíjamos
, de izquierda a derecha.
- Para cada mask en
, tal que mask tiene el
-ésimo bit apagado (mas formalmente,
) se hace la transición DP[mask | (1 << bit)] += DP[mask].
De modo que , para cada
una máscara con al menos
bits prendidos.
Sean las posiciones de la cadena en donde hay un
.
Definimos cómo la posición donde yace la rana, y
como la cantidad de brincos que ha dado hasta el momento. Inicialmente,
y
. La respuesta puede encontrarse mediante siguiente algoritmo.
- Encontrar
tal que
y
- Hacemos
y
- Repetimos mientras
.
La respuesta final es . El algoritmo se puede implementar con complejidad lineal usando la técnica de two pointers (usando
y
como los pointers).
Rescatando la cantidad de ocurrencias para cada vocal (no hay que olvidarse de contar las mayúsculas) mientras recorremos la cadena, estamos listos para imprimir las tres respuestas. Las cuales son
(a) Tamaño de la cadena.
(b) Suma de las ocurrencias de cada vocal.
(c) Imprimir la cadena de derecha a izquierda.
Salvemos los dos vectores dados y
, y generemos un nuevo vector
. La solucion es imprimir
.