Hago este post para que discutamos ideas sobre el problema “Truco de magia” de Nivel 2.
mago.pdf (81,2 KB)
1 me gusta
En el certamen no logré sacar puntos en este problema. Una vez subido al juez, intenté resolverlo mediante un árbol generador mínimo, a través del algoritmo de Kruskal, y logré obtener 35 puntos (subtareas 1 y 2). En las otras subtareas no hay casos en los cuales el Output generado sea incorrecto, pero los casos que dan incorrectos se pasan de tiempo, y estoy viendo para reducir el tiempo de ejecución manteniendo la idea de usar un árbol generador mínimo.
Acá dejo mi código.
Código
#include <bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i=s;i<n;i++)
#define vec(v) v.begin(),v.end()
#define debug(x) cout << #x << " = " << x << endl
vector<int> padre, tam;
void init(int n){
padre = vector<int>(n);
tam = vector<int>(n,1);
forsn(i,0,n) padre[i] = i;
}
int find(int x){
if(padre[x] != x) padre[x] = find(padre[x]);
return x;
}
bool connected(int a, int b){
return find(a) == find(b);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(tam[a] < tam[b]) swap(a,b);
tam[a]+=tam[b];
padre[b] = a;
}
map<pair<int,int>,int> numH;
vector<int> kruskal(int n, vector<int> a, vector<int> b){
vector<int> ret;
init(n);
int K = a.size();
int i = 0;
while(i < K and ret.size() < n-1){
int n1 = a[i], n2 = b[i];
i++;
if(connected(n1,n2)) continue;
unite(n1,n2);
ret.push_back(numH[{n1,n2}]);
}
return ret;
}
int N;
vector<int> donde;
bool mago(vector<int> cantInicial, vector<int> cantFinal, vector<int> a, vector<int> b, vector<int> &hechizos){
int M = a.size();
N = cantInicial.size();
forsn(i,0,M){
numH[{a[i],b[i]}] = i;
numH[{b[i],a[i]}] = i;
}
hechizos = kruskal(N, a, b);
vector<pair<int,int>> numerated = vector<pair<int,int>>(N);
donde = vector<int>(N,-1);
forsn(i,0,N)
numerated[i] = {cantFinal[i], i};
sort(vec(numerated));
forsn(i,0,N){
int b = 0;
while(b < N and numerated[b].first <= cantInicial[i] and (numerated[b].first != cantInicial[i] or donde[numerated[b].second] != -1 or !connected(i,numerated[b].second))) b++;
if(b == N or numerated[b].first != cantInicial[i]){
hechizos = vector<int>();
return false;
}
donde[numerated[b].second] = i;
}
return true;
}
3 Me gusta
No llegué a analizar el 100% del código con total detalle, pero hay 4 cosas que me llamaron la atención:
- En la función “find”, sospecho que la línea return x en realidad debería decir return padre[x]; , ya que sino la función find(x) siempre retorna x, que no es su misión.
- ¿Se podría explicar la lógica del final de la función principal, donde está el forsn(i,0,N) que adentro tiene int b = 0; y el while ? A priori, a menos que se tenga un argumento de por qué el b no puede aumentarse mucho en distintas iteraciones pasando por los mismos valores una y otra vez, no me queda claro por qué esta parte no realizaría del orden de N^2 pasos (hasta N por iteración, y hay del orden de N iteraciones). N^2 es demasiado para este problema y eso solo podría explicar automáticamente el tiempo límite excedido.
- A las funciones que toman vectors (salvo mago, que ya tiene su signatura fija y no hay que cambiarla) se les podría pasar
const vector<int> &v(si son arreglos que no modificás: notar el ampersand&), así no se hace una copia entera del arreglo solamente para leerlo y usarlo. - No está mal en sí, pero no le llamaría “Kruskal” a la función pues no genera un árbol generador “mínimo” ya que no hay pesos en las aristas
Sí es cierto que usa la misma estructura de union find del algoritmo de Kruskal, pero mira las aristas en cualquier orden para obtener un árbol generador cualquiera, mientras que Kruskal se esfuerza en ordenarlas para asegurarse de obtener uno mínimo.
Sí es cierto que usa la misma estructura de union find del algoritmo de Kruskal, pero mira las aristas en cualquier orden para obtener un árbol generador cualquiera, mientras que Kruskal se esfuerza en ordenarlas para asegurarse de obtener uno mínimo.Si estas consideraciones (sobre todo la 2!!!) no resuelven el asunto, volvé a consultar!! 
1 me gusta
Buenas, perdón la demora que tuve en responderte. Recién hoy vuelvo a ver este post, por ende revisé mi código. No logré entender en un 100% la lógica de mi código en lo que vos referís en el punto 2, pero entendí que se excede de tiempo por una complejidad cuadrática. En base a esto, se me ocurrió hacer una modificación a mi código para que la complejidad sea O(N). La primera parte antes del punto 2 es la misma, pero la parte final cambia en lo siguiente: en mi anterior código podemos apreciar que hay un vector llamado “numerated” (pair<int,int>) el cual guarda los valores de cantFinal y la posición en la que están. Entonces al ver esto, se me ocurrió hacer un vector igual pero con los valores de cantInicial y su posición. Entonces, al tener los dos vectores ordenados, simplemente basta con hacer un for y chequear que el vaso al cual debe llegar la cantidad de cantInicial esté conectado con el vaso en el que esta cantidad se encuentra (antes de moverse a través del hechizo).
Estoy probando casos de prueba y por ahora me devuelven el resultado correcto, pero no puedo chequear si mi código resuelve con 100 puntos debido a que el ejercicio no se encuentra en el juez por el retroceso que este tuvo.
Dejo mi código acá abajo.
Código
#include <bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i=s;i<n;i++)
#define vec(v) v.begin(),v.end()
#define debug(x) cout << #x << " = " << x << endl
#define F first
#define S second
vector<int> padre, tam;
void init(int n){
padre = vector<int>(n);
tam = vector<int>(n,1);
forsn(i,0,n) padre[i] = i;
}
int find(int x){
if(padre[x] != x) padre[x] = find(padre[x]);
return padre[x];
}
bool connected(int a, int b){
return find(a) == find(b);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(tam[a] < tam[b]) swap(a,b);
tam[a]+=tam[b];
padre[b] = a;
}
map<pair<int,int>,int> numH;
vector<int> kruskal(const int n, const vector<int> &a, const vector<int> &b, const int K){
vector<int> ret;
init(n);
int i = 0;
while(i < K and ret.size() < n-1){
int n1 = a[i], n2 = b[i];
i++;
if(connected(n1,n2)) continue;
unite(n1,n2);
ret.push_back(numH[{n1,n2}]);
}
return ret;
}
bool mago(vector<int> cantInicial, vector<int> cantFinal, vector<int> a, vector<int> b, vector<int> &hechizos){
int K = a.size();
int N = cantInicial.size();
forsn(i,0,K){
numH[{a[i],b[i]}] = i;
numH[{b[i],a[i]}] = i;
}
hechizos = kruskal(N, a, b, K);
vector<pair<int,int>> numeratedInit(N), numeratedEnd(N);
forsn(i,0,N){
numeratedInit[i] = {cantInicial[i], i};
numeratedEnd[i] = {cantFinal[i], i};
}
sort(vec(numeratedInit));
sort(vec(numeratedEnd));
forsn(i,0,N){
if(connected(numeratedInit[i].S, numeratedEnd[i].S)) continue;
hechizos = vector<int>();
return false;
}
return true;
}
1 me gusta
La idea general de la solución está perfecta y el código está muy prolijo!!!, solamente creo hay un par de detalles menores:
- Si los arreglos cantInicial y cantFinal no son justo permutación uno del otro, este código asume que sí lo van a ser, y mira solamente las conexiones. En ese caso sería imposible por más que se tengan todas las conexiones posibles entre todos los vasos, pero igualmente el código dice que es posible.
- En un caso como este:
3
1 1 2
2 1 1
1
0 2
Si no entiendo mal tu codigo le pide que esten todos conectados entre si esos tres vasos y entonces va a dar false, pero deberia ser true.
El ejemplo que pusiste en el punto 2 me dió incorrecto, pero en realidad sucedió lo contrario a lo que decís en el punto 1: es posible mover los vasos para que queden de la segunda forma, pero mi código tira incorrecto ya que considera el intercambio entre números que son iguales (no se si entendí bien lo que decís en el punto 1, en dicho caso decímelo en respuesta a esto). Para resolver el error que encontré a través de tu ejemplo hago lo siguiente: el vector para los números de cantInicial lo ordeno de menor a mayor pero, en caso de que dos números sean iguales, priorizo que sea menor la posición de un número que de otro; mientras que para el vector de los números de cantFinal hago casi lo mismo, solo que, en caso de que dos números sean iguales, priorizo que sea mayor la posición de un número que de otro.
También agrego una parte a la condición del for y es que si los números a comparar entre ambos vectores son iguales y las posiciones en las que debe ubicarse cada uno también, hago continue en el for.
Probé el código con el ejemplo que pusiste además de ejemplos que había probado antes y funcionó, así que creo que ya está.
Dejo el código acá abajo.
Código
#include <bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i=s;i<n;i++)
#define vec(v) v.begin(),v.end()
#define debug(x) cout << #x << " = " << x << endl
#define F first
#define S second
vector<int> padre, tam;
void init(int n){
padre = vector<int>(n);
tam = vector<int>(n,1);
forsn(i,0,n) padre[i] = i;
}
int find(int x){
if(padre[x] != x) padre[x] = find(padre[x]);
return padre[x];
}
bool connected(int a, int b){
return find(a) == find(b);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(tam[a] < tam[b]) swap(a,b);
tam[a]+=tam[b];
padre[b] = a;
}
map<pair<int,int>,int> numH;
vector<int> kruskal(const int n, const vector<int> &a, const vector<int> &b, const int K){
vector<int> ret;
init(n);
int i = 0;
while(i < K and ret.size() < n-1){
int n1 = a[i], n2 = b[i];
i++;
if(connected(n1,n2)) continue;
unite(n1,n2);
ret.push_back(numH[{n1,n2}]);
}
return ret;
}
bool ordInit(const pair<int,int> a, const pair<int,int> b){
return a.F < b.F or (a.F == b.F and a.S <= b.S);
}
bool ordEnd(const pair<int,int> a, const pair<int,int> b){
return a.F < b.F or (a.F == b.F and a.S >= b.S);
}
bool mago(vector<int> cantInicial, vector<int> cantFinal, vector<int> a, vector<int> b, vector<int> &hechizos){
int K = a.size();
int N = cantInicial.size();
forsn(i,0,K){
numH[{a[i],b[i]}] = i;
numH[{b[i],a[i]}] = i;
}
hechizos = kruskal(N, a, b, K);
vector<pair<int,int>> numeratedInit(N), numeratedEnd(N);
forsn(i,0,N){
numeratedInit[i] = {cantInicial[i], i};
numeratedEnd[i] = {cantFinal[i], i};
}
sort(vec(numeratedInit), ordInit);
sort(vec(numeratedEnd), ordEnd);
forsn(i,0,N){
if((numeratedInit[i].F == numeratedEnd[i].F and numeratedInit[i].S == numeratedEnd[i].S) or connected(numeratedInit[i].S, numeratedEnd[i].S)) continue;
hechizos = vector<int>();
return false;
}
return true;
}
Creo que ya entendí. ¿Te referís a un caso como este?
4
5 40 9 2
9 5 40 1
5
0 1
1 2
0 2
0 3
1 3
No pensé en ese caso 
.
Ahora si, creo haberlo solucionado.
En el for final, agrego una variable de tipo bool inicializada en true, y un if en el cual establezco la condición de que si los números a comparar son diferentes pero sus debidas posiciones iguales, cambio el valor de la variable a false, y en el segundo if agrego esta variable a la condición.
EDIT: al final descubrí que ninguna de las dos cosas que hice modificando el código habían funcionado, por lo que busqué una forma de solucionar las dos cosas juntas: si la condición del for (la del código del mensaje de más arriba) da true, que intercambie en el vector cantInicial los valores de las posiciones correspondientes, y luego retorne true en caso de que los vectores cantInicial y cantFinal sean iguales. El código de abajo contiene la resolución recién mencionada.
Código
#include <bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i=s;i<n;i++)
#define vec(v) v.begin(),v.end()
#define debug(x) cout << #x << " = " << x << endl
#define F first
#define S second
vector<int> padre, tam;
void init(int n){
padre = vector<int>(n);
tam = vector<int>(n,1);
forsn(i,0,n) padre[i] = i;
}
int find(int x){
if(padre[x] != x) padre[x] = find(padre[x]);
return padre[x];
}
bool connected(int a, int b){
return find(a) == find(b);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(tam[a] < tam[b]) swap(a,b);
tam[a]+=tam[b];
padre[b] = a;
}
map<pair<int,int>,int> numH;
vector<int> kruskal(const int n, const vector<int> &a, const vector<int> &b, const int K){
vector<int> ret;
init(n);
int i = 0;
while(i < K and ret.size() < n-1){
int n1 = a[i], n2 = b[i];
i++;
if(connected(n1,n2)) continue;
unite(n1,n2);
ret.push_back(numH[{n1,n2}]);
}
return ret;
}
bool ordInit(const pair<int,int> a, const pair<int,int> b){
return a.F < b.F or (a.F == b.F and a.S <= b.S);
}
bool ordEnd(const pair<int,int> a, const pair<int,int> b){
return a.F < b.F or (a.F == b.F and a.S >= b.S);
}
bool mago(vector<int> cantInicial, vector<int> cantFinal, vector<int> a, vector<int> b, vector<int> &hechizos){
int K = a.size();
int N = cantInicial.size();
forsn(i,0,K){
numH[{a[i],b[i]}] = i;
numH[{b[i],a[i]}] = i;
}
hechizos = kruskal(N, a, b, K);
vector<pair<int,int>> numeratedInit(N), numeratedEnd(N);
forsn(i,0,N){
numeratedInit[i] = {cantInicial[i], i};
numeratedEnd[i] = {cantFinal[i], i};
}
sort(vec(numeratedInit), ordInit);
sort(vec(numeratedEnd), ordEnd);
forsn(i,0,N){
if((numeratedInit[i].F == numeratedEnd[i].F and numeratedInit[i].S == numeratedEnd[i].S) or connected(numeratedInit[i].S, numeratedEnd[i].S)){
swap(cantInicial[numeratedInit[i].S], cantInicial[numeratedEnd[i].S]);
if(cantInicial == cantFinal) return true;
}
}
hechizos = vector<int>();
return false;
}