Olá pessoal,
Eu venho aqui, depois de um tempo enorme, para anunciar uma série de posts que serão feitos aqui no blog, como parte do treinamento das equipes da UFRN para a Maratona de Programação 2011. Nosso treinamento consistirá de diversas reuniões no LCC para simular competições passadas dos mais variados locais do mundo, tanto individuais quanto em equipe e, sempre que possível, no mesmo dia à tarde eu irei fazer um post com algumas dicas para os problemas que conseguirmos fazer. Além das dicas, terá o nível de dificuldade (variando de 0 a 10) e o assunto abordado. O que vocês acharam da novidade?
Começaremos hoje, com uma competição que fizemos individualmente, que é o Waterloo ACM Programming Contest 2009 – Fall 2! Tivemos um comparecimento bem baixo, de apenas 5 pessoas (eu, Edwyn, Lucas, Zailton e Argus), esperando que esse número cresça, mas entendo que algumas pessoas gostariam de estar lá e não puderam, como os calouros de Cien Comp, que tinham aula no horário, além de Álvaro e Leon, que ainda estão em aulas no IFRN. Para vocês que queriam ir e não puderam, tirem 3 horas em casa mesmo e tentem fazer os problemas dessa competição, sem olhar as dicas abaixo; quando terminar o tempo, venha olhar ou dar alguma dica aqui no blog.
Waterloo Contest 2009 – Fall 2
Bem, as competições desenvolvidas pela Universidade de Waterloo, no Canadá, sempre consistem de 5 problemas, para serem resolvido em 3 horas. Desse modo, sempre que formos refazer essas provas, nós iremos competir individualmente, para testar como está o empenho de cada um. Durante a nossa competição, cada competidor só conseguiu fazer o problema E, todavia logo que ela acabou nós nos reunimos para tentar entender a solução do problema C. No final, quando cheguei em casa, pensando mais um bocadinho, consegui ter uma ideia para o problema A. Curtam as dicas:
-
Problem A: Rooks
UVa ID: 11699. Link: Rooks. Dificuldade (0 a 10): 5. Assunto: Bitmasks.
Uma ideia interessante para o problema é perceber que com 15 torres você com certeza pode ter todos os quadrados do tabuleiro ocupados, pois você precisa no máximo de uma torre por linha. Dessa forma, podemos testar todos os possíveis subconjuntos das linhas, pois é um total de 32768. Para ver os subconjuntos, pensamos neles como os números de 0 a 32767, pois temos 15 bits “acesos” ou “apagados”, os quais representarão as linhas com ou sem torres. Para cada subconjunto, percorre-se somente as linhas que não possuem torres e verifica-se quantas colunas existem com hashes. Caso o número de colunas seja menor do que ou igual ao de torres, então pode-se colocar uma torre em cada uma dessas colunas (nas linhas “acesas”) e atacar todos os quadrados necessários. Deu para entender? Qualquer dúvida, mande um comentário!
-
Problem B: Pipes
UVa ID: 11700. Link: Pipes. Dificuldade (0 a 10): ? Assunto: ?
Não conseguimos fazer esse problema. Qualquer dica, mande um comentário!
-
Problem C: Cantor
UVa ID: 11701. Link: Cantor. Dificuldade (0 a 10): 4. Assunto: Sistemas numéricos.
O problema parece simples à primeira vista. Depois de levar o primeiro Wrong Answer, você pensa que ele está errado. Depois descobre que era besteira! Em problemas em que limita-se o número de casas decimais do número para algo baixo (como 6 nesse exemplo), normalmente é muito mais fácil você trabalhar com o número como inteiro, ao multiplicar pela potência de 10 adequada. A ideia é pré-calcular todos os membros e depois fazer somente uma consulta em um vetor. Primeiramente, deve-se calcular os números que no primeiro passo para transformar ele em base 3, já gera um dígito 1. Coloque esses números em uma fila. Além disso, você deve ter uma lista “reversa” para cada número N, indicando de quais números você chegará em N com 1 passo da mudança de base. Assim você marcará cada elemento colocado na fila como NON-MEMBER, e enfileirará aqueles que estão na lista “reversa” dele mas ainda não foram marcados. Deu para entender? Qualquer dúvida, mande um comentário!
-
Problem D: Meltdown
UVa ID: 11702. Link: Meltdown. Dificuldade (0 a 10): ? Assunto: ?
Não conseguimos fazer esse problema. Qualquer dica, mande um comentário!
-
Problem E: sqrt log sin
UVa ID: 11703. Link: sqrt log sin. Dificuldade (0 a 10): 2. Assunto: Recursão + Memoization.
Esse problema é o mais fácil do contest. E é realmente fácil. Nele, só é preciso implementar a recursão exatamente como é descrito no enunciado, sem alterações, e utilizar um memoization, ou seja, ter um vetor que irá armazenar o valor de Xi para cada 0 <= i <= 1000000, assim que ele for calculado a primeira vez, para que não haja cálculo repetido. Deu para entender? Qualquer dúvida, mande um comentário!
É isso aí, pessoal! Esse foi nosso primeiro treino para a Maratona de Programação 2011 e espero que eu possa ter ajudado vocês com essas dicas!
Posts interessantes:
- Computação e Matemática
- Não é apenas o emprego dos sonhos
- Segmentation Fault – a memória do PC pede ajuda!
- Programando Melhor
E você, como foi no Waterloo Contest 2009 – Fall 2? Gostou das dicas ou estavam meio confusas? Conseguiu resolver qual(is) problema(s)? Faça seu comentário e deixe sua opinião!
Helton de Melo Duarte
“E disse o SENHOR a Satanás: Observaste tu a meu servo Jó? Porque ninguém há na terra semelhante a ele, homem sincero, e reto, e temente a Deus, e desviando-se do mal.” Jó 1.8
