solução das questões da prova do ano passado

[maycon sambinelli]

alguém tem as soluções das questões da prova do ano passado?

--
Maycon Sambinelli (@msambinelli)
Mestrando em Ciência da Computação
Universidade Estadual de Campinas (UNICAMP)

Bacharel em Ciência da Computação
Universidade Estadual de Maringá (UEM)

:wq

[Thiago S. A.]

Pra questão 5, eu fiz um algoritmo que usa o método de seleção O(n). Alguém mais fez essa?

[maycon sambinelli]

Manda ai.. eu fiz, mas eu tive que roubar... em um passo do alg. eu
disse que era pra aplicar uma ordenação usando um algoritmo linear

Em 13 de maio de 2012 18:33, Thiago S. A. <thiag...@gmail.com> escreveu:
> Pra questão 5, eu fiz um algoritmo que usa o método de seleção O(n). Alguém
> mais fez essa?

[Igor Medeiros]

thiago, tu poderias explicar a idéia do teu algoritmo?

[Ricardo Correa]

então... para essa questão, eu resolvi usando em parte o counting-sort... e fazendo uma modificação:
Voce monta o primeiro passo do vetor C, que é contar a quantidade de entradas de cada numero no array C e custa theta(n), com o array C em mãos, vc verifica se existe alguma entrada que é maior que n/3, gastando O(k)
No total vc gasta theta(n) se o k for menor que n.
Se tiverem alguma outra idéia, mandem aí.

2012/5/13 maycon sambinelli <msamb...@gmail.com>

[Igor Medeiros]

lembro de o professor ter falado que essa questão era solucionada com o método de seleção com as medianas.

[João Paulo Pereira Zanetti]

Não pode usar o counting sort, porque não há limitante nenhum para os
valores da entrada.

Minha ideia é que um elemento que se repete n/3 vezes vai ser
necessariamente o (n/3)-ésimo menor elemento, o (2n/3)-ésimo, ou o
maior elemento do vetor. (Essas frações talvez precisem de algum piso
ou teto, mas a ideia é essa.)

Então o algoritmo seria encontrar esses três caras, contar quantas
vezes cada um deles aparece e outputar os que tiverem um count >= n/3.

2012/5/13 Igor Medeiros <igorosb...@gmail.com>:

[Thiago S. A.]

 Opa, não deu pra responder antes pq minha internet caiu...

Minha solução foi um pouco parecida com a do João.

Minha solução foi primeiro pegar a mediana m com o Select, contar quantas vezes m se repete no vetor V, se for >= n/3 então já temos um elemento.
Em seguida o vetor é particionado em A, elementos menores que m, e B, elementos maiores que m, cada com no máximo n/2 elementos.
Para cada um dos vetores A e B é apicado o mesmo processo (pegar a mediana e contar repetições), se a respectiva mediana repete-se mais do que n/3 vezes então temos mais um elemento.

É importante notar que se há 3 elementos que se repetem n/3 vezes necessariamente um deles estará na mediana e se  há um elemento que se repete n/3 vezes nos vetores A ou B, então necessariemente este elemento estará na mediana.

Acho que também é necessário fazer alguns tratamentos de pisos e tetos.

[Igor Medeiros]

Joao Paulo, essa sua idéia é para vetores ordenados?

[Ricardo Correa]

Oi Igor, acho que não precisa estar ordenado.... eu tinha pensando na mesma coisa aqui.

O algoritmo acha a mediana, independente da entrada estar ordenada.... portanto com a mediana em mãos não interessa muito a entrada tb.

2012/5/14 Igor Medeiros <igorosb...@gmail.com>

[Raul Negreiros]

Bom eu pensei um pouco diferente, eu usaria um radix sort modificado. Funcionaria da seguinte maneira:

-> primeiro admite que tem um contador em cada "cesta", ele conta quantos elementos a "cesta" possui;

-> na hora de recolher as "cestas" só recolhe as que possuem n/3 dos elementos ou mais;

Acho que assim daria certo, pelo menos não vi um caso que falhasse, porém se fosse na prova eu acrescentaria mais uma verificação só pra ter certeza que tá tudo beleza, ela seria assim:

-> Quando for recolher os elementos das "cestas" na última iteração( bit = k) vai contando e só adiciona caso ele apareça realmente >= n/3;

Creio que essa verificação seja o suficiente, já que nessa altura do campeonato os elementos iguais estão agrupados em uma mesma "cesta" todos juntos.

Ficou clara a ideia? alguém vê algum problema na solução?