Hago este post para que discutamos ideas sobre “Aprovechando comodines”.
Comodin.pdf (73,1 KB)
5 Me gusta
En la competencia, lo que yo había planteado era hacer Fuerza Bruta + DFS para poder contar de manera correcta cadenas adyacentes de números iguales y comodines, sabiendo que se me podría ir de tiempo, pero lo intenté y me dió 15 puntos a través de una subtarea en la cual entraba con suerte el algoritmo. Después en la mayoría de las otras subtareas perdía los puntos por execution timed out.
Mi nuevo planteo fue hacer un BFS e ir asignando padres por cadena de números adyacentes iguales, incluyendo comodines, pero para estos no marcaba como visitados ya que podrían ser reutilizados por otra cadena de números adyacentes, por lo que para estos tenía un vector de tres dimensiones de tipo booleano, en los cuales guardaba si tenía asignado un padre i (al cual accedo por número de posición del vector). Cuando detectaba un número distinto, lo pusheaba al bfs asignándole un padre mayor al que le había asignado a la última cadena de números adyacentes. Después me di cuenta de que fallaría en algunos casos, pero en lo que es el caso ejemplo del problema, me da un resultado correcto. Cuando envío en el juez me tira todo signal 11, y lo que estoy haciendo ahora es buscar de qué vector se está cayendo.
3 Me gusta
La subtarea de 15 puntos es N\cdot M \leq 500, o sea que la grilla en esos casos tiene a lo sumo 500 posiciones. Si sacaste 15 puntos quiere decir que resolvió correctamente todos los casos pequeños (con pocas casillas). Así que es probable que tu enfoque sea correcto, solo que ineficiente. No creo que haya entrado “de suerte” 
El segundo enfoque no estoy seguro de estar entendiéndolo. ¿Hacés un solo BFS o uno por cada tipo de carta?
Que pase el ejemplo en general no dice mucho. Es importante hacerse casos a mano donde uno sepa la respuesta para poder contrastar 
Para ver por qué es ineficiente el primer enfoque y para ver por qué falla el segundo (si es que falla) creo que sería mejor que pegues los códigos 
Aprovecho para recordar que en este problema (como en muchos otros) hay subtareas. Cada subtarea puede ser un problema radicalmente distinto o ser conducente a una solución de 100 puntos. En este problema las subtareas son:
- No hay comodines (30 puntos)
- N \cdot M \leq 500 (15 puntos)
- \texttt{grilla[i][j]} \leq 10 (21 puntos)
- Sin más restricciones, o sea (34 puntos)
Donde para entender completamente hay que recordar que las cotas generales del problema que valen para todos los casos son:
- 1 \leq N \cdot M \leq 200.000
- 0 \leq grilla[i][j] \leq 1.000
Veamos entonces como resolver las primeras 3 subtareas para organizar un poco la línea de pensamiento.
Subtarea 1: No hay comodines
Si no hay comodines solo hay que identificar la componente más grande de cartas del mismo tipo. Como la grilla podría ser grande debemos hacerlo eficientemente, es decir sin revisitar casillas. Tanto BFS como DFS son dos algoritmos que nos permiten recorrerlas eficientemente, solo debemos quedarnos con la componente más grande que hayamos encontrado para algún color.
Ya que estoy recuerdo el (clásico) tip que mencioné durante la clase de grafos para moverse en un grafo grilla que pueden ver aquí, que se resume en utilizar estos dos arreglitos auxiliares:
const int MOVIMIENTOS = 4;
int dx[MOVIMIENTOS] = {1,0,-1,0}; // Abajo, Derecha, Arriba, Izquierda
int dy[MOVIMIENTOS] = {0,1,0,-1}; // Abajo, Derecha, Arriba, Izquierda
Subtarea 2: N \cdot M \leq 500
Sabemos que el tablero es chico, pero ahora puede haber comodines. ¿En qué afecta el hecho de que pueda haber comodines? Al calcular cada componente, tenemos que asumir que los comodines son del mismo tipo de carta que la de la componente que estamos calculando.
Luego debemos quedarnos con la componente más grande y tener cuidado con un caso donde solo hay comodines (entonces la componente más grande es de comodines, y puede ser fácil olvidarse de tenerlo en cuenta en nuestra implementación). Notar que aunque el tablero es pequeño, estamos revisitando a los comodines muchas veces (pues al analizar cada componente nos permitimos visitar nuevamente los comodines).
Subtarea 3: \texttt{grilla[i][j]} \leq 10
Lo que nos están diciendo es que hay pocos tipos de carta distintas en la grilla. Por lo tanto, resulta tentador intentar explotar esta propiedad de esta subtarea. Una opción posible es ampliar los comodines. Basta hacer 10 pasadas (una por cada tipo de carta), y en cada una de ellas asumir que los comodines son todos del mismo color.
Finalmente debemos calcular la componente más grande de cada tipo de carta. Notar que cada comodín es visitado a lo sumo 10 veces. Nuevamente necesitamos de un algoritmo eficiente como BFS o DFS para recorrer la grilla.
Dejo un código que debería resolver las primeras 3 subtareas:
Código
#include <bits/stdc++.h>
#define forsn(i,s,n) for(tint i=(s);i<(tint)(n); i++)
#define forn(i,n) forsn(i,0,n)
#define dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef long long tint;
const tint MOVE = 4;
tint dx[MOVE] = {1,0,-1,0};
tint dy[MOVE] = {0,1,0,-1};
bool en_rango(tint x, tint y, tint n, tint m)
{
return ((0 <= x && x < n) && (0 <= y && y < m));
}
tint visitados_global;
void dfs(tint i, tint j, tint carta, vector<vector<int> > &grilla, vector<vector<map<tint,tint> > > &visitado)
{
tint n = tint(grilla.size());
tint m = tint(grilla[0].size());
visitado[i][j][carta] = 1;
visitados_global++;
forn(k,MOVE)
{
tint i_new = i + dx[k];
tint j_new = j + dy[k];
if (en_rango(i_new,j_new,n,m) && visitado[i_new][j_new][carta] == 0 && (tint(grilla[i_new][j_new]) == 0 or tint(grilla[i_new][j_new]) == carta) )
dfs(i_new,j_new,carta,grilla,visitado);
}
}
int comodines(vector<vector<int> > grilla) // Idea: Donde hay comodines, ampliamos los nodos a todas las cartas posibles
{
tint n = tint(grilla.size());
tint m = tint(grilla[0].size());
vector<vector<map<tint,tint> > > visitado (n, vector<map<tint,tint> > (m));
tint maxi = -1;
forn(i,n)
forn(j,m)
{
tint carta = grilla[i][j];
if (carta > 0 && visitado[i][j][carta] == 0)
{
visitados_global = 0;
dfs(i,j,carta,grilla,visitado);
maxi = max(maxi,visitados_global);
}
}
return int(n*m*(maxi == -1)) + int(maxi*(maxi >= 0)); // hack ad-hoc por si son todas comodines
}
La subtarea 4 probablemente la explique en detalle más adelante.
2 Me gusta
Gracias por la gran explicación!
Yo en competencia también meti fuerza bruta+DFS, solo que bueno, al haber una subtarea de sin comodines, era un DFS normal, mi problema era reiniciar el visited de los comodines en el DFS, así que mande un for(i:ceros.size());
Luego fuera de competencia saque 79 puntos en el ejercicio, faltandóme 3 o 4 casos, que creo que son debido a que mi idea es separar a los 0 por conjuntos, de manera que si llamo a un cero, su adyacente sera del mismo conjunto y así para manejar entre tantos comodines.
El problema es que yo mando la suma de todo el conjunto + mas los que fui encontrando, a la suma del mismo conjunto al terminar, para que luego otra fila de números acceda a ella, esto lo hice con un vector<vector > tab(cont+1,vector(1001) );
Donde guardo todos los conjuntos (cont+1) y todas las posibilidades(1001).
El caso es que en casos como este no funciona debido a que el 1 de (1,1) toma la suma del 0 de arriba y del 0 de la izquierda cuando es la misma suma, ya que estan en conjuntos disjuntos
1 0 2
0 1 5
8 7 9
Dejo mi código si alguien quiere leerlo (aunque creo que se me hizo muy largo) :
Código
int comodines(vector<vector<int> > grilla){
n = grilla.size(),m = grilla[0].size();
vector<vector<int> >comp(n,vector<int>(m,-2)); //preguntar a conjunto pertence
vector<vector<bool> > w(n,vector<bool>(m)); //preguntar si ya pertenece a un conjunto
stack<pair<int,int> > q;
int id[200001]; //guardo la cantidad de comodines de cada conjunto
memset(id,-1,sizeof id);
int cont = -1;
for(int i=0;i<n;++i){
for(int e=0;e<m;++e){
if(grilla[i][e] == 0){
if(w[i][e]== false) cont++;
else continue;
int aux = 0;
comp[i][e] = cont;
q.push(make_pair(i,e));
while(!q.empty()){
pair<int,int> pos = q.top();
aux++;
q.pop();
if(pos.s+1<m and grilla[pos.f][pos.s+1] == 0){ //derecha
if(comp[pos.f][pos.s+1] != cont ){
comp[pos.f][pos.s+1] = cont;
w[pos.f][pos.s+1] = true;
q.push(make_pair(pos.f,pos.s+1));
}
}
if(pos.s-1 >=0 and grilla[pos.f][pos.s-1] == 0){ //izquierda
if(comp[pos.f][pos.s-1] != cont ){
comp[pos.f][pos.s-1] = cont;
w[pos.f][pos.s-1] = true;
q.push(make_pair(pos.f,pos.s-1));
}
}
if(pos.f+1<n and grilla[pos.f+1][pos.s] == 0){ //abajo
if(comp[pos.f+1][pos.s] != cont ){
comp[pos.f+1][pos.s] = cont;
w[pos.f+1][pos.s] = true;
q.push(make_pair(pos.f+1,pos.s));
}
}
if(pos.f-1>=0 and grilla[pos.f-1][pos.s] == 0){ //arriba
if(comp[pos.f-1][pos.s] != cont ){
comp[pos.f-1][pos.s] = cont;
w[pos.f-1][pos.s] = true;
q.push(make_pair(pos.f-1,pos.s));
}
}
}
id[cont] = aux;
}
}
}
vector<vector<int> > tab(cont+1,vector<int>(1001) ); // conjuntos * numeros disponibles
for(int i=0;i<tab.size();++i){
for(int e=0;e<1001;++e)tab[i][e] = id[i]; //asigno a cada conjunto su cantidad de comodines
}
int mayor = 0;
for(int i=0;i<n;++i){
for(int e=0;e<m;++e){
if( grilla[i][e]>0 ){ //numero disponible distinto de comodin
q.push(make_pair(i,e));
int c = grilla[i][e];
vector<int> s;
grilla[i][e] = -1;
int suma = 1,aux;
while(!q.empty()){
int a = q.top().f, b = q.top().s;
q.pop();
if( b+1 < m ){ //derecha
if(grilla[a][b+1] == c){
q.push(make_pair(a,b+1));
grilla[a][b+1] = -1;
suma++;
}
else if(grilla[a][b+1] == 0){ //comodin
aux = comp[a][b+1];
if(tab[aux][c]!=0){
suma+=tab[aux][c];
tab[aux][c]= 0;
s.push_back(aux);
}
}
}
if( b-1 >= 0 ){ //izquierda
if(grilla[a][b-1] == c){
q.push(make_pair(a,b-1));
grilla[a][b-1] = -1;
suma++;
}
else if(grilla[a][b-1] == 0){ //comodin
aux = comp[a][b-1];
if(tab[aux][c]!=0){
suma+=tab[aux][c];
tab[aux][c]= 0;
s.push_back(aux);
}
}
}
if( a+1 < n ){ //abajo
if(grilla[a+1][b] == c){
q.push(make_pair(a+1,b));
grilla[a+1][b] = -1;
suma++;
}
else if(grilla[a+1][b] == 0){ //comodin
aux = comp[a+1][b];
if(tab[aux][c]!=0){
suma+=tab[aux][c];
tab[aux][c]= 0;
s.push_back(aux);
}
}
}
if( a-1 >= 0 ){ //arriba
if(grilla[a-1][b] == c){
q.push(make_pair(a-1,b));
grilla[a-1][b] = -1;
suma++;
}
else if(grilla[a-1][b] == 0){ //comodin
aux = comp[a-1][b];
if(tab[aux][c]!=0){
suma+=tab[aux][c];
tab[aux][c]= 0;
s.push_back(aux);
}
}
}
}
for(int j=0;j<s.size();++j)tab[s[j]][c] = suma; //todos los comodines les agrego la suma
mayor = max(mayor,suma);
}
}
}
return mayor;
}
3 Me gusta
Muchas gracias Guty por la ayuda! Voy a intentar resolver el problema
2 Me gusta