ONI 2012 - Qualificação - A - Cromos Repetidos

[Warrior]

http://www.dcc.fc.up.pt/oni/problemas/2012/qualificacao/probA.html

Discussão, as vossas soluções, dúvidas e ajudas!

[Localhost]

meh, não havia uma solução O(n) + complexidade do qsort pra este problema?

[xtrm0]

Eu fiz com O(N):

A(100%):

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
vector <pair <int, int> > inters;

int PesquisaBinaria (int chave, int inf, int sup)
{
     int meio;
     while (inf <= sup)
     {
        meio = inf + (sup-inf)/2;
        if (chave < inters[meio].first)
               sup = meio-1;
        else
               inf = meio+1;
     }

     return sup+1;   // não encontrado
}

int main() {
    int I, a, b;
    pair <int, int> tmp;
    cin >> I ;
    for (int aaa=0; aaa<I; aaa++) {
cin >> tmp.first >> tmp.second;

if (inters.size()>0) a = PesquisaBinaria(tmp.first, 0, inters.size()-1); else a=0;
if (a>0) {
            if(inters[a-1].second>=tmp.first) {
        inters[a-1].second=std::max(inters[a-1].second,tmp.second);
	a=a-1;
	for(int j=a+1; unsigned(j)<inters.size(); j++) {
	    if(inters[j].first <= inters[a].second) {
		inters[a].second = std::max(inters[j].second, inters[a].second);
		inters.erase(inters.begin()+j);
		j--;
		continue;
	    } else {
		break;
	    }
	} 
    	    } else {
        inters.insert(inters.begin()+a, tmp);
	for(int j=a+1; unsigned(j)<inters.size(); j++) {
	    if(inters[j].first <= inters[a].second) {
		inters[a].second = std::max(inters[j].second, inters[a].second);
		inters.erase(inters.begin()+j);
		j--;
		continue;
	    } else {
		break;
	    }
	} 
    }
} else {
    inters.insert(inters.begin()+a, tmp);
    for(int j=a+1; unsigned(j)<inters.size(); j++) {
	if(inters[j].first <= inters[a].second) {
	    inters[a].second = std::max(inters[j].second, inters[a].second);
	    inters.erase(inters.begin()+j);
	    j--;
	    continue;
	} else {
	    break;
	}
    } 
}
    }
    b=0;
    for (int i=0; unsigned(i)<inters.size();i++) {
b+=inters[i].second - inters[i].first + 1;
    }
    cout << b << endl;
    return 0;
}

[Localhost]

não curto ler codigo mas vi ai uma pesquisa binaria.. podes explicar por palavras oq fizeste?

[Warrior]

Aviso já que não olhei para os resultados de ninguém, pelo que não sei que testes é que estão a passar ou não.

A primeira coisa que devem fazer é olhar para o tamanho do input e perceber que soluções é que conseguem passar no tempo ou não. Com um máximo de N=100.000 intervalos, soluções O(N^2) são demasiado lentas, O(N*logN) ou melhor são candidatas a 100 pontos (se não tiverem wrong answers!)

meh, não havia uma solução O(n) + complexidade do qsort pra este problema?

Sim. Ordenar os intervalos é um bom ponto de partida. Acho que neste problema querer resolver à medida que se lê o input é uma má abordagem, é muito mais simples ler tudo, ordenar e depois sim, resolver.

Eu fiz com O(N):

A tua pesquisa binária "coloca" a solução em O(N*logN). Acho que era para isso que estavas a apontar.

De qualquer modo, tens a certeza? Qual é a complexidade do "erase" num "vector"?

[xtrm0]

Tens razao, e O(NlogN).

Consiste basicamente no seguinte:

10-Ler um intervalo;

20-Colocar o intervalo no vetor inters com PesquisaBinaria, tendo em conta o inicio do intervalo;

30-Extender o intervalo inserido aos intervalos que colidem com ele (le essa parte do codigo para perceberes melor)

40-GOTO 10

Quando tiver acabado de processar o input, e só fazer

10-int cromos = 0

20-Para cada intervalo em inters:

21-cromos += intervalo.fim - intervalo.inicio + 1

30-Imprime(cromos)

[Localhost]

não sei qual a complexidade do qsort mas a minha solução sem contar com isso é O(n). Não sei é se a ideia está certa. Basicamente ordeno e depois verifico para cada intervalo se:

- o intervalo está "dentro" do anterior (se não tiver nenhum novo numero que possa ser utilizado);

- se está "fora" do intervalo (se o inicio do intervalo atual for maior do que o fim do intervalo anterior);

- se existem numeros novos (se o final do intervalo atual for maior do que o final do anterior);

a definição de "anterior" não é mesmo o anterior em si mas sim o anterior possível. Por exemplo, se o intervalo atual estiver "dentro" do anterior - nenhum novo numero então o intervalo "anterior" não muda.

Passa por isto a solução?

[xtrm0]

O qsort tambem e O(nlogn), mas no pior caso e O(n^2), por isso mais vale usar o sort().

[Warrior]

não sei qual a complexidade do qsort mas a minha solução sem contar com isso é O(n). Não sei é se a ideia está certa. Basicamente ordeno e depois verifico para cada intervalo se:

- o intervalo está "dentro" do anterior (se não tiver nenhum novo numero que possa ser utilizado);

- se está "fora" do intervalo (se o inicio do intervalo atual for maior do que o fim do intervalo anterior);

- se existem numeros novos (se o final do intervalo atual for maior do que o final do anterior);

a definição de "anterior" não é mesmo o anterior em si mas sim o anterior possível. Por exemplo, se o intervalo atual estiver "dentro" do anterior - nenhum novo numero então o intervalo "anterior" não muda.

Passa por isto a solução?

Sim. Ordenar tem complexidade O(N*logN)

xtrm0: vê o meu último comentário à tua solução.

[Localhost]

Então a minha solução é O(N*logN + N). Se não tiver nenhum erro creio que é suficiente para os 100 pontos.

edit: Warrior, eu primeiro li e depois é que resolvi, se não me engano xD

[xtrm0]

Nao sei, mas espero que seja O(logn). XD

Qual é?

[Localhost]

Nao sei, mas espero que seja O(logn). XD

Qual é?

google it: http://www.cplusplus.com/reference/stl/vector/erase/..

[xtrm0]

[Localhost]

por isso é que não curto usar stl hahaha

[Warrior]

A STL dá muito jeito, mas têm que saber a complexidade das suas funções!

Durante as provas (mesmo as presenciais) têm acesso a documentação, pelo que podem sempre consultar se precisarem.

[SirDave]

O sort( da STL é N log(N), o que quer dizer que a minha solução é O(N log N N).

A ver se dá para 100...

[pedrosorio]

por isso é que não curto usar stl hahaha

Não caias nessa cantiga. Erase de um vector teria sempre que ser O(N) porque tens que afecta toda a estrutura, só numa list é que podes ter O(1). É como o warrior diz, têm que saber as complexidades, ou consultá-las.

O sort( da STL é N log(N), o que quer dizer que a minha solução é O(N log N N).

A ver se dá para 100...

Provavelmente queres dizer  O(N^2 log N). Nesse caso não dá para os 100. Repara que o número de intervalos é 10^5, portanto N^2 = 10^10 já não passa.

[JoaoSantos95]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
      int n,i,j,e = 0,soma = 0,c,d;
      
      pair <int,int> final[100005] = {};
      
      scanf("%d",&n);
      
      for (i = 1; i <= n; i++)
      {
          scanf(" %d %d",&c,&d);  
          final[i].first = c;
          final[i].second = d;
      }
          
      sort (final, final + n + 1);     
      
      e = final[1].second - final[1].first + 1;
      soma = e;  
      
      for (i = 1,j = 2; j <= n; i++,j++)
      {
              if (final[j].first <= final[i].second)
                 final[j].first = final[i].second + 1;
              
              if (final[j].first <= final[j].second)
              {
                 e = final[j].second - final[j].first + 1;
                 soma += e;
              }
      }    
         
      printf("%d\n",soma);    
}

Podem avaliar o meu código e dizer para quantos pontos dá sff ?

[pedrosorio]

@JoaoSantos: já tentaste avaliá-lo tu? Qual é a complexidade do teu código?

[Warrior]

Também não vou avaliar a complexidade do teu código, mas um pormenor que me chamou a atenção:

pair <int,int> final[100005] = {};

Isto dentro do main é muito perigoso. As variáveis assim declaradas vão para a stack e não para a heap, e os limites de memória que existem para cada uma das duas regiões são normalmente diferentes (e podem ser consultados na "Ajuda" do mooshak, assim como num dos avisos do juri). Podem aprender mais sobre isto se estudarem arquitecturas de computadores ou na faculdade, quando programarem em assembly.

Habituem-se a declarar arrays e vectores fora do main, como variáveis globais.

Neste caso em particular temos 100005*4*2 bytes, o que dá cerca de 781kB, pelo que não deverás ter nenhum problema de Memory Limit Exceeded. Contudo, se o limite fosse 10^6 em vez de 10^5, isto poderia ser a diferença entre muitos ou poucos pontos.