Analysis230312

North America – Greater New York 2008

Para facilitar a referência à essa prova, ela está aqui no Live: http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=332. Eu coloquei as questões em ordem que elas aparecem na prova original, então elas não correspondem a como está no Ahmed (ele ordena por ordem de dificuldade os problemas, por algum motivo).
Status do analysis: 66% completo

Sixth Grade Math (LA 4232)

Essa questão é muito straight-forward, se você sabe o algoritmo de Euclides para o GCD (previsivelmente descrito em: http://en.wikipedia.org/wiki/Greatest_common_divisor) e saber que lcm(a,b) = (a*b)/gcd(a,b). Se você não sabe, estude um pouco o documento de teoria dos números que eu escrevi a partir de uma aula do Fleischman – não está completo, mas acho que está legal: https://docs.google.com/document/d/1wTgHL_mXnUGZoQJSo3xl9Muuk5An4Sr_yT9LJnz2oXA/edit
Minha solução: http://pastebin.com/GTnYBh9b

Cryptoquote (LA 4233)

Quem fez o treino de implementação até o final comeu esse problema de café-da-manhã: você recebe um mapeamento de caracteres em uma string e uma string a ser decodificada. A partir daí, é só substituir cada caractere pelo seu caractere mapeado. Se me lembro direito, nem pegadinhas esse problema tem, então code com calma que é AC.
Minha solução: http://pastebin.com/XzYVhVx9

Binary Clock (LA 4234)

Outro problema de implementação pura: você recebe uma hora e você tem que imprimir essa hora num formato específico. Além do jeito que está na minha solução (eu sempre faço n&(1«i)), é possível verificar se o bit i está ligado em um número n fazendo (n»i)&1. Nesse caso, fica até melhor, já que, em vez de (n&(1«i))?1:0, eu poderia só escrever (n»i)&1 – cortesia do Júlio, esse outro jeito.
Minha solução: http://pastebin.com/hEGPLAhv

Recursively Palindromic Partitions (LA 4235)

Acredito que esse seja o primeiro problema que é preciso pensar um pouco nessa prova: você precisa contar o número de partições recursivamente palidromas – eu sei que isso é o título, mas só relembrando. De qualquer forma, problemas de contagem geralmente significam programação dinâmica e esse não é muito diferente (especialmente porque existe a palavra recursivo, isso é quase um neon para você saber que existem subproblemas).
Então, vamos examinar a indução por trás desse problema: existe 1 jeito de representar o número 1 – esse é nosso caso base.
Vamos tentar quebrar o número n em 3 partes sempre, duas iguais (afinal, temos que ter palíndromos) e o meio (o caso 2: 1 1 vai passar a ser representado por 1 0 1). Para isso, n deve ser 2*x+y, onde x são as pontas e y é o meio, x é inteiro positivo e y é inteiro não negativo. Note que a quantidade de jeitos de representar n com y no meio é o número de representações recursivas palidromas de x. A partir daí, concluímos que se tentarmos todos os x's possíveis, somarmos as representações deles e adicionarmos a representação do n sozinho, temos nossa resposta. Como existem muitos recalculos nesse procedimento, podemos evitar isso salvando os resultados num vetor (memoização).
Finalmente, a equação de recorrência agora limpa:
Se n==1, f(n)=1
c.c. f(n)=1+somatório f(x), onde x>0 e y=(n-2*x)>=0
Minha solução: http://pastebin.com/DjzcYmba

Text Messaging Improvement? (LA 4236)

Outra programação dinâmica legal de fazer, só que essa é mais esperta um pouco. Temos que minimizar os keypresses mantendo a ordem das teclas (thank goodness, se não o problema ia ser impossível), mas temos uma limitação de quantidade de teclas para serem usadas. Além disso, só podemos colocar 8 letras em cada tecla (cuidado com isso, eu devo ter tomado uns 2 WAs por causa dessa informação escondida no final de um parágrafo).
Como precisamos manter a contagem das teclas que já usamos, além de em que tecla estamos que é tradicional de grande parte das pds (o 'i' do estado), precisamos manter o número de teclas também, então fixamos no estado f(i,k) = quantidade média de keypresses até i, inclusive, sendo que eu fechei a tecla k em i (ou seja, não quero mais adicionar letras pra tecla k).
Toda vez que a gente coloca uma letra numa tecla, temos que apertar todas as anteriores mais aquela, por exemplo, considere a função key(i,j) = número de keypresses necessários na tecla que inclui as letras de [i,j]:
key(i,j) = 1*p(i)+2*p(i+1)+…+(j-i+1)*p(j), suponha i<=j

Isso já dá uma boa cola de como fazer o caso base:
f(i,1) = key(0,i), para i>=0 e i<8 (lembre-se da restrição de usar até 8 teclas)

Para a indução, temos:
f(i,k) = mínimo f(j-1,k-1)+key(j,i), para j>=0 e i-j+1<=8
Essa indução implica começar todas as teclas k de um j dentro das restrições e ver qual é o melhor.
Finalmente, esse problema pede uma recuperação de resposta, que pode ser feita guardando qual o início de intervalo (o j, na minha recorrência acima) que deu a melhor opção para cada f(i,k). Tendo o intervalo, você pode só percorrer esse vetor, lembrando que o final do intervalo corrente é o início do próximo intervalo-1.
Minha solução: http://pastebin.com/SrxfByTR

Extended Normal Order Sort (LA 4237)

Ainda não acertei esse problema…

Area of Polycubes (LA 4238)

Esse problema é grande parte implementação (especialmente a parte de ver se um cubo é válido), mas a parte de calcular a área, apesar de parecer complicada, tem uma idéia muito bonitinha e simples por trás: cada cubo que você coloca contribui com 6 unidades de área novas, se ele não tiver nenhuma adjacência – quando ele junta com a face de outro cubo, ambos perdem 1 unidade de área em contribuição. Sabendo disso, podemos só contar quantas adjacências tem cada cubo e fazer 6*(número de cubos)-(somatório das adjacências de cada cubo). Na minha solução, eu implementei isso com a contagem de faces livres pra cada cubo, mas isso é muito desnecessário (usa memória a toa), então fiquem à vontade para mandar uma solução sem esse desperdício idiota de memória
Minha solução: http://pastebin.com/T1MTWtPa

The Two Note Rag (LA 4239)

Ainda não fiz…

Joe's Triangular Gardens (LA 4240)

Eu ainda não resolvi esse problema, mas a melhor análise possível desse problema é feita pelo Fidel, na Escola de Verão de Campinas: http://www.livestream.com/escoladeverao2012/video?clipId=pla_5d774d10-e428-4126-82a4-61c082fd5fa1&utm_source=lslibrary&utm_medium=ui-thumb
(a discussão desse problema em particular começa em 24:13)

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