Jurisdiccional 2019 Nivel 3: Organizando el librero

Problemas Nivel 3
#1

Hago este post para que discutamos ideas sobre “Organizando el librero”.

Librero3.pdf (76,3 KB)

3 Me gusta
#2

En este problema había que tener en cuenta bastantes detalles para llegar a los 100 puntos.

  • Primero que nada, había que darse cuenta de que el libro más chico siempre debía ir con la base más grande y viceversa. De esta manera, el posible resultado sería la suma de la altura del libro más chico y la altura de la base más grande. Luego basta comprobar si para el resto de libros y bases se llega a esa suma.
Código 
int n = libros.size();
sort(libros.begin(), libros.end());
sort(bases.rbegin(), bases.rend());
int altura = libros[0] + bases[0];
for(int i = 0; i < n; i++){
    if(libros[i] + bases[i] != altura){
        altura = -1;
        break;
    }
}
  • Lo de arriba sirve pero, para el puntaje parcial de 20% ya que quedan por hacer algunas cosas como dar un ordenamiento posible. Al ordenarlos se pierde la id de cada libro y base. Para evitar esto hay se antes de ordenar todo se debe adjuntar la id a cada elemento y luego mientras se va comprobando si el valor altura es posible, se va escribiendo la id del libro sobre la id de la base en el arreglo.
Código 
int n = libros.size();
vector<pair<int, int> > lord(n), bord(n);
for(int i = 0; i < n; i++){
    lord[i] = {libros[i], i + 1}; //El + 1 es porque los libros son 1-indexed
    bord[i] = {bases[i], i}; //En cambio las bases son 0-indexed por el arreglo
}
sort(lord.begin(), lord.end());
sort(bord.rbegin(), bord.rend());
int altura = lord[0].first + bord[0].first;
for(int i = 0; i < n; i++){
    if(lord[i].first + bord[i].first != posible){
        altura = -1;
        orden.clear();
        break;
    }
    orden[bord[i].second] = lord[i].second;
}
  • Al momento de calcular la cantidad de ordenamientos existentes hay que ser más cuidadoso. Si bien, el arreglo devuelve 2 enteros como resultado, el enunciado pide la cantidad módulo {10^9 + 7} por lo que nos indica que el valor se puede ir cantidades gigantes. Otra cosa que hay que detectar es cómo se obtiene un ordenamiento diferente, que si ya tenemos la cantidad altura, es evidente que en cada base se puede ubicar únicamente otro libro de la misma altura. Y como todo está ordenado se puede reconocer cuáles y cuántos libros tienen una misma altura. Y entonces solo basta permutar: Claramente no es posible hacer permutaciones reales sino que se obtienen a partir del factorial (Combinaciones de N elementos = {N!}).
Código final 
#include<bits/stdc++.h>
using namespace std;
const ll mod = 1000000007;
vector<int> librero(vector<int> bases, vector<int> libros, vector<int> &orden){
    vector<int> respuestas(2);
    int n = libros.size();
    vector<pair<int, int> > lord(n), bord(n);
    for(int i = 0; i < n; i++){
        lord[i] = {libros[i], i + 1}; //El + 1 es porque los libros son 1-indexed
        bord[i] = {bases[i], i}; //En cambio las bases son 0-indexed por el arreglo
    }
    sort(lord.begin(), lord.end());
    sort(bord.rbegin(), bord.rend());
    lord.push_back({-1, -1}); //Para evitar el bug de preguntar por una posicion siguiente inexistente
    int altura = lord[0].first + bord[0].first;
    int repeticiones = 1;
    ll ordenamientos = 1;
    for(int i = 0; i < n; i++){
        if(lord[i].first + bord[i].first != posible){
            altura = -1;
            ordenamientos = 0;
            orden.clear();
            break;
        }
        orden[bord[i].second] = lord[i].second;
        if(lord[i].first == lord[i + 1].first){
            repeticiones++;
        } else{
            ll factorial = 1;
            for(int i = 2; i <= repeticiones; i++){
                factorial *= i;
                factorial %= mod;
            }
            ordenamientos *= factorial;
            ordenamientos %= mod;
            //Importantes los % en cada multiplicacion
        }
    }
    respuestas[0] = altura;
    respuestas[1] = int(ordenamientos);
    return respuestas;
}

Acá unas aclaraciones extras del algoritmo:

  • Analizando la complejidad a simple vista pareciera que es {\mathcal{O}(N^2)} por los dos for anidados. Puede parecer que en peor de los casos funciona en, como dije anteriormente, {\mathcal{O}(N^2)} que con una N que puede llegar a {10^5} no entra. Pero en realidad esto no pasa nunca ya que si se mira bien la sumatoria de las repeticiones que realiza el bucle de adentro siempre es N quedando en una complejidad de {\mathcal{O}(2N)} que, ignorando la constante sería {\mathcal{O}(N)}.
  • Como el número de ordenamientos y factorial se pueden ir a números grandes es importante aplicarle al módulo en cada operación.
  • En este caso, cuando se buscan las repeticiones adyacentes, se hace fijándose en el siguiente libro, por lo que se debe agregar un libro ficticio para evitar acceder a posiciones no existentes (lord.push_back({-1, -1});).
    Bueno, hasta acá toda mi explicación con las observaciones que tuve que hacer en competencia. Espero que ayude a alguien.
5 Me gusta
#3

¡¡Excelente!! ¡¡Está super bien explicado!!! :heart_eyes:

Yo no lo pensé ordenando, que ahora que lo veo es mucho más lógico y simple, sino que hice algo diferente :stuck_out_tongue:

Me imaginé el dibujo del librero, como el del enunciado. Si el dibujo está bien armado, todos quedan alineados y entonces “se forma un rectángulo”: Ese rectángulo tiene base “N” (cantidad de libros, que es igual a cantidad de bases), y altura “H”, la altura misteriosa buscada. Y tiene un “área” igual a la sumatoria de todas las bases y todos los libros del input. Entonces hago esta sumatoria y divido por N (si no es múltiplo, ya es imposible) y así obtengo el H, que es el único valor posible.

Si solo pidieran el H ya sabiendo que es posible, con esto el problema entero fue una sumita y división :smiley: (creo que es una subtarea esto).

Para determinar un emparejamiento, ahora la gracia es que sabiendo el H, los emparejamientos son “forzados” en cuanto a valor: A un libro de altura x, solamente lo podemos poner en un estante de altura H-x. Así que podemos hacer un “histograma” para contar cuántos libros y bases hay con cada altura (puede ser en arreglo en nivel 1, o puede ser un map de int a int en otros niveles). Si para alguna altura de libro x no coinciden la cantidad de libros con x y las de bases con H-x, es imposible.

Y finalmente para dar el emparejamiento en sí, se puede proceder golosamente, solo hay que cambiar el “histograma” por un map de int a lista de enteros, con los índices de los libros / bases que tienen esas alturas, e ir armando las parejas golosamente cuando aparecen (por ejemplo con pop_back en esas listas).

La parte de contar sí es igual, con los factoriales :slight_smile:

5 Me gusta