Olá pessoal,
Venho aqui para falar da nossa segunda competição de treinamento para a Maratona de Programação. Novamente, compareceram somente os componentes das equipes “Absurdo Clássico” e “Score Limit Exceeded”, da UFRN, apesar de saber que ainda existem alguns que querem mas não estão podendo comparecer. Como já foi dito, quem não pôde ir, tire 5 horas em algum local com sua equipe reunida e tente refazer essa prova, pois irá trazer muito mais conhecimento para vocês.
East Central Regional 2010
Bem, as provas das regionais dos Estados Unidos e Canadá são sempre de um enorme proveito para treinamento, pois consistem de problemas com dificuldade interessante, porém não dos mais difíceis, sendo ideal para equipes que estão começando um treinamento mais pesado, como as nossas equipes da UFRN. Essa prova possuiu 8 questões e nós a fizemos em equipe (na verdade, foram equipes de 2 pessoas, pois só compareceram 4 dessa vez e ainda 2 tiveram que sair mais cedo), conseguindo resolver, ao final, 4 problemas, sendo 3 na hora mesmo da competição e 1 depois do término do tempo. Vejamos como eles são!
- Problema A: Cut it out!
LA ID: 4900. Link: Cut it out! Dificuldade (0 a 10): ? Assunto: ?
Não conseguimos fazer esse problema. Qualquer dica, mande um comentário!
- Problema B: Flip it!
LA ID: 4901. Link: Flip it! Dificuldade (0 a 10): 3 Assunto: Pilhas, Simulação
Esse problema era o segundo mais fácil da prova, acredito eu, pois envolvia somente a manipulação de um tabuleiro de pilhas. É um problema simples de simulação, o qual tem como dificuldade somente o fato de ter que manter cada quadrado do grid como uma pilha, a fim de facilitar as operações descritas no enunciado. Outro cuidado que deve-se tomar é na leitura da linha de operações, a qual é uma string, mas antes foi feita leitura de inteiros, portanto deve fazer um getline() antes, apenas para pegar o ‘\n’ que ainda está no buffer. Mais informações sobre essa limpeza necessária no buffer pode ser encontrado no texto do Shahriar Manzoor. Deu para entender a explicação? Qualquer dúvida, mande um comentário!
- Problema C: Maze
LA ID: 4902. Link: Maze. Dificuldade (0 a 10): ? Assunto: ?
Não conseguimos fazer esse problema. Qualquer dica, mande um comentário!
- Problema D: Photo Shoot
LA ID: 4903. Link: Photo Shoot. Dificuldade (0 a 10): ? Assunto: ?
Não conseguimos fazer esse problema. Qualquer dica, mande um comentário!
- Problema E: Polar Bear
LA ID: 4904. Link: Polar Bear. Dificuldade (0 a 10): 3 Assunto: Grids
Esse problema é de Grids e, aparentemente, bem complexo. Logo que você abre o problema, tem medo do grid circular que aparece, com uma divisões estranhas, contudo esse tipo de grid é para ser tratado praticamente igual a um grid quadrado, o qual nós estamos mais acostumados a lidar. Não entendeu? Se você prestar atenção, vê que cada célula (sem contar as centrais e as de borda) possuem exatamente 8 vizinhos, como em um grid quadrado, mudando somente o fato de que é circular, ou seja, a última “coluna” é vizinha da primeira. Nesse caso, é só preciso tratar os casos especiais, que são descritos no próprio enunciado! Depois de montar o grid, é só fazer a simulação de um Jogo da Vida, assim como nós aprendemos a fazer em OCaml, no 1º semestre do curso (para o pessoal que entrou até 2010, como o meu caso). Alguma dúvida na minha explicação? Mande um comentário!
- Problema F: Pro-Test Voting
LA ID: 4905. Link: Pro-Test Voting. Dificuldade (0 a 10): ? Assunto: ?
Não conseguimos fazer esse problema. Qualquer dica, mande um comentário!
- Problema G: Vampires!
LA ID: 4906. Link: Vampires!. Dificuldade (0 a 10): 2 Assunto: Grids
Esse é o problema mais fácil do contest, envolvendo um grid simples (quadrado) e alguma ideia de como percorrê-lo. Acredito que a única confusão que pode ser feita no problema é tentar partir de cada espelho para chegar nos vampiros e ir armazenando esses encontros nos espelhos, pois deixa a codificação mais complexa e a eficiência do algoritmo menor. A melhor abordagem, pelo menos na minha opinião, é a de partir de cada vampiro até os espelhos e verificar para quais direções ele teria problemas. Fácil, não? Se tiver dúvidas, nos mande comentários!
- Problema H: We’ve Got Chemistry, Babe
LA ID: 4907. Link: We’ve Got Chemistry, Babe. Dificuldade (0 a 10): 7 Assunto: Sitemas lineares, Eliminação de Gauss-Jordan
Esse é certamente o problema mais trabalhoso da competição, tanto é que somente os 2 primeiros lugares da regional que conseguiram resolvê-lo. No entanto, como não estávamos com ideias para os demais problemas, partimos logo para o que a codificação seria mais demorada. A ideia inicial desse problema é conseguir entender como o balanceamento de uma equação química pode ser reduzido a resolução de um sistema linear e esse fato deve a tratar cada coeficiente a ser encontrado como uma variável e cada elemento como uma equação diferente. Além disso, como o problema pede somente os casos de balenceamento único, deve-se considerar somente as situações em que há apenas uma variável livre no sistema e também ignorar os casos em que são encontrados coeficientes não-positivos. Depois de toda essa ideia (e um código já bem extenso), esse problema ainda possui uma leitura de dados bem complexa e trabalhosa, fazendo com que o código cresça mais um bocadinho… Conseguiu fazer? Qualquer dúvida, pode nos perguntar!
E foi esse nosso segundo encontro de treinamento para a Maratona de Programação 2011! Espero que tenham gostado dos comentários e nos vemos na próxima terça-feira, para mais uma competição! (lembrando que agora que o BOCA foi instalado nos servidores do LCC, graças a Edwyn, nossas competições poderão ficar ainda mais realísticas).
Posts interessantes:
- Waterloo Contest 2009 – Fall 2
- 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ê, fez a competição do East Central Regional 2010? Conseguiu fazer quais questões? Deixe seu comentário com algumas dicas ou dúvidas!
Helton de Melo Duarte
“Mas estende a tua mão, e toca-lhe em tudo quanto tem, e verás se não blasfema de ti na tua face! [...] Em tudo isto Já não pecou, nem atribuiu a Deus falta alguma.” Jó 1.11,22
