Solucionario Regional South America 2013

El 11 de noviembre se realizo el Regional ACM ICPC – South America 2013
Fueron 10 problemitas, Compitiendo contra paises como Argentina, Bolivia, Chile, Uruguay, Paraguay.
Los resultados fueron publicados en http://icpc.baylor.edu/regionals/finder/southamerica-south-2013/standings

Felicitaciones a los equipos peruanos que pasaran al World Final en Rusia (Ekaterinburg)   🙂

Estuvieron xevere los problemitas, pueden practicar en el UVA los problemas del 12668-12677
Adjunto mis soluciones https://www.dropbox.com/sh/n33f4d38a1nowuw/OgGMAJE5Ic

Attacking rooks               Bipartite Matching                                 Facil
Blogger language             Segment trees (Lazy Propagation)          Dificil
Counting ones                 Dp sobre digitos                                    Muy Facil
Disjoint water supply        Dp                                                        Facil
Eleven                             Dp con combinatorias                            Medio
Football                           Greedy                                                 Muy Facil
Go up the ultras               Range Minimun Query                           Medio Facil
Hide and seek                  Sweep Circle                                         Dificil
Inverting Huffman              Greedy                                                  Medio
Join two kingdoms            BFS (Diametro del arbol)                         Medio Facil
Analisis

Attacking rooks
En un tablero de ajedrez de N filas y columnas (N<=100) colocamos peones en determinadas posiciones.
Ahora queremos saber la maxima cantidad de torres podemos poner de tal manera de que no existan dos torres que se amenacen entre si.
Sabemos que el movimiento de una torre es horizontal y vertical, ojo que una torre no amenaza a otra torre si en medio de ellos esta un peon.

sabemos que luego de colocar esas torres todas las posiciones son amenazadas ya que si no lo estuviese podriamos colocar una torre mas.

Los cuadritos negros son los peones.

Del grafico si quisieramos cubrir la columna 1(verde), se puede hacer de 2 maneras diferentes, la primera es simplemente colocando una torre en la columna 1
y la segunda es colocando 3 torres en las filas (1,2,3)

Para cubrir la fila 1 de color rojo (ojo que la fila 1 se divide en 2 por culpa del peon)
se cubre de 2 maneras diferentes (colocando una torre en la fila 1 de color rojo y colocando 3 torres en las columnas(5,6,7) )

De esto vemos la correspondencia que hay entre filas y columnas.
La respuesta viene hacer el Bipartite Matching entre (Filas y Columnas) codeamos un hopcroft karp O(E*sqrt(V))

Este bonito problema es explicado en el tutorial de topcoder 😛 (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2)

Blogger language
Dado los string «s» y «t» se les pide contestar «q» operaciones. (q<=100000)
string s (tamanho n, donde n<=100000) , string t (tamanho m, donde m<=5)

cada operacion es de la forma [A-B] se debe contestar el maximo desajuste que hay entre los substrings S que van desde la posicion A-B
y el string t. El desajuste es igual a la cantidad de caracteres que difieren entre mayuscula y minuscula.
ejm AbCdE y aBCde -> desajuste =3 (A,a) , (b,B) y (E,e)
abcde y ABXDe -> desajuste =-1 puesto c y X son caracteres diferentes, solo deben diferir en minuscula y mayuscula

Para hacer mas dificil el problema luego se deben invertir las mayusculas a minusculas y minusculas a mayusculas del string s
desde la posicion A hasta B.
Caso de prueba
3 gR
PrOgRAMmINgiSgrEAt
1 7
4 18
6 14
9 abCAb

del (1 al 7) el substring es ProgRAM-> desajuste (gr, gR) es igual a 1
invertimos los caracteres luego quedando s= pRoGrammINgiSgrEAt

Para mas detalles leer el statement.
Debemos contestar en un intervalo y actualizar en un intervalo (nos da la idea de Lazy Propagation)
el string t (tiene tamanho 5 cuanto mucho) jugando con minusculas y mayusculas hay hasta 2^5 formas de representarlo.
Para cada representacion se usara mascara donde necesitamos 32 bits.
el segment trees se tendra mascara[node]=mascara[2*node]|mascara[2*node+1].
0 minuscula, 1 mayuscula
gr=0
Gr=1
gR=2
GR=3
si un segmento contiene a los 4 strings su mascara[node]=00001111
El unico detalle esta en que como cada indice representa a «m» caracteres
el query(a,b)-> seria representado mejor como query(a,b-m+1)
pues el indice (b-m+1) representa al substring desde [b-m+1,b]
el problema es en el update:
Si tenemos update(a,b) y el string es
……..hamlet…. donde m=4
si actualizamos hamlet los m-1 elementos hacia la izquierda y (m-1) elementos del sufijo hamlet
seran afectados de manera diferente.
para olvidarnos de la parte izquierda nos damos cuenta rapidamente que
update(a,b)= update(0,b) y luego update(0,a-1)
ahora solo nos preocupamos por el sufijo de tamaño m-1 que se modifica de otra manera
como m es pequeño el sufijo de tamaño m-1 se realizara por update2()

Aclaracion. sobre el sufijo

0123456789
….hamlet…
si m=4
UPDATE2
para el indice 7 solo se modificara (7,8,9)
para el indice 8 solo se modificara (8,9)
para el indice 9 solo se modificara (9)

UPDATE1
para el indice 4,5,6,7 se modificaran los «m» elementos siguientes

Es pesado de implementar, se debe ser eficiente 🙂

Counting ones

Desde A hasta B en su representacion binaria cuantos 1’s se utilizan (A<=B y B<=10^16)
la respuesta es simplemente f(b)-f(a-1) donde f(x) la cantidad de digitos 1 desde 0 hasta X en su representacion binaria.
Es un problema clasico de DP sobre digitos.
recorremos los digitos del numero X desde el digito mas significativo al menos

sum nos guardara la cantidad de 1s que vamos añadiendo

long long dp(int pos,bool menor,int sum)
.     si el numero que vamos formando ya es menor que X
.             entonces podemos añadir un 0 o un 1
.     si aun no lo es
.          si en esa posicion el digito X es 0 {
.                 entonces solo puedo añadir un 0 y lo que estoy formando sigue sin ser menor
.                 (Ojo que no puedo añadir 1 porque formaria un numero mayor X)
.          }sino (en esa posicion el digito X es 1){
.                 entonces puedo añadir 0 y lo que forme en adelante sera siempre menor
.                 tambien puedo añadir 1 pero sigue sin ser menor
.          }

el caso base se da cuando lleguemos a pos=-1 retornamos simplemente la cantidad de unos que hemos puesto
que justamente tiene nuestro parametro sum.

complejidad O(60*2*60)
Nota: Pensando un poquito mas podemos eliminar nuestro tercer parametro.

Disjoint water supply
El nodo raiz es el numero 1.
Las aristas van de indices menores a indices mayores.
ejm:
6 6 (6 nodos y 6 aristas) cantidad de nodos n<=1000
1 2
1 3
1 4
2 5
2 6
3 6
Cuantos pares (i,j) existen de tal manera que exista al menos una ruta desde 1 a i
y otra ruta de 1 a j en el cual el unico nodo en comun de esas 2 rutas sea el nodo raiz 1

Nos damos cuenta que el grafo es un DAG (Grafo dirigido y aciclico)
entonces podemos meterle DP( Programacion dinamica).
nos piden cuantos pares distintos (i,j) existen entonces nuestros parametros son:
modelaremos el grafo al reves iremos desde un nodo x hacia el nodo 1
(i<j)
bool dp(int i,int j){} (Se puede o no se puede)
si muevo el nodo i podria perder informacion sobre ese nodo. y no sabria como validar si mas adelante desde j llegase a tomar el nodo i
pero si muevo el nodo j que tiene un indice mayor es obvio que i no tomara j puesto las arista van de mayor a menor valor

El problema es facil 🙂

Eleven 

nos dan un numero N (N<=10^100) nos piden si realizamos una permutacion sobre los digitos de N
cuantos de ellos son multiplos de 11, ojo el numero no puede comenzar con 0

Lo que hacemos primero es f[10] obtener la frecuencia de cada digito en N
Ya que el primer numero no puede comenzar con 0 fijamos el primer digito.
Sabemos el criterio de divisibilidad por 11, 9842723 (+-+-+-+) ((9+4+7+3)-(8+2+2))%11=0 es multiplo de 11
http://es.wikipedia.org/wiki/Divisibilidad

lanzaremos un DP(int pos,int modulo,int posi,int nega)
pos nos indica el digito que queremos poner
modulo nos indica en modulo 11 el numero que estamos formando
posi nos indica cuantos numeros en posiciones impare hemos cogido
nega nos indica cuantos numeros en posiciones pares hemos cogido

dentro de la dinamica fijaremos cuantos numeros en posiciones pares «pos» usaremos
la cantidad de posiciones impares «pos» se obtiene por diferencia con la frecuencia obtenida anteriormente

para cada iteracion i <= frecuencia[pos]
primer=i;
segundo=frecuencia[pos]-primer;
(C[posi][primer]*C[nega][segundo]*dp(pos+1,(modulo+primer*pos-segundo*pos)%11,posi-primer,nega-segundo)

la combinatoria se da por que nos falta «posi» posiciones impares y solo pondremos primer
analogamente con «nega» y luego de llenar pos procederemos a llenar pos+1

Football 

Nos dan los N scores de los partidos que hemos jugado (N<=10^5)
por debajo de la mesa vamos a comprar G goles de tal manera que podemos cambiar los score.
vamos a distribuir G goles a nuestro favor en los scores de tal manera que maximicemos la cantidad de puntos que tendremos en el torneo
(Ya sabemos que recibimos 3 puntos por partido ganado , 1 por partido empatado y 0 por perdido)

Nos damos cuenta que no es necesario gastar goles en partidos que ya ganamos.
Si un partido esta empatado gastamos un gol, para convertir el partido en ganado y poder ganar 2 puntos mas en el torneo
Si un partido esta perdido la diferencia de goles nos permitira ganar un punto mas y la diferencia de goles+1 nos permitira ganar de ese punto, 2 puntos mas

De este analisis nos damos cuenta que siempre es preferible desempatar los partidos que estan empatados.
Luego los partidos perdidos se iran asi. se ordenar por diferencia de goles.
Vamos hacer ganar los partidos que fueron perdidos por menor diferencia de goles.
En el caso que no se pueda hacer ganar el partido perdido, veremos si lo podemos hacer empatar.

Go up the ultras

Los alturas los almacenamos en un arreglo c[]. Un indice i es llamado pico si (c[i-1]<c[i] y c[i]>c[i+1])

Del grafico son picos (4,7,12,14,17,20,23)

Un indice x es llamado ultra si es un pico y si en el camino desde x hacia otros picos de mayor altura hay un indice z tal que c[x]-c[z]>=150000 . De aqui deducimos que mientras mas nos movemos conseguiremos menores valores de c[z] que haran una diferencia mayor igual a 150000 asi que solamente necesitamos el primer pico mayor por la izquierda y por la derecha. si no hay c[z]=0

a es el mayor indice entre 0 y x-1 tal que c[a]>c[x] si no existe a=x

b es el menor indice entre x+1 y n tal que c[b]>c[x] si no existe b=x

Para encontrar a y b queria hacer binary search sobre range maximun query, pero decidi obtenerlo de manera lineal. (se parece a este problema esta parte  http://www.spoj.com/problems/HISTOGRA/)

int der[n];
der[n-1]=n;
for(int i=n-2;i>=0;i–){
der[i]=i+1;
while(der[i]<n && c[i]>=c[der[i]])
der[i]=der[der[i]];
}

der[i] obtiene el menor indice tal que c[i]<c[der[i]]

luego de encontrar a y b  encuentro el z para cada intervalo   [a-x] y [x-b] con un range maximun query

complejidad O(nlogn)

Hide and seek

El analisis de este problema es hecho por chen

En este problema un sweep circle ayuda bastante,
ya que cuando fijamos un rayo que pasa por un kid solo hace falta saber si el primer corte con un segmento
fue antes o despues de este kid no hace falta analizar otros kids ya que por la condicion de no colinealidad solo hay 1 entonces guardamos un set de segmentos cortantes al rayo actual, en el mismo orden de corte que  sus cortes con el rayo, debido a que los segmentos no se intersecan, este orden no se alterara al cambiar  de rayo, entonces debido a la condicion de no colinealidad, al cambiar de rayo siempre encontraremos solo un punto.

Si este punto es un kid entonces verificamos si esta antes o despues del primer elemento del set.
Si este punto es el inicio de un segmento, agregamos el segmento al set si este punto es el final
de un segmento, borramos el segmento del set La nocion de inicio final sí puede cambiar con respecto al
seeker, por ello luego de fijar el seeker se debe reindexar las etiquetas de inicio y final.

Inverting Huffman

Este problema es bonito , lean el statement 😀

Sea la entrada

9

5 5 4 4 4 3 3 2 2

obtendriamos este arbol donde los nodos morados son los nodos individuales que tenemos en un comienzo y los nodos naranjas es el resultado de juntar dos nodos.

Los nodos que tienen mayor nivel obviamente tendran el menor valor es decir 1.

El greedy va en el hecho de cada para un nivel x los nodos morados tendran el maximo valor de todos los nodos en el nivel x+1, ya que si no lo tuviesen podrian haber sido juntado antes.

Nota: no es necesario armar el arbol.   complejidad O(n*n)

Join two kingdoms

Tenemos dos reinos Nlogonia, y Quadradonia que son representados como un arbol cada uno.

cantidad de ciudades en Nlogonia y Quadradonia , N,Q <=10^4

Por razones comerciales deciden hacer una carretera entre dos ciudades (1 de Nlogonia y otra de Quadradonia). Pero no se especifica cual par de nodos seria.

Se decide introducir una medida «size» que es la distancia maxima entre dos nodos del nuevo arbol obtenido al unir las 2 ciudades. Nos preguntan cual es el size esperado. (Es decir la sumatoria de size/(N*Q))

Del grafico observamos que si añadimos la arista entre el nodo i y j.
Entonces size= max(size (Nlogonia) ,size (Quadradonia) , size(entre ambas ciudades) )
size(Nlogonia) es igual al diametro del arbol de Nlogonia
size(Quadradonia) es igual al diamentro del arbol deQuadradonia

Encontrar el diametro de un arbol se obtiene en O(N)
desde cualquier nodo se lanza un bfs. el ultimo nodo en visitar es uno de los extremos
desde ese extremo se lanza otro bfs el ultimo nodo en visitar es el otro extremo.

en el grafico vemos estos extremos son pintados de celeste.
ahora debemos encontrar el size(entre ambas ciudades) al conectar un nodo entre i y j
para conectar estas dos ciudades debieron pasar por esa arista.
este size viene hacer dis1[i]+1+dis2[j].

dis1[i]= es la maxima distancia del nodo i a cualquier otro nodo de Nlogonia
esto es igual a dis1[i]=max(distancia(i,extremo1),distancia(i,extremo2)) de ese arbol
para rellenar todo el arreglo dis1[]. se debio lanzar bfs de los extremos del arbol

Analogamente rellenamos el arreglo dis2[]
Hasta el momento hemos hecho O(N+Q)

la respuesta seria simplemente
long long dev=0;
for(int i=0;i<n;i++)
for(int j=0;j<q;j++)
dev+=max(maxi,dis1[i]+dis2[j]+1);

donde maxi es el maximo de los diametros de Nlogonia y Quadradonia
Debido al doble for obtenemos la respuesta en O(N*Q) que es muy lento
para evitar eso solo fijaremos dis[i], mediante acumulados y con el uso de binary search haremos ese calculo.

complejidad O(N*logQ)

good luck and have fun

hamlet_fiis