RPC 04

Fue un contest interesante, lo malo fue que había varios problemas con las entradas o enunciados de los problemas (ni modo a veces pasan ese tipo de cosas) al final nuestra obsesión en arreglar nuestros códigos para esos problemas que estaban mal (específicamente uno) terminó haciéndonos perder más tiempo y no hicimos más en contest ( pero es que en serio no parecía que nuestras soluciones podrían fallar hasta reimplementabamos las ideas :'( ). Esta vez competimos como "Addis y sus amigos" (yo soy Addis :P ).

Sin más que decir/opinar acá una editorial de los problemas (en el orden en que los resolvimos en contest, y post contest):

Problema D: Dividing hexadecimal numbers

Era el fácil del concurso, dado un número en hexadecimal (el número era un tanto grande) ver si es múltiplo de 17, la forma sencilla de resolver es usando BigInteger en java, java solo puede pasar el número hexadecimal a decimal y ver si es múltiplo de 17. 

Problema H: Hidden String

El problema decía dadas 2 cadenas ver si existe alguna subsecuencia en común de tamaño K, se puede usar algún algoritmo para hallar la longitud del "Longest common substring" entre estás 2 cadenas si este es >= k lógicamente existe un substring de tamaño K, caso contrario no.

Problema A: Advanced multiplications

El problema decía que tenías que sumar las tablas de multiplicar hasta N*N (e imprimir la respuesta modulo 10¹⁰) por ejemplo:

-Para 1: (1x1) = 1

-Para 2: (1x1)+(1x2)+(2x1)+(2x2)=9

-Para 3: (1x1)+(1x2)+(1x3)+(2x1)+(2x2)+(2x3)+(3x1)+(3x2)+(3x3)=36

-Para 4: (1x1)+....+(4x4) = 100 //ya me dio pereza poner todas las multiplicaciones

Como N es 10⁹ no se puede iterar para sacar esta sumatoria entonces...

Si se observa cuidadosamente se puede notar que son los números triángulares "( N * (N + 1) ) / 2" elevados al cuadrado -> ( ( N * (N + 1) ) / 2)²  

Notar que esto es un número muy grande, así que conviene hacerlo en java con BigInteger para no perder el tiempo.

Nota: un amigo me conto que a él le daba WA por imprimir los últimos 10 dígitos de la respuesta (eso decía el problema aparentemente) en realidad es modulo 10¹⁰ (afortunadamente no leí bien el problema o hubiera cometido el mismo error),

Problema E: Expected Characters

Voy a ser sincero cuando leí este problema no lo entendí, así que le pase el problema a  Gabriel y él lo resolvió, hoy una semana y un día después de eso sigo sin entender el problema, pero según me contó era fácil. :P

Acá Gabriel explica su solución: (que sigo sin entender)
Ya que el numero de consultas en el problema es 10⁶ y la longitud de la cadena es hasta 10⁶ entonces no podemos hacer fuerza bruta para
hallar todas las rotaciones, asi que vamos a responder cada consulta en O(1), en cada consulta se da i y j, para la i-esima rotación sabemos
que la cadena inicia en el caracter i-1 (de la cadena original), haciendo unas cuentas podemos saber cual es el j-esimo caracter de la rotación
i.e. Si nuestra cadena es "acmicpc" y queremos hacer la consulta i = 3, j = 3, solo decimos que la 3ra rotacion inicia en el 2do caracter de
"acmicpc" o sea la rotacion será  "micpcac" y el 3er caracter es "c" (caracteres indexados desde 1)

Problema C: Counting Strings

Este problema nos tiro el contest :'( estuvimos debugeando haciendo variantes, repitiendo el código, haciendo cambios absurdos, siempre nos daba RTE porque el límite por mala suerte estaba mal (alguien se preguntará porque no le pusimos un 0 más a nuestro vector... hicimos eso y nuestra pc se mando al diablo al testear) con decir que nuestro primer intento fue al minuto 94 y obtuvimos el AC al minuto 255 (porque alguien en la sala grito "maldita sea el límite esta mal era 10⁶ no 10⁵) y mandamos con 10⁶ aunque moría en nuestra PC :P , al final re evaluaron y dio desde el primer intento .-. fue triste y doloroso.  

El problema hablaba de cadenas binarias de tamaño N que debían tener K cambios por ejemplo: 1000001 tiene 2 cambios (esta cambiando de 1 a 0 en la posición 1 (0 index), y otra vez a 1 en la posición 6. 

Se tenía que imprimir cuantas cadenas binarias de tamaño N con K cambios existían modulo 10⁹+7. Claramente se trata de un problema de combinatoria, si tenemos cadenas binarias de tamaño N entonces tendremos N - 1 lugares donde podrían ocurrir los cambios, con esto el problema se reduce a calcular C(N-1,k)*2 el 2 sale de que nuestra cadena puede comenzar en 0, o puede comenzar en 1. Notar que el límite es grande (10⁵) así que se debe calcular la combinatoria mediante formula C(n,k)=n!/(k!*(n-k)!) no olvidar que como hay división se debe usar inverso modular (recordar que el inverso modular solo funciona cuando el modulo es primo como en este caso).

Problema L: Lines of subway

Se te daba un árbol que contenía cierta información en las aristas: la dificultad de poner esa conexión, y la longitud. Se quería calcular el costo de construir una ruta del nodo "u" al nodo "v" (muchos querys) el costo era la suma de todas las longitudes de los arcos entre "u" y "v" multiplicado por la dificultad más grande entre los arcos de "u" y "v".

Claramente se trata de un problema de LCA (lowest common ancestor), en el preproceso para armar el LCA (con un sparse table) podemos también calcular con programación dinámica cual es la arista más grande, respecto a las distancias se sabe que en un árbol: dist(u)+dist(v)-2*dist(lca(u,v)) (todas estás distancias con respecto al root de nuestro árbol) nos da la distancia entre "u" y "v" así que nuestra respuesta sería: arista máxima entre (u, lca(u,v) ) y (v,lca(u,v)  * dist(u)+dist(v)-2*dist(lca(u,v)) respondiendo cada query en O(lg(n)) y preprocesando en O(n*lg(n))

Problema G:  Getting cofee

El problema nos decía que hallemos la longitud de ir del nodo 1 al nodo N y luego volver del nodo N al nodo 1 (sin pasar dos veces por una misma arista) de manera óptima (menor distancia posible), una forma fácil de resolver este problema es aplicando flujos (max-flow min-cost) simplemente tiramos 2 Bellman-Ford (O Dijkstra o alguna otra cosa que halle caminos mínimos en un grafo con pesos), aplicando el proceso del MFmc (nota si usas Dijkstra mucho cuidado con los ciclos negativos).

Problema F: Factorial divisors

Dados dos números N y K (se garantiza que K es menor o igual a N) hallar cuántos divisores no comparten N! y K!

Los números factoriales son de la forma:
N! = 1*2*3*....(N-1)*N
A simple vista se puede ver que todos los divisores que tiene K! los tiene N! por lo cual nuestra respueta será divisores(N!)-divisores(K!) .
Ahora se puede expresar cualquier número como suma de sus factores primos:

Imagen vilmente copiada de wikipedia.

Además el número de divisores de un número esta dado por:                                                        

También saque la imagen de wikipedia. 

En condiciones normales podríamos usar está 2° formula para poder calcular la cantidad de divisores del número pero 10⁶! es inmensamente grande, por tanto hay que pensar un poco más:

Un número de la forma N! solo tendrá factores primos <= N ya que es producto de los números <= N, lo único que hay que saber ahora es cuantas veces usamos cada número, para esto trataremos de dividir el número N una y otra vez entre cada primo menor o igual a este, (sin importarnos si la división es entera o no, sólo nos quedaremos con las partes enteras 'floor' ) hasta que ya no se pueda dividir más, almacenando la suma de estás divisiones en alguna variable, luego haremos la misma formula para calcular divisores de un número pero en vez de usar los exponentes usaremos estás sumas, e.g (por si no se entendio nada de lo que escribí, o no queda muy claro):

N = 10

primos menores o iguales a 10: 2,3,5,7

10 / 2 = 5 , 5 / 2 = 2 , 2 / 2 = 1, 1 / 2 = 0  suma: 5+2+1 = 8

10 / 3 = 3 , 3 / 3 = 1, 1 / 3 = 0 suma: 3+1+0 = 4

10 / 5 = 2, 2 / 5 = 0  suma 2

10 / 7 = 1 , 1 / 7 = 0 suma 0

entonces el número de factores de 10! es:  (8+1)(4+1)(2+1)(1+1) = 270

Con esto ya podemos calcular nuestra respuesta. :) 

Nota: no olvidar los modulos.

Nota 2: si faltan 5 minutos de contest no debugees este. :'(

Problema J: Joining Points

A saber porque nadie del team leyó este en contest, era más sencillo que los que ya describí (a mi parecer claro esta).

Ni bien lees el problema te das cuenta que te esta pidiendo el minimum spanning tree y el segundo minimum spanning tree (MST).

Ahora calcular el MST se puede hacer con Kruskal o Prim (el que les parezca más bonito) 

Respecto al segundo MST se sabe (por alguna demostración que hizo alguien genial) que para hallar el 2° MST (redundancia) hay que quitar solo una arista del MST y agregar alguna otra que no estaba en el MST, entonces para esto la idea sería hacer (N-1) veces el algoritmo para hallar MST para excluir así cada una de las aristas del MST original, y quedarnos con el mínimo de todo este proceso, desgraciadamente eso implica hacer O(V*E) veces el algoritmo y  al ser N = 5000 el peor caso, con M=N*(N+1)/2 el algoritmo de seguro nos daría TLE. Entonces que hacemos:

Supongamos que tenemos un árbol cualquiera (con pesos) y tratamos de agregarle una arista (que conecta (u,v) ), que no estaba entonces nuestro árbol dejará de ser árbol y ahora tendrá un ciclo entre u y v, para que vuelva a ser árbol deberíamos quitarle una arista de ese ciclo.

Fotito:

La fotito explica lo que dije.

Entonces podemos apoyarnos en esto para resolver el 2° MST tratamos de agregar una arista (u,v) al MST, y a continuación "eliminamos" la arista más pesada de este ciclo, y calcular el nuevo MST con esto: posible2_MST= MST-arista_mas_pesada+nueva_arista.

Si se preguntan como hallas rápido esa arista leer la explicación del problema L (da flojera escribir de nuevo lo mismo). 

Complejidad final O(E*lg(E)+E*lg(N))

Nota: Por razones que no entiendo puede pasar que el 1° MST es igual al 2° MST  pese a que no guarda sentido con la descripción del problema.

Problema I: Inserting a Polynomio

Es un problema fácil, dada una matriz con una figura (1 representa parte de la figura, 0 un espacio en blanco) ver si hay alguna forma de insertar esta en una matriz más grande ( 1 representa que la casilla ya esta ocupada, 0 que no) puedes rotar, o invertir la figura, simplemente hay que implementar con mucho mucho cuidado. 

Nota: No se debe imprimir salto de línea como es normal o da Presentation error.

Problema B: Board game

Es un jueguito en el que tienes un círculo dividido en N partes, y una pelotita que parte de la casilla 1 y va avanzando 1,2,3,4,...N,1,2,3,... además tienes M bloques que puedes poner en un intervalo [t1,t2] si la pelotita choca con un bloque se detiene (se detiene en la casilla donde esta el bloque), se quiere saber de cuantas formas puedes poner estos M bloques en el intervalo [t1,t2], otra vez combinatoria, si cambiamos un poco el problema y nos preguntamos de cuantas formas puedo poner M-1 bloques si el primer bloque es puesto en la celda X nos quedaría: poner el primer bloque en la celda X, los bloques restantes deberían ser puestos luego de la celda X de C(N-X,M-1)  (siempre y cuando haya celdas suficientes para poner todos los M-1 bloques) entonces la respuesta a nuestro problema sería:

Dados los límites de l problema lo más es más que seguro que no podemos calcular esta sumatoria a cada rato terminaríamos con un TLE (es hasta fin de archivo podría ser un caso como podrían ser 1000 casos o más) así que nos usaremos la siguiente propiedad para tratar el problema:

Gracias a esta propiedad podremos llegar a:

                                                  

 C( N - t1 + 1, M)  - C( N - (t2 + 1) + 1 , M ) //se me acabaron las imágenes bonitas.

 (notar que no simplifiqué el 1 en la parte derecha por claridad) 

Esta formula es equivalente a la sumatoria que teníamos más arriba.                        

En palabras sería "todas las formas de colocar los M bloques desde de t1 hasta N, quitándole todas las formas de colocar los bloques desde (t2 + 1) hasta N".  

Nota: No olvidar usar inverso modular.

Problema K: King of the bar

El problema nos habla sobre un bar en el que en una "ronda" eligen a una persona al azar del bar, si esta tenía el vaso lleno lo bebé, y si tiene el vaso vacío le llenan el vaso, y se desea saber cual sería el número esperado de rondas para que este enfermo juego acabe (según yo las personas mueren de intoxicación etílica antes de acabar) el juego termina cuando todas las personas tienen el vaso lleno.

Primero se puede notar que se trata de una distribución uniforme por lo cual nuestro valor esperado no cambiará sin importar que personas sean las que llenen sus vasos primero, también se puede observar que si tenemos x personas con el vaso lleno pueden pasar 2 cosas: que alguien vacíe su vaso (ir a un estado anterior) o que alguien llene su vaso (ir al siguiente estado), excepto cuando x = 0 que solo tenemos la opción de llenar nuestro vaso, y cuando x = n porque el juego ya acaba ahí. Se puede notar que la esperanza para x personas con el vaso lleno es dependiente de la anterior esperanza y la siguiente esperanza, con esta información podemos construir un sistema de ecuaciones para la esperanza: 

 para 1 <= x <= N

Donde:

E(x) es la esperanza si tengo x personas con el vaso lleno.

1 en una ronda extra se llenará el vaso de alguien más.

x*E(x-1) cualquiera de las x personas que tienen el vaso lleno puede ser elegida a vaciar su vaso, con lo cual regresaríamos a E(x-1)

(N-x)*E(x+1) si tengo x personas con el vaso lleno entonces faltan N-x personas por llenar, si una es elegida entonces pasaría a E(x+1)

1/N son eventos equiprobables cada uno tiene una posibilidad de 1/N de ocurrir.

Ahora simplemente hay que resolver este sistema de ecuaciones (E(x) son las incógnitas), lógicamente no podemos usar Gauss-Jordan porque el límite es muy grande para tratar de hacer O(N³)... Estuve trancado sin saber que hacer para resolver este sistema para el límite dado. Luego comentando con un amigo me dijo "pero si esto lo vimos en una materia bla bla bla se hace con algoritmo de Thomas" (claramente no estaba atendiendo esa clase) y si este tipo de sistemas de ecuaciones puede ser resuelto en O(N) con el algoritmo de Thomas :) que resuelve ecuaciones del tipo:

Tener mucho cuidado con los modulos, hay varias restas (C++ no calcula bien modulos cuando el número es negativo) y divisiones (inverso modular). 

Nota: El tiempo para este problema parece ser muy estricto, tuve que hacer algunas optimizaciones al código, lectura rápida, etc. No paraba de darme TLE (es eso o mi forma de implementar es malísima).

 FIN