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
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?
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
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.
#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;
}
}
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.
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.
Yo estaría igual que @michaelszer 
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 
:
#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;
}
}
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 ).
¿Cuántas estaciones meteorológicas realmente distintas puede haber por las cotas del enunciado?
¡¡Me encantó el post de @brianbok sobre mi macro favorita 
!! 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 
no había visto ese bug.
Ya que tenes definido INF, podes inicializar maximo en -INF, que tiene mucho sentido
Graciaaas, sip, eso solucionó todo. Ahora solo me queda mejorar los tiempos, mañana sigo con el programa 
.
Gracias, no me había dado cuenta de esa observación.
Con eso salio el problema de una.
Me alegro que te haya salido. Si tenes ganas podes publicar tu solución con alguna explicación, escondido en una solapa de Spoiler
Muchas gracias por la pista! Pude resolverlo 
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:
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)
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?
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.
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:
En realidad hay que tener en cuenta un par de cosas:
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:
Nos quedaría el dibujo que muestro en 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).
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:
#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…
… Fenwick Tree
Muchas gracias!
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.
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.
#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;
}