Cuatro problemas de selectivo

De varios temas y dificultades diferentes:

http://juez.oia.unsam.edu.ar/#/task/clima/statement
http://juez.oia.unsam.edu.ar/#/task/tesoro/statement
http://juez.oia.unsam.edu.ar/#/task/zapallos/statement
http://juez.oia.unsam.edu.ar/#/task/billar/statement

5 Me gusta

Buenas, una consulta.

Cuando dice: “el lugar más hostil para vivir, será aquél que sea más hostil respecto a la mayor cantidad de lugares con los que sea comparable.”

Se refiere a que el lugar con el coeficiente mas alto de (veces que es un lugar hostil) / (lugares comparables) sería el más hostil?

1 me gusta

Yo también lo interpreté mal, pero después me aclararon la duda.
Supongamos que A es hostil con otras 3 estaciones, B es hostil con otras 2 y C lo es con otras 3.
Los más hostiles son A y C, que tienen el mayor número de hostilidades con respecto a todas las demás. B es hostil, pero no es lo máximo de hostilidad, ese no entraría en la respuesta.
Espero que te ayude

3 Me gusta

Alguno tiene casos complicados para probar en el problema del clima?

Estuve probando con varios casos mios pero no encuentro casos erroneos y sin embargo tengo 35/100 puntos en el Juez Online.

Codigo por si quieren probar con algunas casos:
    #include<bits/stdc++.h>

    #define forn(n) for(int i = 1; i <= n; i++)

    using namespace std;

    int main(){
    	ifstream fin("clima.in");
    	ofstream fout("clima.out");
    	
    	int P;
    	fin >> P;
    	
    	vector<pair<int, int> > reg[P+1];
    	pair<int, int> temp[P+1];
    	int noComp[P+1], res[P+1];
    	memset(noComp, 0, (P+1)*sizeof(int));
    	memset(res, 0, (P+1)*sizeof(int));
    	
    	forn(P){
    		int R;
    		fin >> R;
    		for(int i2 = 1; i2 <= R; i2++){
    			int minT, maxT;
    			fin >> minT >> maxT;			
    			reg[i].push_back({minT, maxT});
    		}
    	}
    	
    	// Get the max/min tempature from each regist
    	forn(P){
    		int maxT = -51, minT = 61;
    		for(int i2 = 0; i2 < reg[i].size(); i2++){
    			if(minT > reg[i][i2].first)
    				minT = reg[i][i2].first;
    				
    			if(maxT < reg[i][i2].second)
    				maxT = reg[i][i2].second;
    		}
    		temp[i] = {minT, maxT};
    	}
    	
    	// Compare places
    	forn(P){
    		for(int i2 = i+1; i2 <= P; i2++){
    			if(temp[i2].first == temp[i].first && temp[i2].second == temp[i].second)
    				break;
    			
    			if(temp[i].first <= temp[i2].first && temp[i].second >= temp[i2].second)
    				res[i]++;
    			else if(temp[i2].first <= temp[i].first && temp[i2].second >= temp[i].second)
    				res[i2]++;
    			else 
    				noComp[i]++, noComp[i2]++;
    		}
    	}
    	
    	
    	// Get maximum num of compatible places
    	double maxCom = 0;	
    	forn(P){
    		if(maxCom < res[i])
    			maxCom = res[i];
    	}
    	
    	// Show best places
    	forn(P){
    		if(maxCom == res[i])
    			fout << i << " " << noComp[i] << endl;
    	}
    }
2 Me gusta

Fijate ahí. Me parece que querés un \color{cyan}\texttt{continue} en vez de un \color{cyan}\texttt{break}.

Cuando hacés \color{cyan}\texttt{break} salís del segundo for y dejás de comparar contra los que siguen.

2 Me gusta

Me gusta que uses las macros, pero te voy a dar una recomendación.

Definí la macro

#define forn(i, n) for(int i = 0; i < int(n); i++)

de esta forma, además de parametrizar la cantidad de iteraciones, parametrizamos la variable que indexa.
entonces uno puede escribir

forn(i, 10){
    forn (j, 10) {

    }
}

Yo no introduciría el forn sin pasarle la variable para indexar porque eso nos podria introducir “bugs ocultos” por no ser suficientemente declarativos y esconder cosas en la macro. En este caso, escondemos una declaración de variables

Por ejemplo, este código tendría un error oculto usando tu macro

int i = 24;
forn(10){
	cout << i << endl;
}

Un lector cualquiera asumiría que este código escribe 10 veces el número 24, pero se encontraría con que imprime los números del 1 al 10.

En general el objetivo de las macros no es escribir menos caracteres, si no escribir código que evite bugs simples por repetición o copy-paste.

for(int i=0;i<n;i++){
    for(int j=0;j<m;i++){

   }
}

Ese código tiene un bug no evidente, en el segundo for incrementa i en vez de j.
En cambio, usando la macro forn como la definimos más arriba, sería

forn(i, n) {
   forn(j, m) {
        
   }
}

¡Donde ese bug es simplemente imposible de escribir!

Por otro lado, notar que usé el intervalo [0, n)
En general es conveniente por muchos motivos. En este caso porque los arreglos y vectores se indexan desde 0 en C++.
Otra ventaja que tiene usar intervalos de esa forma es que uno puedo dividir el intervalo en
[0, k) [k, n) en vez de [0,k-1][k, n-1] que tiene -1 y +1 por todos lados y nos puede traer errores.

4 Me gusta

Yo estaría igual que @michaelszer :sweat_smile::sweat_smile::sweat_smile:
Igual también tengo muchos casos donde excede el limite de tiempo, pero otros son por error de output y estuve probando con bastantes casos diferentes y todos me dan bien, y no se me ocurre por ese lado donde puede estar fallando.
Yo tengo 65/100 puntos en el juez, dejo también mi codigo por si a alguien se le ocurre algo :stuck_out_tongue: :

Codigo:
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
#include <iostream>

#define INF 9999999

using namespace std;

int main()
{
	ifstream cin ("clima.in");
	ofstream cout("clima.out");
	
	int cant;
	cin >> cant; 
	
	vector<int> minimo(cant + 1, INF);   //Guardo minimo valor tomado para cada lugar
	vector<int> maximo(cant + 1, -1);    //Guardo maximo valor tomado para cada lugar
	
	for(int i = 1; i < cant + 1; i++)
	{
	    int mediciones;
	    cin >> mediciones;
	    for(int j = 0; j < mediciones; j++)
	    {
	        int mini, maxi;
	        cin >> mini >> maxi;
	        minimo[i] = min(minimo[i], mini);
	        maximo[i] = max(maximo[i], maxi);
	    }
	}
	
	vector<int> hostilidad(cant + 1, 0);    //Guardo la hostilidad de cada lugar
	vector< vector <int> > revhostilidad;   //Dada una hostilidad veo todos los lugares la tienen
	vector<int> incomparable(cant + 1, 0); //Guardo con cuantos lugares es incomparable c/ lugar
	
	
	int maxhosti = -1;  //Mayor hostilidad encontrada
	
	for(int i = 1; i <= cant; i++)
	{
		for(int j = 1; j <= cant; j++)
		{
			if(j == i)
			{
				
			}
			else if(minimo[i] > minimo[j] && maximo[i] > maximo[j])
			{
				incomparable[i]++;
			}
			else if(minimo[i] < minimo[j] && maximo[i] < maximo[j])
			{
				incomparable[i]++;
			}
			else if(minimo[i] < minimo[j] && maximo[i] > maximo[j])
			{
				hostilidad[i]++;
			}
			else if(minimo[i] < minimo[j] && maximo[i] == maximo[j])
			{
				hostilidad[i]++;
			}
			else if(minimo[i] == minimo[j] && maximo[i] > maximo[j])
			{
				hostilidad[i]++;
			}
		}
		
		maxhosti = max(maxhosti, hostilidad[i]);
		revhostilidad.resize(maxhosti + 1);
		revhostilidad[ hostilidad[i] ].push_back(i);
	}
	
	int largo = int(revhostilidad.size()) - 1;
	
      // Me fijo en la parte de los más hostiles y hago un sort para que ya esten ordenados los lugares

	sort(revhostilidad[largo].begin(), revhostilidad[largo].begin() + revhostilidad[largo].size());
	
	for(int i = 0; i < int(revhostilidad[largo].size()); i++)
	{
		int num = revhostilidad[largo][i];
		cout << num << " " << incomparable[num] << endl;
	}
	
}

2 Me gusta

Ojo. Podría ser que la máxima temperatura máxima de una estación sea un número negativo más chico que \color{red}-1 y ahí no lo estás viendo. Por las cotas del enunciado, debería alcanzar poner un -51. Igual siempre le podés dar changüí, y ponerle un número bastante más groso, tipo -128 “por las dudas”. Importante ver con mucho cuidado las cotas del enunciado.

El resto me parece correcto… igual es normal por lo que hacés que te de “time out” en algunos casos (por la misma razón que a @michaelszer ).

SPOILER: Pista para evitar el time out

¿Cuántas estaciones meteorológicas realmente distintas puede haber por las cotas del enunciado?

¡¡Me encantó el post de @brianbok sobre mi macro favorita :heart_eyes:!! Si quieren leer más sobre \texttt{forn} y otras macros para programación competitiva pueden leer el post en la Wiki que está muy bueno :wink:

4 Me gusta

no había visto ese bug.
Ya que tenes definido INF, podes inicializar maximo en -INF, que tiene mucho sentido

2 Me gusta

Graciaaas, sip, eso solucionó todo. Ahora solo me queda mejorar los tiempos, mañana sigo con el programa :smile::smile:.

1 me gusta

Gracias, no me había dado cuenta de esa observación.
Con eso salio el problema de una.

1 me gusta

Me alegro que te haya salido. Si tenes ganas podes publicar tu solución con alguna explicación, escondido en una solapa de Spoiler

2 Me gusta

Muchas gracias por la pista! Pude resolverlo :grin:

2 Me gusta

Zapallos (solución)

Intento 1 (que no es solución)

Un primer intento sería probar todas las posibilidades. Esto es, la solución final solo depende de cuántas cajas le compramos a cada agricultor. Ahora, ¿cuántas formas de hacer esto hay? Esto no hace a la solución, pero creo que es un análisis interesante de hacer.

Una forma de contar esto es imaginar que ponemos una bolita “\circ” por cada caja. Ahora lo que podemos hacer es ubicar A separadores “|”. Por ejemplo, si tenemos 7 cajas y 3 agricultores, una disposición posible es:

\underset{\text{Agricultor ficticio}}{\underbrace{ \circ \quad \circ}} | \underset{\text{Agricultor 1}}{\underbrace{ \circ \quad \circ \quad \circ}}|\underset{\text{Agricultor 2}}{\underbrace{ \quad \quad}}|\underset{\text{Agricultor 3}}{\underbrace{ \circ \quad \circ}}

El “Agricultor ficticio” es porque si bien tenemos hasta 7 cajas, podríamos comprar solo 5 en total. Si no nos gusta la figura de un “Agricultor ficticio”, podemos pensar que son las cajas que dejamos afuera.

Entonces, la cantidad de formas será igual a la cantidad de formas de ubicar los separadores en las bolitas. Esto es: \frac{10!}{3!7!}, (Recordar que n! es la cantidad de permutaciones de una palabra que tiene n letras. En nuestro caso podemos pensar a la palabra de 10 letras AAABBBBBBB, pero, necesitamos dividir por todas las permutaciones posibles entre las A's y las B's, para no contar palabras repetidas).

En general, nos queda que en el problema hay (llamo S = \sum_{a = 1}^A K_a \leq A \cdot 1200 \leq 240000)

\frac{\left (A + S\right ) !}{A!S!} = \frac{(A+S)\cdot(A+S-1)\cdots(S+1)}{A!}

Lo cual en el peor caso nos da algo así como: \frac{(240000)^{20}}{20!}. Lo cual obviamente es mucho (igual esta cota es muy burda, porque no usa que tenemos un límite M de cajas a utilizar, pero me servía más así para exponer la idea de “bolitas y separadores”).

¿Cómo hacemos entonces para resolver el problema?

Intento 2 (que sí es solución)

Por comodidad, vamos a precomputar para cada agricultor a, en qué ganancia/pérdida se incurre por comprar i cajas \forall \hspace{3pt} 1 \leq i \leq K[a] (para todas las cajas).

La idea es aprovechar la estructura que tiene el proceso que se realiza. Uno primero le compra una cierta cantidad al primer agricultor, luego otra cantidad al segundo, etc. Como siempre, lo mejor para esto es hacerse un dibujito.

Ahora, inicialmente tenemos un límite de M cajas para comprar, entonces cuando uno le va a comprar a un cierto agricultor, la cantidad de cajas que le podrá comprar, dependerá de cuántas se haya gastado en los agricultores anteriores. Teniendo esto, podemos describir el proceso.

BEST(a,m) = \text{"Lo mejor que puedo hacer comprando hasta el } \\ a \text{-ésimo agricultor, si todavía puedo meter } m \text{ cajas en el camión"}.

En el dibujito anterior, esto puede verse como: BEST(a,m) = "La mayor ganancia con la que puedo llegar al nodo “a.0”, sobrándome m cajas

Si estoy parado en a.0, ¿de dónde puedo venir? O mejor dicho, ¿De quiénes se necesitan conocer los valores para responder BEST(a,m)?

Sí o sí uno viene de comprarle al agricultor anterior, y va a depender de cuántas cajas le compró al agricultor anterior, de dónde venimos (estamos viendo en el dibujo las aristas que llegan a a.0).

Entonces, si estamos en (a,m) podemos venir de:

  • (a-1,m) : Esto significa que no le compramos nada al agricultor a-1.
  • (a-1,m+1) : Esto significa que le compramos 1 caja al agricultor a-1.
  • (a-1,m+j): Esto significa que le compramos j cajas al agricultor a-1.
  • (a-1,m+K[a-1]) : Esto significa que le compramos todas las cajas al agricultor a-1.

En realidad hay que tener en cuenta un par de cosas:

  • En ninguno de esos casos puede pasar que que m+j sea mayor que M. Porque de ser así, quiere decir que en algún momento dispusimos de más de M cajas.
  • Si venimos de (a-1,m+j), entonces la ganancia sería BEST(a-1,m+j) + gananciaPorComprar(a-1,j) (O sea, la ganancia o pérdida en la que se incurre por comprarle j cajas al agricultor a-1).
  • Bueno, y no olvidarnos que de todas las opciones queremos la que de más grande (más ganancia).

Bueno, esta es una forma de plantear el problema y resolverlo. Se enmarca dentro de lo que es Programación Dinámica, les dejo el post en la wiki que está muy bueno.

Un detalle de implementación, quizá quede cómodo agregar un agricultor ficticio al principio y al final. Así la respuesta nos queda en:

\underset{0 \leq m \leq M}{\text{arg max}} \hspace{2pt} BEST(A+1,m)

Nos quedaría el dibujo de la siguiente figura. Además por lo que pide el problema, debemos recordar dónde se realizó cada máximo para reconstruir el camino (cuántas cajas se le compran a cada agricultor).

3 Me gusta

Hola buenas. Intenté resolver el primer problema de este envío de la forma más “simple” posible.
Lo malo es que el evaluador me devuelve “Execution killed with signal 11” en muchos casos, “wrong answer” en otros, y solamente pasa unos pocos casos (25 puntos).

No encuentro dónde estoy accediendo a alguna dirección de memoria no declarada, ni por qué mi programa no resuelve algunos casos. Me gustaría que alguien me dijera en qué falla mi lógica. Dejo mi código y explico un poco lo que quise hacer:

Código
#include <iostream>
#include <vector>
#include <cstdio>

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

using namespace std;

struct station{

    int minimum, maximum, ammount, unc, dom;
};

int P;
vector <station> stations;
vector <station> all;
int maxDom = -1;
int referencias[300][300];

int main(){

    freopen("clima.in","r",stdin);
    freopen("clima.out","w",stdout);

    cin >> P;
    forn(i,P){

        int buffR;
        cin >> buffR;

        int minL=100, maxR=-100;
        forn(j,buffR){

            int izq, der;
            cin >> izq >> der;

            minL = min(minL,izq);
            maxR = max(maxR,der);
        }

        minL += 60;
        maxR += 60;

        if (referencias[minL][maxR]){

            stations[ referencias[minL][maxR] ].ammount++;
        } else {

            referencias[minL][maxR] = i;
            stations.push_back({minL,maxR,1,0,0});
        }

        all.push_back({minL,maxR,1,0,0});
    }

    forn(i,stations.size()){

        forn(j,stations.size()){

            if (i==j){

                continue;
            }

            if ( stations[i].minimum < stations[j].minimum && stations[i].maximum < stations[j].maximum || stations[i].minimum > stations[j].minimum && stations[i].maximum > stations[j].maximum){
                stations[i].unc += stations[j].ammount;
                continue;
            }

            if( stations[i].minimum <= stations[j].minimum && stations[i].maximum >= stations[j].maximum){
                stations[i].dom += stations[j].ammount;
                maxDom = max(maxDom,stations[i].dom);
            }
        }
    }

    forn(i,all.size()){
        station c = stations[referencias[all[i].minimum][all[i].maximum]];
        if(c.dom == maxDom){

            cout << i+1 << " " << c.unc << endl;
        }
    }

    return 0;
}

Mi idea fue tener dos vectores. Uno con todas las estaciones, y otro con una estación de cada tipo. Cada tipo de estación almacena la cantidad de estaciones de ese tipo que hay, a cuántas domina y con cuántas es incomparable. Calculo estos dos números para todos los tipos de estaciones, que son a lo sumo 110x110 = 12100.

Además, tengo un array bidimensional que almacena la posición en la que se encuentran las estaciones con cada combinación de temperaturas existentes. Esa posición hace referencia al vector de tipos de estaciones.

Recorro el vector de todas las estaciones, e imprimo la posición original y la cantidad de estaciones con las que es incomparable cada una, solo si la cantidad de estaciones a las que domina es la mayor de todas. Accedo a este dato mediante la referencia que almacené en el array bidimensional que mencioné. La cantidad de estaciones a las que domina cada estación la obtengo sumándole la cantidad de estaciones existentes de cada tipo que es dominado, a la cantidad de dominados por el tipo de estación que estoy evaluando.

Espero haberme explicado bien.

Probablemente esté terrible errado con mi línea de pensamiento, pero quería ahorrarme codear un…

Spoiler

… Fenwick Tree

Muchas gracias!

1 me gusta

La idea está bien. Un par de cosas.

Fijate en esa línea que cuando hay estaciones distintas en el mismo lugar, \texttt{referencias[all[i].minimum][all[i].maximum]} ese numerito puede ser mayor o igual que el tamaño de \texttt{stations} (accediendo fuera de rango).

Por ejemplo, podés fijarte qué pasa con un ejemplo de esta pinta:

5
1
1 5
1
1 5
1
0 6
1 
0 6
1
0 7

Fijate acá:

Esa línea, además de ser larga, creo que le faltan paréntesis (quizá los esté asociando bien, no sé bien en qué orden asocia, pero yo por las dudas pondría paréntesis).

Quizá quede más prolijo si declarás dos \texttt{bool} auxiliares, y después dejás algo escrito de la pinta:

if (condicion_1 || condicion_2)
{
   ...
}

Fijate qué pasa también en un caso con una sola estación.

1 me gusta

Muchas gracias por la respuesta!

Tenías razón con lo de que el número de referencia podía ser mayor al tamaño del vector stations. Agregué otra variable para usar de puntero, y en vez de guardar el valor de i como referencia, guardo el valor de la primera variable, que solo se incrementa cuando encuentro un nuevo tipo de estación.

Siempre pensé que en C++ el operador and tenía precedencia sobre el or, y que por eso no hacían falta paréntesis. Igual por las dudas te hice caso y separe ese if en dos variables.

En estos casos no se imprime nada, porque nunca se actualiza el valor de maxDom. Lo solucioné recorriendo la lista de todas las estaciones para settear el valor de maxDom correctamente.

92 puntos! Hay un solo caso en el que el output no es correcto, me quedaría encontrar cuál es.

Gracias por la ayuda, como siempre!

P.D: por las dudas dejo mi código, capaz a alguien le sirva.

Codigo
#include <iostream>
#include <vector>
#include <cstdio>

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

using namespace std;

struct station{

    int minimum, maximum, ammount, unc, dom;
};

int P;
vector <station> stations;
vector <station> all;
int maxDom = -1;
int referencias[300][300];

int main(){

    freopen("clima.in","r",stdin);
    freopen("clima.out","w",stdout);

    forn(i,300)
        forn(j,300)
            referencias[i][j] = -1;

    cin >> P;

    int pointer = 0;
    forn(i,P){

        int buffR;
        cin >> buffR;

        int minL=300, maxR=-300;
        forn(j,buffR){

            int izq, der;
            cin >> izq >> der;

            minL = min(minL,izq);
            maxR = max(maxR,der);
        }

        minL += 60;
        maxR += 60;

        if (referencias[minL][maxR] != -1){

            stations[ referencias[minL][maxR] ].ammount += 1;

        } else {

            referencias[minL][maxR] = pointer;
            stations.push_back({minL,maxR,1,0,0});
            pointer++;
        }

        all.push_back({minL,maxR,1,0,0});
    }

    forn(i,stations.size()){

        forn(j,stations.size()){

            if (i==j){

                continue;
            }

            bool iLowerThanJ = ( stations[i].minimum < stations[j].minimum && stations[i].maximum < stations[j].maximum );
            bool jLowerThanI( stations[i].minimum > stations[j].minimum && stations[i].maximum > stations[j].maximum );

            if ( iLowerThanJ || jLowerThanI ){
                stations[i].unc += stations[j].ammount;
                continue;
            }

            if( stations[i].minimum <= stations[j].minimum && stations[i].maximum >= stations[j].maximum){
                stations[i].dom += stations[j].ammount;
            }
        }
    }

    forn(i,all.size()){
        maxDom = max(maxDom, stations[ referencias[all[i].minimum][all[i].maximum]].dom);
    }

    forn(i,all.size()){
        station c = stations[referencias[all[i].minimum][all[i].maximum]];
        if(c.dom == maxDom){

            cout << i+1 << " " << c.unc << endl;
        }
    }

    return 0;
}
1 me gusta