Resoluções de Ano Novo - Edição 2013

Retomando uma tradição interrompida deste blog, segue um balanço das resoluções anteriores (de 2010) e um novo conjunto de resoluções para este novo ano.

Google Code Jam 2012

Começam hoje, às 16h, as inscrições no Google Code Jam 2012. A inscrição pode ser feita até o final da rodada de qualificação (que ocorrerá nos dias 13 e 14 de abril).

Detalhes no site oficial: http://code.google.com/codejam/schedule.html

Google Code Jam 2011: QR_D - GoroSort

O problema final da rodada da qualificação foi o mais difícil. Além disso, veio recheado de malvadezas, da descrição cheia de detalhes desnecessários ("Goro has 4 arms." - e daí?) a uma saída com seis casas decimais ("Answers with an absolute or relative error of at most 10-6 will be considered correct") para uma resultado que é sempre inteiro.

Google Code Jam 2011: QR_C - Candy Splitting

No terceiro problema da rodada de qualificação a coisa esquenta. Parece ser um problema de maximização que requer uma solução a base de programação dinâmica - mas será isto mesmo?

Quando eu finalmente enxerguei a solução soltei um palavrão em voz alta...

Google Code Jam 2011: QR_B - Magicka

O segundo problema da rodada de qualificação foi um pouco mais difícil que o primeiro, principalmente se você tentar fazer uma solução mais sofisticada e cometer erros primários (o meu caso).

Google Code Jam 2011: QR_A - Bot Trust

O primeiro problema da rodada de qualificação não foi difícil, para resolvê-lo bastou fazer uma simulação seguindo a descrição do problema.

Google Code Jam 2011: Qualification Round

Na sexta/sábado passado tivemos a rodada de qualificação do Code Jam 2011. Para quem não conhece esta competição e o seu formato, sugiro ver os meus posts anteriores.

Esta rodada foi um pouco diferente para mim. Eu não estava muito motivado, pensei até em não participar; acabei entrando no site somente no final da manhã de sábado. Ao contrário dos anos anteriores, foram quatro problemas. Uma primeira olhada rápida indicaram que os dois primeiros eram relativamente simples, o terceiro complicado e o quarto muito complicado.

Google Code Jam 2011: Inscrições abertas

As inscrições para o Google Code Jam de 2011 já estão com as inscrições abertas no site oficial. Se você não sabe do que estou falando, veja a minha cobertura dos anos anteriores.

As incrições vão até 7 de maio, ao témino da rodada de qualificação iniciada no dia anterior (com duração de 24 horas). Em seguida teremos três rodadas eliminatórias on-line, culminando com a final presencial no Japão. Além da fama, os 1000 melhores colocados na rodada 2 receberão uma camiseta e os 25 participantes da final ganharão prêmios em dinheiro variando de US$10.000 a US$100.

Minhas Aventuras com "Parsing" - Gramáticas

Estou retomando os problemas do SPOJ Brasil (em preparação para o Google Code Jam deste ano) e o primeiro que eu revi foi o "ET Phone Home". Eu já tinha tentado este problema antes, sem sucesso. Hora de estudar um pouco de teoria... Este problema envolve parsing - a análise de textos com base em uma gramática. Eu já falei um pouco sobre isto aqui no blog, mas dentro do contexto de compilar uma linguagem de programação adequadamente simples.

Os livros sobre o assunto são caros (versões "físicas" acima de US$100 e versões eletrônicas acima de US$50 na Amazon). Existe bastante material na web porém a maior parte é confusa e existe pouco código de exemplo. Daí a origem desta série de posts para organizar as minhas ideias e, se tudo der certo, ajudar a outros interessados.

Google Code Jam 2010: Encerrado

Na semana passada ocorreu em Dublin a final do Google Code Ja, 2010. O campeão do ano é o russo Egor Kulikov. O campeão dos dois anos anteriores chegou perto mas acabou em quarto.

Nesta última rodada foram seis problemas; ninguém conseguiu resolver completamente os dois últimos.

Os problemas e a análise oficial estão em http://code.google.com/codejam/contest/dashboard?c=801485

Google Code Jam 2010: Making Chess Boards

Making Chess Boards (fazendo tabuleiros de xadrez) foi o terceiro e último problema da rodada !C do Google Code Jam 2010. Segundo a análise oficial, seria uma combinação de parsing, programação dinâmica e truques espertos. Embora eu tenha resolvido com sucesso o problema, minha solução envolve somente parsing e força bruta.

Google Code jam 2010: Load Testing

Load Testing (teste de carga) foi o segundo problema da rodada 1C. Uma distração minha neste problema me impediu de obter a pontuação máxima na rodada.

O enunciado (que você encontra aqui) parece confuso na primeira leitura; felizmente os exemplos são mais claros. Tentando colocar de uma forma simples:

• Você precisa determinar qual o número mínimo de testes de carga a serem feitos em um site.
• Os testes são concluídos quando sabemos que o site suporta, dentro de um fator C, pelo menos P participantes ou uma quantidade X < P
  
• Suportar X participantes dentro de um fator C significa que você sabe que o site suporta uma carga a mas não uma carga a*C com a < P < a*C
  
• Inicialmente você sabe que o sistema suporta uma carga L mas não uma carga P.

Google Code Jam 2010: Rope Internet

Rope Internet foi o primeiro problema da rodada 1C. O enunciado oficial está aqui; considere a figura abaixo que mostra uma série de segmentos de reta unindo dois prédios:


O problema consiste em, dadas as alturas A e B das extremidades das retas, determinar quantas intersecções ocorrem. Para simplificar, é garantido que nenhum par de segmentos começa ou termina na mesma altura e que nunca ocorre de mais de dois segmentos cruzarem no mesmo ponto.

Google Code Jam 2010: File Fix-It

File Fix-It foi o primeiro problema da rodada 1B, e um dos mais simples da competição.

O enunciado completo está no site oficial, mas pode ser resumido da seguinte forma: o seu programa recebe duas listas de nomes de diretório (todos a partir da raiz e usando '/' como separador das partes), uma com os nomes dos diretórios que já existem e outra com os nomes dos diretórios que se deseja criar, e deve informar quantas operações de criação de diretório (mkdir) serão necessárias (considerando que cada operação cria somente a última parte do nome).

Google Code Jam 2010: Rodada 2

Neste sábado (5/junho) ocorreu a rodada 2 do Google Code Jam 2010. Estavam classificados para a rodada 3000 competidores; apenas os 500 melhores avançaram para a rodada 3. Eu não estava muito otimista quanto a passar (no que estava correto), ainda mais que nas últimas semanas o rítmo no trabalho tem sido intenso (o que explica também a redução dos posts aqui no blog).

Quando começou a rodada, meu primeiro objetivo era ver se tinha algum problema que eu tivesse uma boa chance de resolver; se não tivesse eu ia simplesmente desistir. Foram 4 problemas, com 2,5 horas para solução. Numa primeira olhada os três primeiros problemas pareciam atacáveis, o quarto envolvia uma geometria pesada. Embora os enunciados fossem razoavelmente simples, nos primeiros 20 minutos ninguém tenha resolvido nenhum problema (nem mesmo um small input). A análise oficial dos problemas pode ser vista aqui.

Eu me interessei pelo problema C (Bacteria), uma versão simplificada do clássico Life. Uma solução "força bruta" capaz de resolver o small input parecia simples. E realmente era, mas levei uma hora para implementar. O problema é que o large input era simplesmente imenso. Tive uma ideia para tentar reduzir a memória necessária e gastei uns 50 minutos implementando uma das minhas soluções complexas, cheia de alocação manual de memória. Para minha surpresa, o código funcionou praticamente de primeira... mas se mostrou muito mais lento que a força bruta! Eu cheguei a imaginar uma terceira solução, mas não tinha certeza se conseguiria implementar nos 40 minutos restantes. Dando uma olhada na classificação, percebi que mesmo que conseguisse resolver o large input não ia dar para passar para a rodada seguinte e entreguei os pontos. Pela análise da Google, esta minha solução não deveria ser suficiente.

A rodada foi realmente difícil. Ninguém conseguiu a pontuação máxima. Somente 12 competidores enviaram uma solução para o large input do último problema, e somente 2 acertaram. Somente os seis primeiros acertaram todo o resto (somente um deles tentou o large input do problema D, mas estourou o tempo). O sétimo colocado acertou os problemas A, B e D, mas não teve tempo para o problema C. O último classificado conseguiu acertar o problema B inteiro e mais o small input do C em uma hora e meia, fazendo 31 pontos (o mesmo que eu teria obtido se tivesse conseguido resolver o problema C inteiro).

Minha principal conclusão da minha participação este ano é que usando C puro não vai dar para ir em frente. Para o ano que vem preciso estar preparado para usar uma linguagem com mais recursos.

Sobra a pendência de apresentar minhas soluções para os problemas que eu resolvi na rodada 1. Vamos ver se as coisas acalmam no trabalho e consigo preparar isto.

Ainda Vivo no Code Jam 2010

Bem, pelo menos estou melhor que no ano passado. A primeira rodada do Google Code Jam 2010 ocorreu neste fim de semana e consegui passar para a próxima fase.

Google Code Jam 2010: Theme Park

Theme Park (parque de diversões) foi o terceiro problema da Qualification Round do Code Jam 2010. O enunciado completo está no site oficial, mas o resumo é:

• "N" grupos de pessoas, cada um com g_i pessoas, passam o dia andando em uma montanha russa.
• Cada viagem da montanha russa suporta um máximo de "k" pessoas.
• A cada viagem os grupos vão entrando até que não caiba um grupo inteiro. Ao final da viagem os grupos voltam para o final da fila, mantendo a ordem.
• Ao longo do dia são feitas "R" viagens; cada pessoa gera uma receita de 1 euro por viagem.
• O problema é determinar a receita total.

Uma solução "força bruta", como implementar exatamente o que está escrito acima, é inadequada para o conjunto grande, onde podemos ter até 100.000.000 viagens e até 1.000 grupos.

Google Code Jam 2010: Snapper Chain

Snapper Chain ("cadeia de estaladores") foi o primeiro problema da Qualification Round do Code Jam 2010. O enunciado completo está no site oficial, mas o resumo é:

• O "estalador" (snapper) é um interruptor que, quando alimentado, muda de estado entre ligado e desligado quando alguém estala os dedos.
• "N" estaladores são ligados em série. O primeiro é ligado na tomada e o último a uma lâmpada.
• O problema consiste em determinar se a lâmpada estará acesa ou apagada após "K" estalos.

A solução de simular diretamente o funcionamento é inadequada para o conjunto grande, que pode ter até 30 estaladores tratando até 100.000.000 estalos.

Google Code Jam 2010: Qualification Round

O Qualification Round do Code Jam 2010 ocorreu de sexta às 20:00 até sábado no mesmo horário. Trata-se de uma competição de programação que já mencionei várias vezes aqui no blog. Foram três problemas, cada um com dois conjuntos de teste: um pequeno (que você pode tentar várias vezes e é corrigido na hora) e um grande (que você só pode tentar uma vez e só é corrigido no final). Para passar nesta rodada bastava acertar pelo menos um conjunto pequeno e um grande.

Lembrete: Code Jam 2010

A competição de programação Google Code Jam 2010 começa hoje (7 de maio) às 20:00. A rodada de qualificação fica aberta 24h e você pode se inscrever até o final dela.

A cobertura do Google Code Jam no blog está aqui.