#include "grader.h"
#include "encoder.h"
#include <queue>
#include <vector>
using namespace std;
// Calcula la longitud del camino mas corto desde la fuente al resto de ciudades.
vector<int> caminoMasCortoATodasLasCiudades(int fuente, vector<vector<int>> & listaAdyacencia) {
int numCiudades = (int) listaAdyacencia.size();
vector<int> distancias(numCiudades, numCiudades + 1);
distancias[fuente] = 0;
queue<int> colaBfs;
colaBfs.push(fuente);
while (!colaBfs.empty()) {
int ciudad = colaBfs.front();
colaBfs.pop();
for (int & vecina: listaAdyacencia[ciudad]) {
if (distancias[vecina] > distancias[ciudad] + 1) {
distancias[vecina] = distancias[ciudad] + 1;
colaBfs.push(vecina);
}
}
}
return distancias;
}
// Calcula la distancia entre todos los centros de actividades y todas las ciudades.
vector<vector<int>> todasLasDistancias(
vector<vector<int>> & listaAdyacencia, int numCentros
) {
vector<vector<int>> distancias(numCentros);
for (int i = 0; i < numCentros; i++) {
distancias[i] = caminoMasCortoATodasLasCiudades(i, listaAdyacencia);
}
return distancias;
}
// Encuentra el arbol BFS del grafo y saber el padre de cada ciudad.
vector<int> definePadres(vector<vector<int>> & listaAdyacencia) {
vector<int> padre(listaAdyacencia.size(), -1);
queue<int> colaBfs;
colaBfs.push(0);
padre[0] = -2;
while (!colaBfs.empty()) {
int ciudad = colaBfs.front();
colaBfs.pop();
// Definimos el padre como la primera conexion que vemos de la ciudad.
for (int & vecina: listaAdyacencia[ciudad]) {
if (padre[vecina] == -1) {
padre[vecina] = ciudad;
colaBfs.push(vecina);
}
}
}
padre[0] = -1;
return padre;
}
// Codifica un numero decimal en numBits columnas binarias.
void codificaEnBits(int numero, int numBits) {
vector<int> bits(numBits);
for (int idx = numBits - 1; idx >= 0; idx--) {
bits[numBits - idx - 1] = numero / (1 << idx);
numero %= (1 << idx);
}
for (int i = 0; i < numBits; i++) {
encode_bit((bool) bits[i]);
}
}
void encode(int numCiudades, int numCentros, int numConexiones, int * v1, int * v2) {
vector<vector<int>> listaAdyacencia(numCiudades);
for (int i = 0; i < numConexiones; i++) {
listaAdyacencia[v1[i]].push_back(v2[i]);
listaAdyacencia[v2[i]].push_back(v1[i]);
}
// Primero, definimos y codificamos los padres de todas las ciudades.
vector<int> padre = definePadres(listaAdyacencia);
for (int i = 1; i < numCiudades; i++) {
codificaEnBits(padre[i], 10);
}
// Encontramos todas las distancias entre centros y ciudades y las codificamos.
vector<vector<int>> distancias = todasLasDistancias(listaAdyacencia, numCentros);
int ciudad, diferenciaDistancias, diferenciasAgregadas;
for (int hub_idx = 0; hub_idx < numCentros; hub_idx++) {
ciudad = 1;
// Codificamos las distancias en grupos de 3 hasta que ya no haya grupos.
while (ciudad + 2 < numCiudades) {
// Al tener 3 diferencias, todas ellas en {0, 1, 2}, podemos codificarlas en 5 bits,
// ya que 2^5 >= 3^3.
diferenciasAgregadas = 0;
for (int diff = 0; diff < 3; diff++) {
diferenciaDistancias = (
distancias[hub_idx][ciudad + diff] - distancias[hub_idx][padre[ciudad + diff]] + 1
);
diferenciasAgregadas = 3 * diferenciasAgregadas + diferenciaDistancias;
}
codificaEnBits(diferenciasAgregadas, 5);
ciudad += 3;
}
// Codificamos el resto de forma aislada.
while (ciudad < numCiudades) {
diferenciaDistancias = distancias[hub_idx][ciudad] - distancias[hub_idx][padre[ciudad]] + 1;
// Como la diferencia es 0, 1 o 2, nos bastan 2 bits para codificarla.
codificaEnBits(diferenciaDistancias, 2);
ciudad++;
}
}
}
#include "grader.h"
#include "decoder.h"
#include <queue>
#include <vector>
using namespace std;
// Descodifica un numero decimal recibido en numBits columnas binarias.
int decode_in_bits(int numBits) {
vector <int> bits(numBits);
for (int i = 0; i < numBits; i++) {
bits[i] = (int) decode_bit();
}
int numero = 0;
for (int idx = numBits - 1; idx >= 0; idx--) {
numero += bits[numBits - idx - 1] * (1 << idx);
}
return numero;
}
// Recupera las distancias desde la fuente al resto de ciudades.
vector<int> recuperarDistancias(
int fuente,
vector<vector<int>> & listaAdyacenciaArbol,
vector<int> & diferenciasDistancia,
vector<int> & padre
) {
// Hacemos una BFS desde la fuente, calculando la distancia total con las diferencias.
vector <int> distancias(listaAdyacenciaArbol.size(), -1);
distancias[fuente] = 0;
queue <int> colaBfs;
colaBfs.push(fuente);
while (!colaBfs.empty()) {
int ciudad = colaBfs.front();
colaBfs.pop();
for (int & vecina: listaAdyacenciaArbol[ciudad]) {
if (distancias[vecina] != -1) {
continue;
}
if (padre[vecina] == ciudad) {
distancias[vecina] = distancias[ciudad] + diferenciasDistancia[vecina];
} else {
// Sabemos que padre[ciudad] == vecina en este caso.
distancias[vecina] = distancias[ciudad] - diferenciasDistancia[ciudad];
}
colaBfs.push(vecina);
}
}
return distancias;
}
void decode(int numCiudades, int numCentros) {
// Primero, reconstruimos el arbol de expansion.
vector<vector<int>> listaAdyacenciaArbol(numCiudades);
vector<int> padre(numCiudades, -1);
for (int i = 1; i < numCiudades; i++) {
int p = decode_in_bits(10);
listaAdyacenciaArbol[p].push_back(i);
listaAdyacenciaArbol[i].push_back(p);
padre[i] = p;
}
// Recuperamos las distancias gracias a las diferencias en el arbol.
vector<vector<int>> distancias(numCentros, vector<int>(numCiudades));
vector<int> diferenciasDistancia(numCiudades);
for (int centro = 0; centro < numCentros; centro++) {
int ciudad = 1, distanciaAgregada;
while (ciudad + 2 < numCiudades) {
distanciaAgregada = decode_in_bits(5);
for (int diff = 2; diff >= 0; diff--) {
diferenciasDistancia[ciudad + diff] = (distanciaAgregada % 3) - 1;
distanciaAgregada /= 3;
}
ciudad += 3;
}
while (ciudad < numCiudades) {
diferenciasDistancia[ciudad] = decode_in_bits(2) - 1;
ciudad++;
}
distancias[centro] = recuperarDistancias(centro, listaAdyacenciaArbol, diferenciasDistancia, padre);
}
// Enviamos las distancias para que el juez las corrija.
for (int centro = 0; centro < numCentros; centro++) {
for (int ciudad = 0; ciudad < numCiudades; ciudad++) {
hops(centro, ciudad, distancias[centro][ciudad]);
}
}
}
