Olimpíadas Nacionais de Informática 2007

[Warrior]

Não penses que é fácil resolver correctamente um problema.

Os pontos são atribuídos conforme o número de testes que o problema passou correctamente.

Isto significa, dar a resposta correcta, dentro do tempo limite (1 segundo) e da memória limite (32MB).

A divisão é (normalmente) feita através do tempo. Existem várias maneiras de resolver um problema, umas mais rápidas (eficientes) do que outras. Umas irão passar os testes todos, outras irão ter Time Limit Exceeded no últimos casos de teste.

[samuca]

Eu inscrevi-me nas ONI, ainda ñ tive a treinar, mas ja dei uma olhada. O género de exercícios é igual aos que fiz no CIP (outro concurso de programação) na univ de coimbra e a minha equipa ganhou. O sistema Mooshak é exatamente o mesmo e os problemas estão em português (no outro estavam em ingles), por isso já tou ambientado. Vai ser fixe concorrer com o pessoal desta comunidade, vai ser uma boa experiencia.

Já vi li aqui que algum pessoal tem problemas quanto aos inputs. Aconcelho a que usem Linux e que façam o input por um ficheiro txt, foi assim que fiz em coimbra. Boa sorte a todos.

[Guest tsenart]

É pá.... Alguém me explica como é que eu resolvo este problema???

[Warrior]

Se te der a solução perde a piada toda, mas vou dar uma dica..

Repara que o maior placar vai obrigatoriamente tocar o topo de pelo menos um dos prédios

Já agora, Pedro, quando/se passares por cá.. Qual é a solução óptima para este problema? (a minha apesar de ter 100 pontos é O(n²), pelo que devia falhar num caso de testes "mau", não aleatório)

Programação dinâmica tendo por base a altura dos prédios e o número deles? O(n*h)? Acho que passava em tempo mas que dá MLE..

PS: tsenart qual é o teu nome?

[djthyrax]

É pá.... Alguém me explica como é que eu resolvo este problema???

Tens que ver qual é a sequência mais longa de prédios altos. O maior produto de (nr de prédios) * (altura do mais baixo), vai ser a sequência que prédios onde vai estar a ocupar mais espaço.

[Guest tsenart]

Se te der a solução perde a piada toda, mas vou dar uma dica..

Repara que o maior placar vai obrigatoriamente tocar o topo de pelo menos um dos prédios

Já agora, Pedro, quando/se passares por cá.. Qual é a solução óptima para este problema? (a minha apesar de ter 100 pontos é O(n²), pelo que devia falhar num caso de testes "mau", não aleatório)

Programação dinâmica tendo por base a altura dos prédios e o número deles? O(n*h)? Acho que passava em tempo mas que dá MLE..

PS: tsenart qual é o teu nome?

http://www.portugal-a-programar.pt/index.php?showtopic=6553

[Warrior]

Ainda não te vejo como inscrito nas ONI, vais fazê-lo?

[Guest tsenart]

Ainda não te vejo como inscrito nas ONI, vais fazê-lo?

Lol... Não. Estava só a resolver problemas de programação.

Provavelmente para o ano lá estarei. Agora ainda não tenho nivel.

[Rui Carlos]

Já agora, Pedro, quando/se passares por cá.. Qual é a solução óptima para este problema? (a minha apesar de ter 100 pontos é O(n²), pelo que devia falhar num caso de testes "mau", não aleatório)

Programação dinâmica tendo por base a altura dos prédios e o número deles? O(n*h)? Acho que passava em tempo mas que dá MLE..

recorrendo a uma stack podes resolver o problema em tempo O(n) (acho eu, já implementei a solução, mas ainda não analisei a complexidade a fundo, mas penso que é linear).

[Warrior]

É possível resolver em O(n*h) com O(h) de espaço, encontrei uma solução para isso.

Com a stack.. Não estou a ver como funciona em O(n). Provavelmente não estou a ver o funcionamento.

[Rui Carlos]

É possível resolver em O(n*h) com O(h) de espaço, encontrei uma solução para isso.

Com a stack.. Não estou a ver como funciona em O(n). Provavelmente não estou a ver o funcionamento.

colocas a altura de um prédio e a sua posição numa stack, quando aparecer um prédio mais pequeno do que o prédio que está no topo da stack vais retirando o(s) elemento(s) da stack (maiores do que o prédio em causa); como também guardaste a sua posição podes calcular as áreas máximas possíveis para os prédio que estás a retirar da stack. é claro que há pormenores a ter em conta para garantir que funciona em todos os casos, nomeadamente na última iteração (e se calhar alguns que eu ainda não coniderei, mas em meia dúzia de testes que fiz estava a funcionar).

EDIT: em termos de espaço este algoritmo será O(n).

[Warrior]

E isso dá a solução correcta para uma rua em que os prédios só crescem? (por exemplo)

Nunca vais retirar nenhum prédio (são sempre maiores do que o anterior), mas não estou a ver como consegues calcular a área neste caso.

Se funciona, continuo sem perceber.

[Rui Carlos]

E isso dá a solução correcta para uma rua em que os prédios só crescem? (por exemplo)

Nunca vais retirar nenhum prédio (são sempre maiores do que o anterior), mas não estou a ver como consegues calcular a área neste caso.

Se funciona, continuo sem perceber.

é claro que há pormenores a ter em conta para garantir que funciona em todos os casos, nomeadamente na última iteração.

[Warrior]

E o que fazes nessa última iteração? Pelo que percebo, chegas à última iteração com uma stack completamente cheia com os prédios (ou seja, o vector original). Ou fazes algo alem de inserir o prédio caso a sua altura seja maior?

[Rui Carlos]

E o que fazes nessa última iteração? Pelo que percebo, chegas à última iteração com uma stack completamente cheia com os prédios (ou seja, o vector original). Ou fazes algo alem de inserir o prédio caso a sua altura seja maior?

uma solução muito simples para esse problema é adicionar sempre um prédio no fim com altura 0.

outra solução é no final ter um ciclo que esvazia a stack.

eu optei pela primeira alternativa.

[Warrior]

De facto parece funcionar. Só tenho dúvidas quanto à complexidade, mas uma vez que só adicionas e removes cada prédio uma única vez parece ser mesmo O(n)

[Guest tsenart]

Por favor.... Voces tao para ai a falar de Big O notations(coisa que eu nao sei)... Podem postar o código? E que isto está mesmo a dar cabo das minhas unhas. Já tentei de todas as maneiras que conheço.

Thankz

[Warrior]

Não vou postar o código, mas adiciona-me no MSN que eu ajudo-te no que for preciso.

Deixei o mail lá para tras.

[Warrior]

Pus online o CD fornecido no estágio para as Olimpíadas Internacionais de 2005, tem material bastante interessante para todos, quer participem este ano nas ONI quer não.

http://www.upgaming-hq.com/cd_ioi_05/

PS: Ignorem as informações pré-estágio etc, porque obviamente que já não se aplicam.

[vbmaster]

É oficial, eu e o quickfire vamos participar.

Só estamos dependentes dos dados do professor responsável para proceder à incrição.