Analysis - Google Code Jam 13, Qualification Round

Questões: https://code.google.com/codejam/contest/2270488/dashboard#s=p0
Scoreboard: https://code.google.com/codejam/contest/2270488/scoreboard#vf=1 (o scoreboard do GCJ permite que você baixe as soluções corretas de todos as pessoas, então por isso que ele é interessante aqui)

A: Tic-Tac-Toe-Tomek

Problema estritamente de implementação – é suficiente checar linearmente cada row, cada column e cada diagonal para passar nos casos large (e passa com folga!)

Solução - small e large, em C++ (Luiza): http://pastebin.com/UTCKTKuA

B: Lawnmower

Uma simulação O(n^3) é suficiente para passar esse problema, ou seja, você setar a grama em um tamanho máximo, procurar o maior quadrado que precisa de corte e ir fazendo isso até que não seja possível cortar um quadrado (por que vai interferir com outros) ou você tenha terminado – a prova de corretude é óbvia

Solução - small e large, em C++ (Luiza): http://pastebin.com/1Z1Ek9YY

O Ruan e o Hugo tiveram uma ideia mais esperta: em vez de simular, que gasta o dobro de memória, eles só checam para cada quadrado se é possível cortá-lo na altura certa, ou seja, se ele é o menor quadrado da sua linha ou coluna; continua O(n^3), mas o código é bem menor.

Existe uma outra solução que é O(n^2) em tempo. Basicamente, se você "inverter" o seu raciocínio, uma condição para ser possível cortar é que todo quadrado deve ter a máxima altura da sua coluna OU da sua linha.

Solução - small e large, em C++ (Fleischman): http://pastebin.com/yybASUJ2

C: Fair and Square

Para o small, é suficiente você, para cada intervalo, checar cada número se é quadrado perfeito, se é palindromo e se a raíz é palindroma.
(acho que o Hugo tem uma implementação com isso em Python, mas não tenho certeza)

Para o input large 1, você tinha que ser um pouco mais esperto, mas não muito – bastava você sacar que:
1. você poderia iterar nas raízes dos números, o que baixava o intervalo máximo pra 10^7 (totalmente fazível)
2. A computação dos números válidos poderia ser feita de uma vez só e guardada num array – antes de rodar os testes. Para cada teste, bastava uma busca binária no limite superior e inferior para saber quantos números tinham

Solução - small e large 1, em C++ (Luiza): http://pastebin.com/QSRudx55

Para o input large 2, era necessária uma ideia bem mais esperta – felizmente, o Maurício deu a cola numa discussão sobre:
"Maurício Collares Neto Renato Parente: http://oeis.org/A057135 dá uma caracterização legal para os palíndromos, que já foi discutida aqui. Os palíndromos (fora o 1, 4 e 9) só podem ser da forma 20…02, 20…010…02, XX, A0Â, A1Â ou A2Â, onde A é um número formado por dígitos 0 e 1, com no máximo quatro 1s e no máximo 25 dígitos (por causa do B <= 10^100); Â denota o reverso de A. Depois disso é só tratar os bignums direito (eu usei a biblioteca gmpxx) ao testar se o quadrado é palíndromo.
2 hours ago · Edited · Like

Maurício Collares Neto O bom desse problema é que ele tem duas lições legais para Code Jam (que não valem para Maratona, em geral):

1) OEIS é sempre seu amigo; o programa que dá pra fazer ingenuamente pro large1 gera uma lista de palíndromos que pode ser facilmente procurada lá;
2) gmpxx é uma lib bacana de bignum pra C++ Todos os operadores estão sobrecarregados pra fazer exatamente o que você espera que eles façam."

Solução - small, large 1 e large 2, em Python (Fleischman): http://pastebin.com/FcPRbinc

D: Treasure

Para o input small, era suficiente fazer uma PD com estado dp[bitmask dos baús abertos]=é possível. Como, a partir dos baús abertos, você já sabe que chaves você tem, você não precisa de mais nada no estado. A partir daí, era fazer um código que tornasse a recuperação lexicograficamente mínima, o que pode ser feito garantindo que os estados sejam preenchidos em ordem contrária (ou seja, o dp[0] é o cara que tem a resposta e é o último a ser preenchido). Infelizmente, não posso dizer mais detalhes da solução porque ainda não acertei ela.

Código WA – small, em C++ (Luiza): http://pastebin.com/sVKUh8hc

O input large ainda está em discussão

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License