Treino Algoritmos Clássicos 1

Treino de Algoritmos Clássicos 1

Status desse analysis: 0% completo =(

Quick-ref link para os problemas:

Testing the CATCHER (UVa 231)

Esse é um exemplo de um dos problemas mais clássicos de programação dinâmica, o Longest Increasing Sequence (muitas vezes abreviado por LIS) – nesse caso, é uma non-increasing sequence, mas vocês vão ver que dá na mesma. Tem muitos e muitos jeitos de fazer esse problema, eu vou apresentar o que eu sou mais familiar com, mas depois vou ver se falo sobre os outros que eu lembro.

Primeiro, vamos enunciar o problema: temos um vetor v com n números e queremos o tamanho da maior subsequência não-crescente que pode ser formada nesse vetor. Lembre-se que uma subsequência são números que aparecem na mesma ordem no vetor original, mas que não necessariamente não consecutivos, por exemplo, se v = {1,5,3,2,4,6}, uma sequência válida é {1,3,2,6}, enquanto {5,1} não é porque houve uma reordenação dos elementos.

Como qualquer problema de programação dinâmica, queremos achar um estado que guarda só o necessário – se estamos montando uma sequência decrescente, é importante sabermos quais elementos podemos adicionar a ela, então basta sabermos qual é o último elemento; dado que a sequência toda está correta (ou seja, é não-crescente), basta adicionarmos o próximo elemento menor ou igual para manter a corretude. Sabendo que nossa indução depende só do último cara, podemos fazer um estado assim:
f(i) = tamanho da maior sequência que TERMINA em i (ou seja, que obrigatoriamente inclui o i-ésimo elemento)

Quando estamos em i, queremos ver qual a maior sequência que podemos completar, então:
f(i) = max (f(j)+1), com j=0..i-1 e v[i]<=v[j]; se não houver nenhum cara assim, f(i)=1, porque sempre podemos começar uma nova sequência de i
Veja que para uma subsequência crescente, basta mudar a condição para v[i]>=v[j]
Daí, nossa resposta fica max f(i), i=0..n e o algoritmo fica O(n^2)

Outra abordagem O(n^2) bastante bacana é fazer LCS com a sequência ordenada (http://en.wikipedia.org/wiki/Longest_common_subsequence_problem não vou detalhar LCS aqui, vou deixar pr'um problema específico do tema)

Existem versões de LIS que rodam em tempo O(n log n), mas não é necessário para esse problema – para os curiosos: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Minha solução: http://pastebin.com/8cBB2NPe O(n^2)

Dividing Coins (UVa 562)

Esse problema é um algoritmo conhecido por mochila binária (knapsack, na versão em inglês – http://en.wikipedia.org/wiki/Knapsack_problem). É um algoritmo extremamente importante em programação dinâmica. Apesar de estar bem descrito na página, eu vou reescrever a recursão aqui pra fazer comentários sobre.
A mochila clássica, na verdade, é um pouco diferente desse problema - o enunciado é assim:
Você tem um conjunto de n objetos com custos c[i] e valores v[i] e uma mochila com capacidade W; você quer montar a mochila de maior valor que o custo de todos os itens que existem dentro dela não ultrapasse W.

Vamos começar com uma mochila com 0 objetos, que obviamente tem valor zero; coloque os objetos numa fila de ordenação arbitrária (arbitrária mesmo). A primeira solução que deve vir à cabeça (deve mesmo) é testar todos os subconjuntos, o que é um algoritmo exponencial, (2^n)*n (o n extra é para somar os custos e valores).

É, isso não funciona pra muitas coisas – vamos melhorar isso. O que precisamos guardar aqui? Candidatos são: o subconjunto que estamos considerando, o peso da mochila e o valor dela. O subconjunto vai servir para fazermos a indução sobre os itens, ou seja, conseguir colocar um cara de cada vez. Pra cada cara que quisermos colocar, temos que saber quanto ainda falta de mochila para ver se dá ou não pra colocar o cara.
Dado que você tem o subconjunto que você está usando e o peso que você quer ocupar, é bastante claro que você quer a mochila mais valiosa, até porque, se você puder alterar o valor da sua mochila para mais sem alterar o peso, aquela obviamente não era a mochila ótima. Finalmente, temos um estado:
f(subconjunto, peso) = máximo valor que eu estou usando;
O subconjunto a gente geralmente representa como um índice, mas é implícito que estamos falando do subconjunto de [0..i].

Concluído o estado correto, a indução sai quase que por inércia. O caso base, em particular, é bastante óbvio: a melhor mochila (e a única) com o conjunto vazio tem valor 0. Agora a recursão – para isso, passo indutivo 101: imagine que você tem todas as informações sobre as mochilas usando o conjunto [0..i-1] e está tudo certinho. Daí, você quer adicionar o cara i, para começar a considerar o conjunto [0..i]. Da mesma forma que o brute force com todos os subconjuntos, você pode colocar o cara i ou não:

se w+c[i]<=W, ou seja, se o cara i cabe na mochila
f(i,w) = max(f(i-1,w), f(i-1, w+c[i])+v[i])
caso contrário
f(i,w) = f(i-1,w)

Ah, é, acho que já deve ter ficado claro, mas é bom explicitar, de qualquer forma: a resposta é o maior valor que você consegue usando o conjunto todo, ou seja, max(f(n-1,w)), com w=0..W

Pronto, é isso – agora vamos olhar pro nosso problema, efetivamente: queremos saber, dado um conjunto de moedas c, como conseguimos particionar essas moedas em dois conjuntos de forma que a diferença seja mínima; parece que não tem nada a ver, não? Não tem custos e valores, você tem só valores, right? Pois é, mais ou menos.

Ignore por um momento que não podemos indexar vetores negativamente e pense no seguinte estado:
g(i,p) = é possível, com o conjunto [i..0], fazer com que o primeiro cara tenha p (valor da soma de moedas) a mais que o cara dois;

Bem parecido, usando o "peso" como índice e tal; a recorrência é parecida, também
g(i,p) = g(i-1,p-c[i]) //isso equivale a dar essa moeda pro segundo cara
g(i,p) = g(i-1,p+c[i]) //a moeda vai pro primeiro

Daí, a resposta é um bocado diferente, mas é bastante intuitiva: você quer w tal que abs(w) seja mínimo para todos os valores onde g(|c|-1,w) é verdadeiro. Acredito, inclusive, que por simetria (o primeiro e o segundo cara são intercamb, você possa só olhar pros valores positivos.

Legal, agora vocês podem fazer o problema! Não, mentira, sabe por quê? Não é nem pela indexação positiva, é pelo limite de memória. Se vocês fizerem a conta, ele dá um bocado alto, mesmo se você usar bool: fica (2*500*100)*100, onde 500*100 é a soma máxima, o 2* é para lidar com os valores negativos e o 100 é o tamanho do conjunto – isso sem folga… resultado? alguns pra mim =)
Tá, vamos abordar outra recursão, que é um truque bastante usado por todos os caras very fodas, em particular eu li pela primeira vez em USACO, num editorial do Neal Wu. Vocês concordam que tudo que vocês não vão dar pro primeiro cara, vai pro segundo? Então vamos manter a soma de todas as moedas numa variável sum e mudar um pouco nosso estado e recursão:

h(i,p) = é possível, com o conjunto [i..0], fazer o primeiro cara ter p;

Dado que você entendeu as recursões lá de cima, essa goes without saying, quase:
h(i,p) = verdadeiro se h(i-1,p) ou h(i-1,p-c[i])
E a resposta fica o melhor que você consegue da diferença, ou seja, para cada p que tenha h(|c|-1,p) == true, queremos o que minimiza abs((sum-p)-p).

Good, eu até codei isso, está aqui: http://pastebin.com/bpJvremN
Maaas… isso ainda não passa no limite de memória; oh, well… e aqui entra uma das otimizações de memória MAIS usadas da vida em programação dinâmica – reparem que para calcular cada linha, vocês só precisam da linha anterior (i só depende de i-1), então você pode só guardar a linha que você está calculando (óbvio) e a última – acabou.
(eu tenho que acertar a implementação e colocar aqui)

Agora, o Andrey, numa das aulas dele, citou uma outra otimização que é muito específica, mas é muito, muito bacana e talvez seja útil na vida de vocês – foi minha primeira implementação para esse problema. O truque é o seguinte: uma vez que você muda o estado de um índice na recursão acima, ele vai sempre ser verdadeiro, então basta você guardar quais que você já achou como verdadeiro (porque h(i,p) = verdadeiro se h(i-1,p). Isso só tem um problema: como você está atualizando o mesmo vetor que você está usando de referência, você pode sem querer atualizar um índice que você… (continua)

Minha solução:

Expensive Subway (UVa 11710)

Minha solução:

The Orc Attack (UVa 10793)

Minha solução:

No Brainer (LiveArchive 3077)

Minha solução:

Getting in Line (UVa 216)

Minha solução:

Il Gioco dell'X (UVa 260)

Minha solução:

Optimal Array Multiplication Sequence (UVa 348)

Minha solução:

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