Jurisdiccional 2019 Nivel 2: Organizando el librero

Problemas Nivel 2
#1

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

Librero2.pdf (74,6 KB)

4 Me gusta
#2

con este código las subtareas caso de prueba me dan correctos(no en su totalidad) no entiendo porque no me da puntaje.

les dejo mi código, si alguien me puede ayudar se lo agradezco

#include <vector>
#include <iostream>

using namespace std;

int librero(vector<int> bases, vector<int> libros, vector<int> &orden)
{
    int mayor=0,menor=100000,N,R;
    bool existe;
    N=bases.size();

    for(int i=0;i<N;i++){
        if(bases[i]>mayor){
            mayor=bases[i];
        }
    }

    for(int i=0;i<libros.size();i++){
        if(libros[i]<menor){
            menor=libros[i];
        }
    }

    R=mayor+menor;


   for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
        existe=false;
        if ((bases[i]+libros[j])==R){
                for(int h=0;h<i;h++){
                    if (orden[h]==j){
                        existe =true;break;
                    }
                }
                if (existe==false){
                    orden.push_back(j);
                    break;
        }
        }
    }
   }
                if(orden.size()<N){
                    R=-1;
                }



    return R;
}
1 me gusta
#3

Hola!!!

Hay un problema con la inicialización

menor=100000

Es demasiado pequeño, ya que el enunciado indica que las alturas de los libros y las bases pueden llegar hasta 1.000.000.000. Siempre cuando uno calcula el minimo de esta forma inicializando a un valor especial “INFINITO”, debe asegurarse de que ese INFINITO sea sí o sí mayor a cualquier número posible. En este caso podríamos inicializar por ejemplo con menor=1000001000

Por otro lado, el código tiene 3 fors uno adentro de otro, y en este caso eso causa que la complejidad (cantidad de pasos totales del algoritmo) sea más o menos n^3. Como n puede llegar hasta 100.000 en este problema, es un costo demasiado alto y va a producir tiempo límite excedido. Para resolver ese otro problema, se pueden pensar otras soluciones, por ejemplo ordenando con la función sort, utilizando un vector de bool para marcar si un nodo ya está “adentro” del vector “orden” o no, cosa de no tener que buscar en el momento, o utilizando la estructura “set” de C++.

3 Me gusta