Analysis040412

Africa/Middle East - Arab and North Africa 2005

Eu escolhi essa prova ao acaso, mas acabei achando ela um tanto fácil – é uma boa pra quem quer treinar implementação e idéias simples, mas não tem nenhuma modelagem legal (não que eu lembre, pelo menos).
Stats do analysis: 70% completo
Link para a prova no Live Archive: http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=208

The Earth is Flat! (LA 3533)

Começar uma prova com um parser é quase maldade, mas bom, anyway… essa questão foi uma das que eu mais demorei, porque parsers em geral são complicados de get it right. Aqui tem alguns truques: o primeiro é o jeito que eu estou lendo números naturais – quando eu acho um dígito, eu leio ele caractere a caractere e retorno o número com uma função – recomendação do professor Fidel na aula de parsers dele (se vocês tiverem duas horas sobrando no dia de vocês, assistam porque a aula é excelente: http://www.livestream.com/escoladeverao2012/video?clipId=pla_14873438-74ab-46c3-89da-946427b56581&utm_source=lslibrary&utm_medium=ui-thumb). Além disso, usei a definição que ele tinha (uma espécie de gramática que ele dá no problema) de expressão e só – mesmo assim me tomou pelo menos uma hora to get it right… Ah, sim, e como ele não especificou o tamanho da string, eu li caractere a caractere (achei que era melhor não arriscar).
Minha solução: http://pastebin.com/aNwkn5Dy

The Double HeLiX (LA 3534)

Essa questão é muito bonitinha e bastante clássica, lembra muito uma programação dinâmica que é o primeiro exemplo de uma das versões do Cormen (esse aqui: http://books.google.com.br/books?id=NLngYyWFl_YC&pg=PR21&lpg=PR21&dq=first+edition+cormen&source=bl&ots=BxQpHB8mI6&sig=sUOEE3bp5Jb7gj69Fwd_7EOmppw&hl=pt-BR&sa=X&ei=-0B_T_F-i6DyBMmFvdsH&ved=0CFIQ6AEwBg#v=onepage&q=first%20edition%20cormen&f=false, página 324). Deve ser por isso que eu acabei fazendo a memoização, mesmo que eu não tivesse muita certeza se ela era necessária (como cabia tranquilo na memória, não sei se isso é problemático). De qualquer forma, vamos analisar a recorrência, porque ela será a mesma com ou sem memoização:
O estado é f(i,idx) = maior soma que eu consigo fazer a partir da posição i da fita idx.
Do jeito que eu formulei inicialmente, a recursão chegava no final da fita e voltava calculando os melhores (por isso a implementação top-down), fazendo com que a resposta seja o melhor de f(0,0) e f(0,1), porque eu tenho que considerar que eu posso começar em qualquer uma das fitas.
f(i,idx) = fita(idx,i) +
se o número em fita(idx,i) é um ponto de interseção, eu posso escolher se vou mudar de fita ou não, então:
max(f(i+1,idx),f(k+1,(idx da outra fita))), onde k é a posição de fita(idx,i) na outra fita – como ele diz que as fitas são estritamente crescentes, eu não preciso me preocupar com o caso de múltiplas interseções.
caso contrário, eu só posso continuar na mesma fita, então f(i+1,idx)
Como as fitas estavam ambas ordenadas, eu fiz uma busca binária para encontrar as interseções, porque acho que busca linear ia estourar o tempo – eu codei a busca na mão e tomei um WA por causa disso, então talvez vocês queiram usar a função lower_bound da biblioteca algorithm.
Minha solução: http://pastebin.com/Nis25JVp

Alpha of Degree k (LA 3535)

Ainda não fiz esse carinha…

Sort that Queue (LA 3536)

Não fiz ainda…

Still Johnny Can't Add (LA 3537)

Para esse problema, eu assumi algo que é meio intuitivo para mim, mas eu não provei, então eu fiquei com um bocado de medo de mandar essa idéia até a hora que era ou isso, ou o parser. Eu assumi que se todos os resultados estavam entre -10000 e 10000, logo todos os operandos estariam também. Aí, eu fiz um brute force "esperto" – "esperto" porque eu tentei todos os operandos possíveis para cada linha, só chutei um fiz a conta para achar os outros (o que reduziu MUITO minha complexidade final). Como eu só estava testando 2*10^4 números, eu podia testar todas as possibilidades para o primeiro, achar os outros e testar a tabela inteira (se você fizer a conta, isso dá mais ou menos 2*10^6 operações, o que é razoável)
Minha solução: http://pastebin.com/frZukJ95

Newton's Apple (LA 3538)

Essa questão me irritou, porque ele te dá o jeito de resolver (tem uma equação recursiva bonitinha que é só você escrever e foi), mas te dá a árvore do jeito mais inconveniente possível. Então o problema não é verificar a validez realmente e sim montar a árvore. Dito isso, vamos nos concentrar nessa tarefa específica. Se você tentar montar na ordem que ele dá, você vai ter uma dor de cabeça, porque muitas vezes não dá pra dizer se você mudou de filho ou onde você está exatamente… mas, se você ler a string ao contrário, ele está percorrendo a árvore em pré-ordem ao contrário (that is, raiz-direita-esquerda, não raiz-esquerda-direita como pré-ordem tradicional)! Opa, ótimo! Então é só você pegar a árvore toda, ler a string ao contrário, montar sua árvore com uma dfs besta e checar a propriedade – não esqueça de testar bem a função que monta a árvore. Ah, e uma coisa: como maratonistas e ponteiros em geral não se dão, como todas as árvores que vocês vão ver na maratona, eu estou usando aquela representação em vetor (vetor estático!!) típica de heaps, onde os filhos de i são 2*i+1 e 2*i+2. Algumas pessoas preferem começar a árvore do nó 1 e fazer 2*i e 2*i+1, tanto faz, só ache um jeito e stick with it pra você não se confundir =)
Minha solução: http://pastebin.com/AhEaTMc7

The Euclidian Clock (LA 3539)

Para essa questão, basta você mudar a hora de base (12*100*60*60 cabe num inteiro simpaticamente) e fazer algumas regras de três com ângulos. Para não ter problemas de precisão, sempre divida no final e use acos(-1.0) como PI (em vez de fazer um define com poucas casas, esse jeito é muito melhor). Piece of cake.
Minha solução: http://pastebin.com/nU8AVRRz

Chop Ahoy! Revisited! (LA 3540)

Se você calcular o tamanho do conjunto solução desse problema, você vai chegar em 2^24, que é grande demais pra fazer muita coisa (16777216, argh, so close…). Mas, como o próprio problema faz cortes nesse conjunto (a soma tem que ser maior ou igual à soma do último), você vê que o conjunto fica bem menor, como queríamos, para fazer um backtracking – uhu! A partir daí, é só ir descendo na árvore e, quando você terminar o conjunto, adicionar +1 à sua contagem de conjuntos válidos.
Minha solução: http://pastebin.com/6XeYLsdm

What's Your Logo? (LA 3541)

Ainda não fiz…

It's All About Three (LA 3542)

Esse problema é mó feliz – basicamente um exercício para fazer o Crivo de Erastótenes e iterar pelos primos dele. Como todos os números são menores que 10^6, é iterar mesmo, conferindo se os fatores primos deles têm %10==3 (que é equivalente a ter o último dígito 3). Talvez tenha um jeito mais simples de implementar, até, mas esse é muito rápido de codar e funciona bem.
Minha solução: http://pastebin.com/MagiuuB1

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