Olimpíadas Nacionais de Informática 2007

[QuickFire]

Pois, mas o problema é que as funções que iria usar em PHP são totalmente diferentes 😛

By the way, quero um badgezito de Old School por baixo do nick 😛

[mogers]

boas ppl

Reparei neste topico ontem e não resisti a ir espreitar os exercícios  😄

Vou por aqui como resolveria os exercícios. Digam se acham se as minhas soluções chegavam para ter os 100 pontos e se tão correctas (não adianta ter um programa rápido que dá uma resposta errada).

Já agora, eu não gostei nada do Algorithm Design Manual. Acho que o Data Structures And Algorithm Analysis in C++ do Mark Allen Weiss explica muito melhor os conteudos.

Mas sinceramente, a USACO quase que chega por si só  😄

Problema A - Turismo Espacial.  Categoria: Simulação

Este problema pareceu-me simples. Dado o limite para o número de clientes ser 50000, uma solução O(N^2) dá Time Limit Exceeded, por isso, é preciso encontrar uma solução O(N log N) que passa facilmente no tempo.

A minha estratégia passa por usar uma priority queue (heap) - tempo de O( log N ) na inserção e remoção.

A priority queue ordena os clientes por ordem decrescente de dinheiro e no caso de 2 clientes pagarem o mesmo, escolhe o que tem um tempo de chegada mais antigo.

Primeiro leio os clientes para um array - O( N ).

De seguida, tenho um ciclo para simular as partidas e chegadas dos clientes.

Tempo = C

Enquanto Existirem clientes em espera na heap ou ainda não chegaram todos os clientes a agencia

Colocam-se os clientes cujo tempo_chegada é <= Tempo na heap (que ainda não estavam la obviamente).

Se não existirem clientes em espera ( heap vazia )

Tempo = tempo de chegada do proximo cliente

Senão

Retirar um cliente da heap, este cliente é o proximo a viajar

Tempo em que o cliente "embarcou" = Tempo

Tempo = Tempo + duração da viagem do cliente

Na pesquisa são feitas N comparações no máximo. Cada cliente é inserido e removido da heap 1 vez ( N * 2 (log N) )

Ordenar o array de clientes pelo criterio ja referido - O( N log N ).

Para cada cliente,

imprimir "nome dinheiro (tempo_embarque - tempo_chegada)"

Output em O( N ).

Segundo as minhas contas o tempo de execução T(N) = O( N + 2 * N log N + N log N + N ) ~ O( N log N ).

E penso que passava facilmente no tempo limite.

Problema B - Números Divertidos. Categoria: Complete Search + Teoria dos Números

Para mim, dos problemas da final é o mais dificil de fazer dentro do tempo limite.

Ao contrário do que me pareceu a primeira vista, este problema tem pouco de Teoria dos Números.

"Seguir o enunciado" e percorrer todos os números do intervalo, verificando para cada um se é um número divertido está fora de questão: percorrer 2^31 -1 números é impensável.

Penso que só há uma forma de resolver o problema: primeiro calcular todos os "números divertidos". Depois, dado um intervalo, ver quantos "números divertidos" estão dentro do intervalo.

Assim, o único problema é fazer o primeiro passo eficientemente.

Primeiro calculo para uma matriz, as potencias dos digitos 1..9 que são menores do que 2^31 -1 e guardo o número de potências para cada digito. Para o número 1 não há limite.

Podemos poupar muito tempo com uma simples análise: com k = 3 e os números 153 e 531 temos

153 - 1^3 + 5^3 + 3^3

531 - 5^3 + 3^3 + 1^3

Assim, a minha ideia é ter um ciclo de 2 a 10 (nº digitos) e fazer as combinações de potências dos digitos (1..9) de forma crescente. Isto é, com k = 3 e número de digitos = 3, teria

1^3 + 3^3 + 5^3 = 153 , e verifico que 153 tem um 1, um 3 e um 5 o que bate certo com a soma que fiz.

No caso 1^5 + 4^5 + 5^5 = 4150, é a mesma coisa. Não interessa fazer a soma de zero, por isso na verificação não tenho em conta os zeros.

A minha implementação é:

Array global V com os números divertidos

Pesquisa( Numero_digitos , digito_inicial , potencia , array_digitos , soma_actual )

Se Numero_digitos = 0 Verificar se o número é um número divertido

Array tmp com 10 posicoes

Colocar em tmp a contagem de cada digito na soma_actual

Se tmp = array_digitos // sem contar com o número de zeros

adicionar soma_actual a V

Senao

Repetir Digito de digito_inical até 9

Se Numero_potencias[Digito] > potencia

Se ( soma_actual + Digito^potencia < 2^31 )

Array_digitos[Digito]++

pesquisa( Numero_Digitos-1 , Digito , Potencia , Array_digitos , soma_actual + Digito^potencia)

Array_digitos[Digito]--

main()

Calcular as potencias dos digitos

Adicionar os números 1..9 ao array de números divertidos

Repetir  Numero_digitos de 2 até 10

Repetir Digito_inicial de 1 a 9

Array_digitos[Digito_inicial] = 1

Repetir Potencia de 1 a maximo[digito_inicial]

pesquisa( Numero_Digitos-1 , Digito_inicial , Potencia , Array_digitos , potencias[digito_inical].p[Potencia])

Array_digitos[Digito_inicial] = 1

Ordenar V

Ler número de casos de teste

Para cada caso de teste

ler INF e SUP

Percorrer V e contar

imprimir soma

Alguém me pode confirmar que só existem 37 "números divertidos"? Eu perdi quase 1 hora por um erro mt estúpido. Não sei se tenho mais algum erro.

edit: existem 35 números divertidos. Tinha-me enganado numa condição.

A análise de complexidade é complicada... eu implementei e corre o caso mais complicado (10 inputs de 1 a 2^31 -1)  em menos de 1 segundo.

Problema C - Planeta Arrakis. Categoria: Pesquisa em grafos + Programação dinâmica

Belo problema. Para mim é o mais interessante dos 3 🙂   Mas a solução, penso que não é complicada.

Temos de escolher o percurso em que apanhamos o máximo de especiarias.

Quando nos dirigimos para baixo, podemos seguir para baixo, para a esquerda ou direita.

Quando nos dirigimos para a esquerda, podemos seguir para baixo ou para a esquerda.

Quando nos dirigimos para a direita,  podemos seguir para baixo ou para a direita.

Assim, podemos chgar a cada posição do mapa vindo destas 3 direcções.

Logo, temos uma matriz de programação dinâmica com 3 dimensões: Linha, Coluna , Direcção --- dp[500][500][3]

Eu escolhi partir de baixo, do carryal até ao harvester.

Assim, dp[ y ][ x ][ dir ] contem o máximo de especiarias que podemos colher desde a posição (y,x) até ao harvester vindo da direcção dir.

Dir = 0 -> vindo de baixo , Dir = 1 -> vindo da esquerda , Dir = 2 -> vindo da direita

Teremos também outra matriz  visit[ y ][ x ][ dir ]  com 3 valores possiveis: -1 = não visitado , 0 = não é possivel chegar ao harvester, 1 = é possivel chegar ao harvester.

bool dfs( linha , coluna , direccao )

Se mapa[linha][coluna] == 'H'

devolve true

Se visit[linha][coluna][direccao] != -1 // já visitamos

devolve visit[linha][coluna][direccao]

Se mapa[linha][coluna] == '#'

dp[linha][coluna][direccao] = 0

devolve false

bool encontra_harvester = false

int maximo = 0

Se dfs( linha-1 , coluna , BAIXO ) == true // pesquisa para cima, as outras pesquisas sao semelhantes

encontra_harvester = true

maximo = dp[linha-1][coluna][baixo]

Se direccao  = BAIXO

Pesquisa para a esquerda e direita, actualizando o maximo se as pesquisas encontrarem o harvester

Senao se direccao  = ESQUERDA

Pesquisa para a esquerda , actualizando o maximo se a pesquisa encontrar o harvester

Senao

Pesquisa para a direita , actualizando o maximo se a pesquisa encontrar o harvester

Se mapa[linha][coluna] == 'S'

incrementa maximo

dp[linha][coluna][direccao] = maximo

visit[linha][coluna][direccao] = encontra_harvester

devolve encontra_harvester

main()

init dp a -1

init visit a -1

ler numlinhas, numcolunas

ler mapa

Encontrar coluna do carryal na ultima linha (j)

dfs( numlinhas , j , 0 )

imprimir dp[numlinhas][j][0]

O tempo de execução é O( numLinhas * NumColunas * 3 ) que passa facilmente no tempo limite.

[Warrior]

Foi assim que eu resolvi o problema A e C.

O meu problema no A foi ter implementado a heap à mão, num concurso presencial, devo ter feito borrada.

No B não me lembrei de os pré-calcular todos, é algo que não me posso esquecer num concurso futuro.

No C reduzi a programação dinâmica de 3 para 2 dimensões. Podia-se também resolver com memoization, o código ficaria mais elegante.

[mogers]

O meu problema no A foi ter implementado a heap à mão, num concurso presencial, devo ter feito borrada.

pois... eu agora uso sempre o push_heap e pop_heap da biblioteca algorithm do c++.

No C reduzi a programação dinâmica de 3 para 2 dimensões. Podia-se também resolver com memoization, o código ficaria mais elegante.

eu fiz com memoization.. como é que fizeste o problema com a PD em 2 dimensões? Não tiveste os 100 pontos, sabes pk ?

Eu acho que dá para fazer isto bottom-up (sem recursividade), foi assim que fizeste ?

E no B, são só 37 números?

[Warrior]

Sim, lembro-me que os números eram 30 e tal, tinha na cabeça o número 39, mas pode ser perfeitamente 37 visto o concurso já ter sido à 2 meses.

O Pedro disse que não tinha tido tempo de ver porque é que não tive os 100 pontos porque estava mesmo no final do concurso.

Eu fiz o problema sem recursividade, tinha uma matriz (ou dois vectores, agora não me lembro, mas acho que era mesmo uma matriz) que guardava o número máximo de especiarias que se conseguiam apanhar até (i,j). Para cada (i,j), achava o máximo caso ele viesse pela esquerda, direita, ou cima, +1 caso a casa tivesse especiaria ou não. Lembro-me que dava qualquer coisa n³, e uma vez que o lado era 500 devia ter passado..

[mogers]

Isto de nao ter net em casa é uma xatisse  😕   só pude vir aki agora...

Nos problemas sobre números do Pedro Ribeiro nos concursos universitarios, é tipico ser preciso pre-calcular tudo 😄   E mesmo de outros autores, é bastante frequente, pela força do hábito pensei logo nisso...

O Pedro disse que não tinha tido tempo de ver porque é que não tive os 100 pontos porque estava mesmo no final do concurso.

Eu fiz o problema sem recursividade, tinha uma matriz (ou dois vectores, agora não me lembro, mas acho que era mesmo uma matriz) que guardava o número máximo de especiarias que se conseguiam apanhar até (i,j). Para cada (i,j), achava o máximo caso ele viesse pela esquerda, direita, ou cima, +1 caso a casa tivesse especiaria ou não. Lembro-me que dava qualquer coisa n³, e uma vez que o lado era 500 devia ter passado..

infelizmente vim aqui numa fugida... pode ter sido um bugzito que acontece... eu tenho alguma dificuldade em fazer este tipo de problemas sem recursividade... vou tentar dar uma olhadela a essa ideia 😄

[Tharis]

A esta hora, os nossos colegas/compinchas estão no concurso CIIC 2007 do estágio das ONIs.

Neste momento encontra-se assim.

OI Miguel_Araujo             0:36:27 (0) 1 0:36:27

2 IOI Filipe_Brandao 0:41:35 (0)     1       0:41:35

3 IOI Tiago_Andrade     0:54:39 (0)   1       0:54:39

4 IOI Nuno_Sousa         0:52:15 (1)    1       1:12:15

5 IOI Nuno_Lourenco    0:57:33 (1) 1 1:17:33

6 IOI Joao_Matos 0     0:00:00

7 IOI Diogo_Sousa 0      0:00:00

8 IOI Ricardo_Goncalves0 0:00:00

Podem encontrar tudo neste site e mais info sobre o estágio aqui.

[Triton]

Sim, só falta uma prova para decidir quem vai às IOI, mas independentemente disso já aprendi imensas coisas no estágio e a experiência também está a ser muito enriquecedora. 😛

[Tharis]

Passou o Warrior (1º Lugar) e o Triton ficou em 7º Lugar... Mas pelas palavras dele:

mas independentemente disso já aprendi imensas coisas no estágio e a experiência também está a ser muito enriquecedora. 😉

A classificação final foi:

[vbmaster]

Oh tharis o que tu estás a ver não quer dizer nada nem garante que o Warrior tenha passado (é claro que passou).

Tu podes ter resolvido algo muito rápido nas ONi mas estar mal, tens de ver mesmo os pontos que se obteve, e essa classificação não diz isso.

[Triton]

O vbmaster tem razão, isso não tem qualquer efeito para classificação, como eu comecei a resolver o B, só enviei o A depois dos outros que começaram pelo A. Eu até acabei por ficar em sexto nessa prova. Em suma o estágio foi uma experiência muito fixe, conheci pessoas excelentes e aprendi algoritmos e técnicas de programação que são mesmo muito interessantes. Recomendo a todos que querem realmente participar para o ano que treinem muito!

[Guest id194]

Eu acho que isso não importa e o que a classificação mostra é o que é. Pelo menos era assim quando eu fui a concursos onde usavam esse sistema. Não importa quando começaste a resolver, o que interessa era o tempo que demoraste a submeter (desde o inicio do concurso) o código correcto e que funcionava. Ou seja, quem resolvesse mais no menor tempo, ganhava.

O quadro mostra que o Warrior submeter apenas uma versão do código de cada problema e que demorou X tempo desde o inicio do concurso até submeter cada um dos problemas.

Comigo era assim, o sistema é o mesmo e é isso que dá entender. Se não, como é que vão avaliar?

A ideia do mooshak, quando eu o usei em concursos era mesmo essa. Ver quem submetia os problemas correctos em menor tempo possível. Submeter determinado código com erro, aumentava o tempo. Não sei ainda é assim, mas é o que parece.

[Triton]

Não fales do que não sabes... os concursos podem estar configurados de várias formas, neste caso não interessa o tempo que demoras a resolver, só conta a última submissão do teu programa, apesar de o ranking no Mooshak durante o concurso ser feito com base no tempo.

[vbmaster]

Só interessa o tempo de submissão em caso de empate.

A cada código enviado será submetida uma pontuação de 0 a 100 a partir do número de testes que o algoritmo passa sem dar qualquer género de erro.

Ali o Warrior até podia ter submetido 3, mas em cada um ter 10 pontos e no final ser ultrapassado por quem resolveu 1 e teve 70.

(Mas isso não aconteceu, e ainda bem)

[Warrior]

Eu tive 256/300 pontos nesta prova (96/60/100), na de 4ª feira em que eram 4 problemas tive ~280/400, o Triton não me lembro..

[Guest id194]

Não fales do que não sabes...

Desculpa se te ofendi... Já não se pode ter opiniões neste fórum!

[mogers]

boas ppl

alguém sabe os resultados dos portugueses no dia 1 das IOI's ? (Especialmente do Warrior)

[vbmaster]

boas ppl

alguém sabe os resultados dos portugueses no dia 1 das IOI's ? (Especialmente do Warrior)

No news.

Mas eles em olimpíadas internacionais têm acesso restrito a contactos com o exterior....

[djthyrax]

Para quem quer treinar, http://evaluator.hsin.hr/

[Warrior]

Muito mau. (mesmo)

Acabou agora o segundo dia e já correu melhorzinho, os resultados devem ser publicados daqui a nada (na verdade já estão 30 minutos atrasados)

Para terem uma ideia, espero hoje ter pelo menos 4x mais do que tive no primeiro dia, e mesmo assim não fiz um problema..

Edit: Afinal tive 5x mais.. Que miséria de primeiro dia..