Problema con solución

Estuve tratando de resolver este problema. Cuando lo envío al juez me da 0 puntos por wrong answer en todos los casos, pero no encuentro el problema con mi solución. Capaz no sea la mejor o más limpia, pero me gustaría arreglarla. La dejo acá abajo por si alguien me puede dar una mano. Gracias!

Mi código

#define forn(i,N) for (int i=0;i<N;i++)
#define rforn(i,N) for(int i=N;i>0;i--)

struct persona
{
    int pos, enojo;

    bool operator<(const persona other) const
    {
        if ( enojo < other.enojo )
            return true;

        if ( enojo == other.enojo )
            return pos > other.pos;

        return false;
    }
};

struct Fecha
{
    int dia, mes, anno;
};

const int maxN = 1<<18;

int N;

int segTree[600000];
int positions[600000];
priority_queue <persona> personas;


int findMin( int left, int right, int lsearch, int rsearch , int node ){

    if ( left > rsearch || right < lsearch)
        return -1;

    if (left>=lsearch && right <= rsearch){

        return node;
    }

    int lres = findMin ( left , (left+right)/2 , lsearch , rsearch , node*2 );
    int rres = findMin ( (left+right)/2 + 1 , right , lsearch , rsearch , node*2+1 );

    if (lres > -1 && rres > -1){
        if (segTree[lres] >= segTree[rres]){
            return rres;
        }else{
            return lres;
        }
    }

    if (lres > -1)
        return lres;

    if  (rres > -1)
        return rres;

    return -1;
}

int fila(vector<Fecha> orden, vector<int> &enojados)
{
    int maxEnojo = -maxN*2;

    /// setea todo a infinito
    forn(i,maxN*2){
        segTree[i]=maxN*2;
    }

    /// calcula la edad de cada uno
    forn(i,N){
        
        segTree[i+maxN] = (10000 - orden[i].anno)*10000 + (12-orden[i].mes)*100 + (31 - orden[i].dia);
        positions[i+maxN] = i+1;
    }

    /// calcula los nodos internos del segment tree
    rforn(i,maxN-1){

        if(segTree[2*i] < segTree[2*i+1]){

            segTree[i] = segTree[2*i];
            positions [i] = positions[2*i];

        } else {

            segTree[i] = segTree[2*i+1];
            positions [i] = positions[2*i+1];
        }
    }

    /// calcula el enojo de cada persona
    forn(i,N){

        int enojo = 0;
        int masChico = positions[ findMin( 1 , maxN , 1 , i+1, 1) ]-1;
        
        enojo = i-masChico;
        
        if (segTree[masChico+maxN] >= segTree[i+maxN])
            continue;
            
        forn(j,masChico){
            if ( segTree[j+maxN] < segTree[i+maxN]){

                enojo = i-j;
                break;
            }
        }
        personas.push({i+1,enojo});
        maxEnojo = max(enojo,maxEnojo);
    }

    while ( !personas.empty() ){

        enojados.push_back(personas.top().pos);
        personas.pop();
    }

    return maxEnojo;
}
1 me gusta

Hola, anduve mirando un poquito el código, y me llamó la atención lo siguiente…

:thinking:¿Dónde se inicializa N? :thinking:

Me parece que falta una línea al comenzar la función fila que diga algo como:

N = int(orden.size());

Fijate siempre de correr el ejemplo al resolver un problema (idealmente está bueno correrle además algunos casos pensados por uno donde sepas la respuesta). En este caso, este error debería saltar porque no pasaría el ejemplo.

En el OIAJ, arriba del enunciado del problema hay una solapa que dice “Adjuntos” (en los problemas más nuevos, que hay que implementar una función). Ahí podés descargar el archivo fila-cpp.zip. Al extraerlo aparecen 3 archivos.

  1. El evaluador local (“evaluadorFila.cpp”)
  2. La función a implementar (este es el código que ponés arriba, “fila.cpp”)
  3. Un archivo de entrada (“fila.in”).

Si uno tiene la función que implementa en la misma carpeta que el evaluador, corriendo el evaluador nos muestra la salida que se obtiene. En este caso es algo como:

Con una fila de 8 personas la maxima intensidad de enojo es 3 y su orden:
4 5 8 2 7

El evaluador en este problema lee de stdin. Si uno quisiera que lea de “fila.in”, tendría que agregar una línea en el main del evaluador para que lea del archivo, por ejemplo:

assert(freopen("fila.in", "r", stdin));

Por ahora eso, cualquier cosa, no dudes en preguntar :slight_smile:

2 Me gusta

Hola, gracias por la respuesta! Me resultaba raro porque cuando probaba el caso ejemplo localmente, el output era correcto. Pero tenías razón: agregué esta línea al principio de la función “Fila” y se solucionó:

N = orden.size();

Ahora lo que me gustaría es mejorar la solución (porque me dio 60 puntos por algunos Time Out). Hay alguna manera de hacerla más eficiente? O alguna otra forma de resolver el problema?

Saludos!

Hola!

Qué raro que sin inicializar N diera output correcto. Cuando no sabés qué está pasando podés pedir prints. Por ejemplo un print al calcular los enojos, quizás te imprimía “calculando enojo de la persona 9” y veías que había algo raro.

Fijate que el Time Out viene de cuando concatenás forn(i,N) con forn(j, masChico). Ahí el orden te queda cuadrático en la cantidad de personas, y si querés pensar un ejemplo concreto en el cual hagas muchas operaciones, pensá qué pasa si el más chico está en la posición N/2, los anteriores son muy viejos (90 años ponele), y los que están después del más chico tienen todos 80 años. Para cada i>N/2, buscás el más chico, y te fijás desde el principio hasta ahí si alguno de menos de 80 años, que no lo hay, entonces terminás haciendo para cada uno de estos índices, N/2 operaciones, por lo que tenés O(N/2 * N/2) que es demasiado, y sin contar el findMin en el medio.

Si bien la idea de “busco al más chico anterior a i, porque sé que los que están entre ese y el i no me importan porque quiero al primero que es más joven” puede parecer agilizar la solución fuerzabrutesca, el orden de la complejidad termina siendo el mismo. Está bueno al ver un Time Out analizar “adonde podría llegar a estar ese Time Out”. Quizás juntás dos “fors” que por alguna propiedad particular del problema no se hace cuadrático, pero hay que pensar en el peor caso. En tu código, el peor caso era si el for recorría todas las posiciones, es decir, no encontraba nadie más joven antes que el más joven de todos, de ahí se me ocurrió el ejemplo.

Entonces, si bien no es fácil programar todo un segment tree y lo hiciste prolijamente, la idea no es válida.

Si querés pensá bien qué es lo querrías que el segment tree encuentre (ya que vimos que no es el mínimo de un rango), si lo podés programar, y cualquier cosa pedite pista y te pasamos sin problema por acá :slight_smile:

Saludos!

2 Me gusta

Para probar el problema localmente armé un main en el que sí inicializaba N, pero cuando lo pasé al juez eso se perdió y por eso el error.

Esta solución se me ocurrió como una forma de robar puntos mejorando la complejidad de algunos casos. Es verdad que en muchos otros queda demasiado lenta. Voy a probar de otra manera a ver si me sale, creo que ya se cual es la pista.

Gracias!

Ahh claro primero supuse que lo inicializabas en el main pero después pensé que no.

Bueno ojalá salga, cualquier cosa para está el foroo!

1 me gusta

Ya que estoy, pongo un comentario medio al margen sobre esto que solo sirve para darle un ejemplo concreto a lo que dijo Seba:

Probablemente el ejemplo más claro/conocido donde “dos fors” uno adentro del otro no te queda cuadrático sea el de la Criba de Eratóstenes.

1 me gusta

http://wiki.oia.unsam.edu.ar/algoritmos-oia/enteros/criba-de-eratostenes

2 Me gusta

Ahí cuento otra forma de resolver el problema. Sé que además hay otra forma distinta de resolverlo.

1 me gusta

Hola! Estuve tratando de resolver el problema de otra forma.

Usando un Segment Tree, en vez de buscar a la persona más joven dentro de un rango de posiciones (como hice antes), busco la persona con menor posición dentro de un rango de edades.

Entonces, los “índices” del Segment Tree son las edades de las personas, y los valores son las posiciones de esas personas en la fila original. Este es el código que tengo hasta ahora:

Mi código
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#define forn(i,N) for(int i=0;i<N;i++)
#define rforn(i,N) for(int i=N;i>0;i--)

using namespace std;

const int maxN = 1<<18;

int N; 					/// cantidad de personas
int segTree [600000]; 	/// minima posicion dentro de un rango de edades
int edades[600000];
int personas[300000];

struct Fecha
{
    int dia, mes, anno;
};

struct persona
{
    int edad, enojo;

    bool operator<(const persona other) const
    {
        if ( enojo < other.enojo )
            return true;

        if ( enojo == other.enojo )
            return segTree[edad] > segTree[other.edad];

        return false;
    }
};

priority_queue <persona> prioridades;

void build (){

	forn(i,maxN*2)
		segTree[i] = maxN*2;

	forn(i,N){
        if (segTree[personas[i] + maxN] > i+1 ){

            segTree[personas[i] + maxN] = i+1;
            edades[personas[i] + maxN] = personas[i];
        }
	}

	rforn(i,maxN-1){

        if (segTree[i*2] < segTree[i*2+1]){

            segTree[i] = segTree[i*2];
            edades[i] = edades[i*2];
        } else {

            segTree[i] = segTree[i*2+1];
            edades[i] = edades[i*2+1];
        }
	}

}

int findMin( int qLeft, int qRight, int tLeft, int tRight , int node ){

	if ( qLeft > tRight || qRight < tLeft ){

		return -1;
	}

	if (tLeft == tRight){

        return node;
	}
	if ( tLeft == qLeft && tRight == qRight){

		return node;
	}

	int lRes = findMin ( qLeft , qRight , tLeft , (tLeft + tRight) / 2 , node*2 );
	int rRes = findMin ( qLeft , qRight , (tLeft + tRight)/2 + 1 , tRight , node*2 + 1 );

	if ( lRes > -1 && rRes > -1 ){

		if (segTree[rRes] > segTree[lRes]){
			return lRes;
		} else {
			return rRes;
		}
	}

	if (lRes > -1){
		return lRes;
	}

	if (rRes > -1){
		return rRes;
	}

	return -1;
}

int fila(vector<Fecha> orden, vector<int> &enojados){

	N = orden.size();
	int maxEnojo = 0;

	forn(i,N){

		personas[i] = (10-orden[i].anno)*10000 + (12-orden[i].mes) * 100 + (31-orden[i].dia);
	}

    build();

    forn(i,N){

        int actualPos = segTree[ personas[i]+maxN];
        int minPos = segTree[ findMin ( 2 , personas[i] , 1, maxN, 1) ];

        if ( actualPos > minPos ){
            int enojo = actualPos - minPos;
            prioridades.push({ personas[i]+maxN , enojo });
            maxEnojo = max( enojo, maxEnojo);
        }
    }

    while(!prioridades.empty()){

        enojados.push_back( segTree[ prioridades.top().edad ] );
        prioridades.pop();
    }

    return maxEnojo;
}


int main()
{
    freopen("entrada.txt","r",stdin);
    int C; cin >> C;
    vector<Fecha> v(C);

    forn (i,C)
        cin >> v[i].dia >> v[i].mes >> v[i].anno;

    vector<int> enojados;

    cout << "Con una fila de " << C << " personas la maxima intensidad de enojo es ";
    cout << fila(v, enojados) << " y su orden:" << endl;
    forn (i,int(enojados.size()))
    {
        if (i) cout << " ";
        cout << enojados[i];
    }
    cout << endl;
    return 0;
}

A medida que lo fui haciendo, encontré algunos problemas:

  1. Los índices son demasiado grandes y debería “comprimirlos” de alguna forma.
  2. Mi función “findMin” funciona mal y, si quiero buscar a la persona con la menor posición que tenga una edad entre, por ejemplo, 1 y 10, por algún motivo que no puedo resolver tengo que llamar a la función con 2 como edad mínima y 11 como edad máxima para obtener el resultado que espero (les sumo 1 a ambos).

Espero que me puedan ayudar. Gracias!

1 me gusta

Me gusta que hayas puesto un par de líneas antes del código contando la idea. :grinning:

Lo de buscar a la persona de menor índice en un rango de edades está muy bien.

Dada una fecha de la forma (\text{año},\text{mes}, \text{día}) entiendo que lo estás llevando a un número de 8 cifras, de la forma :

(\text{año},\text{mes}, \text{día}) \rightarrow \underbrace{10000-\text{año}}_{\text{4 cifras}}|\underbrace{12-\text{mes}}_{\text{2 cifras}}|\underbrace{31-\text{día}}_{\text{2 cifras}}

En realidad en el código en vez de 10000 tenés un 10, que creo que es un bug. Si llamamos h a esa transformación, la gracia es que ahora una persona i es más joven que una persona j, si y solo si h(a_i,m_i,d_i) < h(a_j,m_j,d_j). Me gustó esta idea, pero, como vos decís, va a haber que comprimir estos números si queremos que sean las hojas de nuestro segment tree.

Seguro hay formas más elegantes, pero una forma de comprimirlas es la siguiente: podés tener a las personas como un par (i, h(a_i,m_i,d_i)), donde i es el índice en la fila. Ahora podés ordenar a estos pares, comparando primero por la segunda coordenada. Fijate que en realidad no hace falta la h, podés comparar directamente las tuplas de (\text{año},\text{mes}, \text{día}) y se comparan lugar a lugar.

Una vez ordenados, podés cambiar las segundas coordenadas por 1,2,3, \dots. Si querés volver al orden original, podés volver a ordenarlos por la primera. Puede ayudar pasar como tercer parámetro a \texttt{sort} una función de comparación :wink:

Me gusta que la forma en que lo estás resolviendo es re geométrica. Básicamente si pensás a las personas como un par ordenado en el plano (i,e_i) = (\text{índice},\text{edad}) (notar que a menor edad, más joven).

Entonces al mirar a la persona i, lo enojan las personas de menor edad que están a la izquierda. La que realiza el mayor nivel de enojo, será la que esté más a la izquierda (pero siempre de menor edad). Geométricamente se ve da la siguiente forma:

Después miro lo de \texttt{findMin} y edito este post, si no lo encontrás antes.

Edit: Ya lo miré. En un post de más abajo está la respuesta.

2 Me gusta

Gracias por la respuesta! Que bueno estar en el camino correcto.

Ese 10 lo puse para probar si las cosas funcionaban, porque usando un 10000 se rompía el código (tratando de acceder a posiciones muy grandes del array).

Muy buena la forma de pensarlo geomtricamente!

Voy a probar de ordenar a las personas como dijiste (eso no va a empeorar mucho el tiempo de ejecución, o sí?) y veo cómo queda.

Todavía no encontré el problema (capaz ni siquiera esté en findMin y hay un error en build() o algo así.

Saludos!

Fijate de que corra bien en un ejemplo donde dos personas tengan la misma edad. La forma que te dije de comprimir va a funcionar bien si no hay dos personas que tengan la misma edad, o al menos hay que tener más cuidado que usar solo la función h para usar ese orden.

Básicamente si hay dos personas con la misma edad hay que considerar más joven en este nuevo orden comprimido a la que está más a la derecha (para que no la enoje la que está más a la izquierda, porque no es realmente más joven).

Perdón por no aclarar esto en el post anterior.:sweat_smile:

La complejidad asintótica queda \mathcal{O}(n \lg(n)), donde n es la cantidad de personas (estoy suponiendo que uno ordena en \mathcal{O}(n\lg(n)), por ejemplo con \texttt{sort} de C++.). Lo cual debería entrar porque n \leq 3 \cdot 10^5

De todas formas, además de ordenar, uno también paga \mathcal{O}(n) operaciones de Segment Tree que cuestan \mathcal{O}(\lg(n)) en este caso.

Así que la complejidad asintótica “pinta bien”, aunque quizá la constante no sea la más linda que hay.

Por las dudas, recién mandé al juez una implementación de tu idea y entra (sin sobrarle mucho) en el límite de tiempo.

Estuve probando lo que dijiste, pero solamente saque 19 puntos, en algunos casos fue output incorrecto y en otros timeout.

Mi codigo
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#define forn(i,N) for(int i=0;i<N;i++)
#define rforn(i,N) for(int i=N;i>0;i--)

using namespace std;

const int maxN = 1<<18;

int N; 					/// cantidad de personas
int segTree [1000000]; 	/// minima posicion dentro de un rango de edades
int edades[1000000];
int personas[300000];
int ordenado[300000];

struct Fecha
{
    int dia, mes, anno;
};

struct persona
{
    int edad, enojo;

    bool operator<(const persona other) const
    {
        if ( enojo < other.enojo )
            return true;

        if ( enojo == other.enojo )
            return segTree[edad] > segTree[other.edad];

        return false;
    }
};

priority_queue <persona> prioridades;

void build (){

	forn(i,maxN*2)
		segTree[i] = maxN*2;

	forn(i,N){
        if (segTree[personas[i] + maxN] > i+1 ){

            segTree[personas[i] + maxN] = i+1;
            edades[personas[i] + maxN] = personas[i];
        }
	}

	rforn(i,maxN-1){

        if (segTree[i*2] < segTree[i*2+1]){

            segTree[i] = segTree[i*2];
            edades[i] = edades[i*2];
        } else {

            segTree[i] = segTree[i*2+1];
            edades[i] = edades[i*2+1];
        }
	}
}

bool sortBool ( int a , int b ){

    return (personas[a] < personas[b]);
}

void sortPersonas(){

    sort( ordenado , ordenado+N , sortBool );
    int diff = 0;
    int diffBuffer = 0;
    forn(i,N){
        diffBuffer = diff;
        if ( i<N-1 && personas[ordenado[i]] == personas[ordenado[i+1]]){
            diffBuffer++;
        }
        personas[ ordenado[i] ] = 1+i-diff;
        diff = diffBuffer;
    }
}

int findMin( int qLeft, int qRight, int tLeft, int tRight , int node ){

	if ( qLeft > tRight || qRight < tLeft ){

		return -1;
	}

	if (tLeft == tRight){

        return node;
	}
	if ( tLeft == qLeft && tRight == qRight){

		return node;
	}

	int lRes = findMin ( qLeft , qRight , tLeft , (tLeft + tRight) / 2 , node*2 );
	int rRes = findMin ( qLeft , qRight , (tLeft + tRight)/2 + 1 , tRight , node*2 + 1 );

	if ( lRes > -1 && rRes > -1 ){

		if (segTree[rRes] > segTree[lRes]){
			return lRes;
		} else {
			return rRes;
		}
	}

	if (lRes > -1){
		return lRes;
	}

	if (rRes > -1){
		return rRes;
	}

	return -1;
}

int fila(vector<Fecha> orden, vector<int> &enojados){

	N = orden.size();
	int maxEnojo = 0;

	forn(i,N){

		personas[i] = (10000-orden[i].anno)*10000 + (12-orden[i].mes) * 100 + (31-orden[i].dia);
		ordenado[i] = i;
	}

	sortPersonas();
    build();

    forn(i,N){

        int actualPos = segTree[ personas[i]+maxN];
        int minPos = segTree[ findMin ( 1 , personas[i] , 1, maxN, 1) ];

        if ( actualPos > minPos ){
            int enojo = actualPos - minPos;
            prioridades.push({ personas[i]+maxN , enojo });
            maxEnojo = max( enojo, maxEnojo);
        }
    }

    while(!prioridades.empty()){

        enojados.push_back( segTree[ prioridades.top().edad ] );
        prioridades.pop();
    }

    return maxEnojo;
}

Voy a tratar de explicar lo que quise hacer con la función sortPersonas. Básicamente, tengo un array de N posiciones (siendo N la cantidad de personas) e inicializo cada casillero con el valor de su indice. Cada uno de esos valores hace referencia a una persona. Entonces, ordeno esos valores segun la edad de la persona a la que hacen referencia. Despus recorro el array ordenado. En el primer casillero de ese array, por ejemplo, voy a tener almacenada la posicion de la persona mas joven. A esa persona (en el array “personas”) le asigno una nueva edad (en este caso 1, por ser la primera posicion). A esa edad le resto una especie de “offset” que se va acumulando a medida que encuentro personas con la misma edad, para que al asignarles su nueva edad se siga manteniendo la igualdad.

Lo que me parece raro es que el programa tarda mucho en correrse localmente, aunque son casos chicos (unas 8 personas). Capaz estoy pasando algo por alto.

int minPos = segTree[ findMin ( 1 , personas[i] , 1, maxN, 1) ];

Más raro todavía es que ahora cuando llamo a “findMin” para hacer, por ejemplo, una búsqueda entre 1 y 5, tengo que llamar con 1 como mínimo y 6 como máximo (al menos en los casos que probé, y solamente haciendo ese cambio en el llamado inicial, adentro de “fila”). La llamada correcta en la línea de arriba sería, según pensé, la siguiente:

int minPos = segTree[ findMin ( 1 , personas[i]-1 , 1, maxN, 1) ];

Porque 1 es la edad mínima de cualquier persona, y la edad más alta que me interesa es la de esa persona menos 1 (cualquiera más joven).

Saludos!

¿Quizá te tarda mucho en pedir la memoria de los arreglos globales? Después miro bien el código y te digo.

Edit: Ahí miré. Primero, hablando de arreglos globales, ese \texttt{maxN} = 2^{18} = 262144 < 3 \cdot 10^5, por lo tanto no es lo suficientemente grande en el peor de los casos.

El problema por el que tarda mucho está en \texttt{findMin}. Al hacer la query a un segment tree, uno devuelve el nodo como está cuando ese nodo está totalmente contenido en el intervalo de la query. Básicamente, en el código hay que cambiar esta línea:

if ( tLeft == qLeft && tRight == qRight){
		return node;
	}

por esta otra:

if ( tLeft >= qLeft && tRight <= qRight){
		return node;
	}

Así corta ni bien el nodo que representa [\texttt{tLeft}, \texttt{tRight}) está contendio en [\texttt{qLeft}, \texttt{qRight})


Insisto, no miré el código del segment tree todavía, pero así funciona normalmente cuando uno piensa a los intervalos con la convención “cerrado-abierto”. Tenés que poner 1 y 6, porque estás buscando en el intervalo [1,6), que en enteros es lo mismo que el [1,5]. Supongo que tu sorpresa quiere decir que trabajaste “cerrado-cerrado”.


Le corrí este ejemplo:

3
1 1 4
1 1 2
1 1 2

Y el evaluador me devuelve esto:

Con una fila de 3 personas la maxima intensidad de enojo es 1 y su orden:
2 2

Sin embargo, el máximo enojo debería ser 2 y la fila de enojados debería ser 3 2

Ahora lo miro bien en detalle a ver qué está pasando (voy a mirar ese segment tree…).


Edit: Además de lo que te marqué en \texttt{findMin} y con las cotas globales, hay algo que me hace ruido. Al iterar por fila, uno sabe el índice de la persona con el mismo i que itera en el for. No veo por qué intentar acceder vía el segment tree. Además esto traía problemas en el ejemplito que te mostré antes donde hay dos enojados con la misma edad. Lo que digo es que en vez de:

int actualPos = segTree[personas[i]+maxN];

es más natural poner:

int actualPos = i+1;

Lo otro que me llamó la atención fue el struct persona, porque solo lo usás para ordenar la salida, para lo cual necesitás la posición en la fila (que la tenés, es actualPos) y el enojo (que lo tenés, es actualPos - minPos).

Entonces creo que sería mejor poner (además nos ahorramos pasar por el segment tree).

struct persona
{
    int pos, enojo;
    bool operator<(const persona other) const
    {
        if ( enojo < other.enojo )
            return true;

        if ( enojo == other.enojo )
            return pos > other.pos;

        return false;
    }
};

Luego, en el for tendríamos que poner:

prioridades.push({ actualPos , enojo });

Y al imprimir la respuesta:

enojados.push_back( prioridades.top().pos );

Fijate que nos ahorramos de preguntar por un índice cósmico en el segment tree.

Creo que con eso está todo. Lo más importante es lo del nodo en el Segment Tree.

3 Me gusta

Hola! Perdón por tardar en responder, estuve de vacaciones.

Con los cambios que dijiste da 96 puntos! Así que solamente me queda encontrar ese caso que el programa no resuelve.

Sobre lo de las cotas, 262144 es la mayor potencia de dos que el evaluador me deja correr. Con 1<<18 funcionó bien.

Igualmente, no entiendo por qué el puntaje es otro cuando intento acceder a través del segment tree en vez de usar el índice del for.

Gracias por la ayuda y por dedicarle tanto a la respuesta. Saludos!

1 me gusta