Jump to content
Sign in to follow this  
xtrm0

ONI 2009 - A

Recommended Posts

xtrm0

Boas, estava a fazer o exercicio A das ONI de 2009, e só consegui ter 62 pontos. Já estive a tentar pensar em formas de pré-processar soluções, só que não consigo.

Alguma ideia?

#include <iostream>

using namespace std;

int main(){
   int N, F, maxi=0, Me;
   int E[50002], Fi, Ff, ME[52]; //ME - variavel para guardar a quantidade de edificios com a mesma altura, para cada resposta
   cin >> N;
   for (int i=1; i<=N; i++) {
       cin >> E[i];    
   }
   cin >> F;
      for (int i=1; i<=F; i++) {
       maxi=0;
       Me=0;
       cin >> Fi >> Ff;
       for (int j=Fi; j<=Ff; j++) {
           if (E[j] > maxi) {
              maxi=E[j];
              Me=1; 
              ME[Me]=j;        
           } else if (E[j] == maxi) {
              Me++;
              ME[Me]=j;       
           }
       }
       cout << maxi << " ";
       for (int x=1; x<Me; x++) cout << ME[x] << " ";
       cout << ME[Me] << endl;    
   }

   return 0;
}

Enunciado:

Problema - Dubai

A mais importante cidade dos Emirados Arabes Unidos, o Dubai, sofreu nos últimos anos uma enorme transformação, passando de um aglomerado populacional quase perdido no meio do deserto para uma imensa metrópople recheada dos mais fantásticos arranha-céus. Ao longo da sua principal avenida multiplicam-se as construções em altura, como o incrível Burj Dubai, que ao ficar completo no final de 2009 se tornará no mais alto edíficio do mundo, passando os 800m e batendo por larga margem todos os antigos recordes.

Os edíficios são identificados pelo seu número de ordem, contado a partir do início da avenida. Quando uma foto é tirada, apenas uma parte dos edifícios da avenida aparece na imagem e desse modo um edifício se destaca por ser o mais alto nessa mesma imagem. Por exemplo, podíamos ter os seguintes 10 edifícios ao longo da avenida:

Nº ordem:  1  2  3  4  5  6  7  8  9  10

  Altura: 350 150 200 400 831 450 200 350 100 350

Se uma foto apanhar todos os edifícios, o mais alto é o de altura 831. Se a foto apenas apanhar do primeiro ao quarto edifício, o mais alto mede 400. Já se considerarmos apenas do sétimo ao décimo edifício, existem dois empatados medindo o máximo de 350.

Dada a configuração dos edifícios ao longo da avenida, terás de descobrir qual o mais alto de cada uma duma série de fotografias.

O Problema

Dada um conjunto de N números inteiros indicando as alturas dos edifícios ao longo da avenida e F fotos, cada uma descrita por dois números Ai e Bi, indicando que a foto apanha todos os edifícios entre Ai e Bi (inclusive), a tua tarefa é descobrir qual (ou quais) o(s) edifício(s) mais alto(s) de cada foto.

Input

Na primeira linha do input vem um único número inteiro N indicando o número de edifícios da avenida (1≤N≤50 000). Segue-se uma linha contendo exactamente N inteiros Ei separados por espaços únicos, indicando as alturas dos edifícios ao longo da avenida, da esquerda para a direita (1≤Ei≤100 000 000).

Na terceira linha vem um único inteiro F indicando o número de fotos a considerar (1≤F≤50 000). Seguem-se exactamente F linhas, cada uma contendo dois números inteiros Ai e Bi, separados por um espaço, indicando que a foto apanha todos os edifícios consecutivos desde o edifício nº Ai até o edifício nº Bi ,inclusive (1≤Ai≤ Bi≤N). Nota que os edifícios são contados da esquerda para a direita, ou seja, o primeiro edifício corresponde ao edifício mais à esquerda.

Output

O output deve ser constituído exactamente por F linhas, cada uma descrevendo o(s) edifícios(s) mais alto(s) de cada foto, pela mesma ordem em que as fotos aparecem no input.

Cada uma destas linhas começa por um único inteiro indicando a altura do(s) edifício(s) mais alto. Segue-se um único espaço, seguido dos números de ordem dos edifícios da foto que têm essa altura máxima. Estes números devem também vir separados por um único espaço. Nota que se existir um único edifício de altura máxima, apenas deves imprimir esse número. Caso existam vários empatados, deves imprimir todos pela ordem em que aparecem na avenida (isto é, da esquerda para a direita). É garantido que no máximo existem 50 edifícios empatados com a altura máxima.

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 50% dos pontos, o número de prédios e de fotos é inferior ou igual a 200.

Exemplo de Input

10

350 150 200 400 831 450 200 350 100 350

3

1 10

1 4

7 10

Exemplo de Output

831 5

400 4

350 8 10


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Olá,

Em 1º lugar, pedia que quando pedisses ajuda para um problema que postasses o link para o enunciado. Por "ONI 2009 - A" pensei que era o problema A da final e não o da qualificação.

62 pontos já tá bom sem conhecimentos prévios. Este problema requeria o uso de técnicas um pouco mais avançadas. Vê o tutorial sobre Range Minimum Query (RMQ). Neste caso queres o máximo, mas a forma de construção do RMQ é quase igual.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Não consigo,o que estou a fazer mal?

Tentei fazer a usar vectors e DP, e mesmo assim não deu:

#include <iostream>
#include <vector>
#define MAXN 50002
#define max(a, b)  (a > b) ? a : b
using namespace std;

int E[MAXN];
vector <vector <int> > P;
int N;
int pre(int x, int t)
{
   if(P[x][t]!=-1) {
       return P[x][t];
   }
   P[x][t]=max(pre(x,t/2),pre(x+t/2,(t+1)/2));
   return P[x][t];
}


int main(){
  int F, maxi=0;
  int Fi[MAXN], Ff[MAXN];
  cin >> N;
  for (int i=1; i<=N; i++) {
      cin >> E[i];
  }
  cin >> F;
  for (int i=1; i<=F; i++) {
      cin >> Fi[i];
      cin >> Ff[i];
  }
  for (int x=0; x<N; x++) {
      P.push_back(vector <int>());
      for (int t=0; t<N-x+1; t++) P[x].push_back(-1);
  }
  for (int x=0; x<N; x++) P[x][0]=E[x];
  pre(0,N-2);


  for (int i=1; i<=F; i++) {
      maxi=P[Fi[i]][Ff[i]];
      cout << maxi << " ";
      for (int x=1; x<N; x++) if(E[x]==maxi) cout << x << " ";
      cout << "\b" << endl;
  }

  return 0;
}



<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Não tive muito tempo para ver o código. Eu prefiro a versão que divide o array em blocos iguais (sqrt(N) cada), não tive tempo para ver se a tua função Pre está correcta, mas sei que

maxi=P[Fi[i]][Ff[i]];

Aqui não é assim que deves calcular o maximo, deixo isso como exercício. Senão chegares lá, eu ajudo.

De qualquer forma, essa solução acaba por ser tão lenta como a anterior porque percorres todo o array para cada query. O tempo de execução é F*N na mesma. Para além de identificar o máximo, vais precisar de guardar os indices onde o maximo ocorre.

Penso que na usaco tem um texto a falar dos tempos de execução e complexidade dos algoritmos logo no inicio, é uma coisa muito importante.

edit: quando t = 1, a função pre pode entrar em ciclo infinito devias tratar esse caso especial.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Acho que já corrigi o erro de quando é igual a Fi==Ff. E tambem já meti as funções a funcionarem de forma certa, mas mesmo assim dá-me runtime error, mas no meu pc não dá.

#include <iostream>
#include <vector>
#define MAXN 50002
#define max(a, b)  (a > b) ? a : b
using namespace std;

int E[MAXN];
vector <vector <int> > P;
int N;
int pre(int x, int t)
{
   if(P[x][t]!=-1) {
       return P[x][t];
   }
   P[x][t]=max(pre(x,(t+1)/2),pre(x+(t+1)/2,(t+1)/2));
   return P[x][t];
}


int main(){
  int F, maxi=0;
  int Fi[MAXN], Ff[MAXN];
  cin >> N;
  for (int i=1; i<=N; i++) {
      cin >> E[i];
  }
  cin >> F;
  for (int i=1; i<=F; i++) {
      cin >> Fi[i];
      cin >> Ff[i];
  }
  for (int x=0; x<N; x++) {
      P.push_back(vector <int>());
      for (int t=0; t<=N-x; t++) P[x].push_back(-1);
  }
  for (int x=1; x<N; x++) P[x][1]=E[x];
  pre(1,N-1);


  for (int i=1; i<=F; i++) {
      if (Fi[i]==Ff[i]) {maxi=E[Fi[i]];} else {maxi = pre(Fi[i],Ff[i]-Fi[i]);}
      cout << maxi << " ";
      for (int x=Fi[i]; x<=Ff[i]; x++) if(E[x]==maxi) cout << x << " ";
      cout << "\b" << endl;
  }

  return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Uma coisa que deves fazer sempre é testar com o caso base (o caso mais simples possível)

1

1

1

1 1

O teu programa dá segmentation fault. Acho que estás a misturar formas de numerar os indices diferentes, quer usando [0..N-1] ou [1,N] e isso nunca é boa ideia :P

Primeiro põe esta versão a funcionar, mas creio que terás ~62 pontos na mesma. Repara que se a query for de 1 a N, continuas a percorrer o array E todo na mesma.

edit: pela minha experiência, penso que usar indices de 0 a N-1 é quase sempre melhor porque simplifica alguns cálculos. Exemplo: evitas precisar de fazer coisas como (t+1)/2 --->  t/2


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Agora já não dá erro nessa, mas mesmo assim não funciona.

#include <iostream>
#include <vector>
#define MAXN 50002
#define max(a, b)  (a > b) ? a : b
using namespace std;

int E[MAXN];
vector <vector <int> > P;
int N;
int pre(int x, int t)
{
   if(P[x][t]!=-1) {
       return P[x][t];
   }
   P[x][t]=max(pre(x,t/2),pre(x+t/2+1,t/2));
   return P[x][t];
}


int main(){
  int F, maxi=0;
  int Fi[MAXN], Ff[MAXN];
  cin >> N;
  for (int i=0; i<N; i++) {
      cin >> E[i];
  }
  cin >> F;
  for (int i=1; i<=F; i++) {
      cin >> Fi[i];
      Fi[i]--;
      cin >> Ff[i];
      Ff[i]--;
  }
  for (int x=0; x<N; x++) {
      P.push_back(vector <int>());
      for (int t=0; t<N-x; t++) P[x].push_back(-1);
  }
  for (int x=0; x<N; x++) P[x][0]=E[x];
  pre(0,N-1);


  for (int i=1; i<=F; i++) {
      if (Fi[i]==Ff[i]) {maxi=E[Fi[i]];} else {maxi = pre(Fi[i],Ff[i]-Fi[i]);}
      cout << maxi << " ";
      for (int x=Fi[i]; x<=Ff[i]; x++) if(E[x]==maxi) cout << x+1 << " ";
      cout << "\b" << endl;
  }

  return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Ainda alguns exemplos triviais

3

1 2 3

4

1 1

1 2

1 3

2 3

Falha na 3ª query. Usa antes este exemplo. Verifica bem se o pre está a funcionar correctamente, isto é, se P tem os valores que devia.

De momento, não te posso ajudar a fazer o debuging disso, o facto de ser recursivo não ajuda muito. Caso não consigas, sugiro que tentes antes a alternativa com blocos de sqrt(N) elementos. É iterativo e parece-me mais fácil de debugar caso seja preciso.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
mogers

Fiz um pouco de debug. Comecei por simplificar um bocado o código do cálculo dos intervalos para evitar erros e ver o que estava a acontecer na chamada à função pre.

int pre(int x, int t)
{
if(P[x][t]!=-1)
	return P[x][t];

if (t == 1)
	return P[x][t] = max( E[x], E[x+1]);
int i = x, f = x+t;
int mid = (i+f) / 2;
int ta = mid-x;
int tb = f-mid;
P[x][t] = max(pre(x,ta),pre(mid,tb));
return P[x][t];
}

Assim parece estar a funcionar. Mas mantém o problema de eficiência que já falei.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

alguém me pode explicar para que servem as seguintes linhas de codigo:  😳

vector <vector <int> > P;

P.push_back(vector <int>());


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

Em primeiro lugar é preciso saber se conheces o normal funcionamento das classes da Standard Template Library (STL). Como não parece ser o caso, sugiro veres isto http://www.cplusplus.com/reference/stl/vector/ e um exemplo


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Olá. Deu-me MLE. Então como é que é suposto fazer, de modo a não se calcular todos os intervalos?


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Já falei em quase todos os meus posts neste tópico na técnica de usar blocos de sqrt(n) elementos explicada no tutorial...

Já tentaste fazer dessa forma?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

mogers, sugeres dividir o array, em blocos de sqrt(n) elementos mas tipo imagina que o limite inferior está no meio de um bloco, e o limite superior está no meio de outro bloco? Nesses casos ignoram-se os blocos?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

mogers, sugeres dividir o array, em blocos de sqrt(n) elementos mas tipo imagina que o limite inferior está no meio de um bloco, e o limite superior está no meio de outro bloco? Nesses casos ignoram-se os blocos?

Isso é um caso a ter cuidado, mas se ignorasses os blocos, para que é que os terias? :D   Tens de pensar como tratar essa situação (dica: keep it simple).


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

Hum acho que já estou a compreender mas antes de vir a este exercicio, vou tentar fazer o C :D


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
xtrm0

Já consegui fazer a pesquisa para sqrt(n) blocos. Só que deu-me um warning:

A.cpp: In function ‘int jaexiste(int)’:

A.cpp:26: warning: comparison between signed and unsigned integer expressions

Aqui:

struct ecama{
    int h;
    vector <int> e;
}; //edificios com a mesma altura
vector <ecama> ama;
int jaexiste(int n) {
    for(int x=0; x<ama.size(); x++) {      // erro aqui
        if (ama[x].h==n) {
            return x;
        }
    }
    return -1;
}

Como é que faço para um x signed e comparar um x unsigned?


<Signature goes here>

Share this post


Link to post
Share on other sites
skiller10

acho que se meteres (int) antes da variavel unsigned, funciona


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
xtrm0

Sim, funcionou obrigado. Mas tive TLE aos 15 pontos :confused: .

Foi assim que fiz:

#include <iostream>
#include <vector>
#include <cmath>
#define max(a, b)  (a > b) ? a : b
using namespace std;
int E[50001];
int ma[256];
int N, F, Fi, Ff;
int sqrn;
int maxi=0;
struct ecama{
   int h;
   vector <int> e;
}; //edificios com a mesma altura
vector <ecama> ama;

void pre() {
   for (int x=1; x<=N; x+=sqrn) {
       for(int j=x; j<=x+sqrn; j++) {
           ma[x/sqrn]= max(ma[x/sqrn], E[j]);
       }
   }
   return;
}
int jaexiste(int n) {
   for(int x=0; x<int(ama.size()); x++) {
       if (ama[x].h==n) {
           return x;
       }
   }
   return -1;
}

void pre2() {
   ecama qs; //querry_starter
   for (int x=1; x<=N; x++) {
       int a=jaexiste(E[x]);
       if(a==-1) {
           qs.h=E[x];
           qs.e.clear();
           qs.e.push_back(x);
           ama.push_back(qs);
       }else{
           ama[a].e.push_back(x);
       }
   }
}



void processar() {
   maxi=0;
   int i;
   for (i=Fi; i<Fi+(Fi%sqrn); i++) { // é i<=Fi ou i <Fi?
       maxi=max(maxi, E[i]);
   }
   for (; i<=Ff-(Ff%sqrn); i+= sqrn) {
       maxi=max(maxi, ma[i/sqrn]);
   }
   for (; i<=Ff; i++) {
       maxi=max(maxi, E[i]);
   }

   return;
}


int main() {
   cin >> N;
   for (int x=1; x<=N; x++) cin >> E[x];
   sqrn = sqrt(N);
   pre();
   pre2();
   cin >> F;

   for (int x=0; x<F; x++) {
       cin >> Fi >> Ff;
       processar();
       cout << maxi << " ";
       int al=jaexiste(maxi);
       for (int kj=0; kj<int(ama[al].e.size()-1); kj++) {
           if (ama[al].e[kj]>=Fi && ama[al].e[kj]<=Ff)
           cout << ama[al].e[kj] << " ";
       }
       if (ama[al].e[ama[al].e.size()-1]>=Fi && ama[al].e[ama[al].e.size()-1]<=Ff)
       cout << ama[al].e[ama[al].e.size()-1] << endl;
   }
   return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.