Analysistreino100312

Treino de Complete Search e Backtracking

Esse aqui é pra galera que tem preguiça de implementar e ficar fazendo cortes no código até o problema passar. A parte dos calouros inclui o básico das técnicas, enquanto a dos veteranos tem vários truques muito legais na hora de abordar problemas de busca.
Status desse analysis: 72% completo

Link para os problemas

Parte dos Calouros

Ecological Bin Packing (UVa 102)

Se você leu o texto antes do enunciado de fato, você reparou que ele dá a dica, já, que alguns problemas de bin packing são NP-completo – isso é uma cola de "não tente nada melhor, não vai funcionar". Honestamente, eu diria ao contrário: mesmo se existir algo melhor, não tente porque não PRECISA! Lembre-se: a primeira coisa que é necessario fazer quando temos um problema com os limites que parecem pequenos é calcular o tamanho do conjunto solução dele. Aqui podemos ver que, se mantivermos as latas na ordem, o número de possíveis soluções é a permutação dos vidros nessas latas, ou seja, 3!. Como assumimos que cálculos até 10^6 passam no TL e 3!<10^6, podemos até ser bastante porcos em termos de implementação.
A segunda coisa é simplificar a implementação ao máximo. Honestamente, vocês não querem ficar escrevendo todas as possibilidades na mão – isso funciona, mas é um bocado chato. Na minha solução, eu mudei a ordenação inicial das garrafas para garantir que qualquer resposta que eu achasse já fosse a menor string lexicográfica possível (por isso que tem aquele swap) e eu só precisasse testar o número de garrafas. Além disso, como estamos testando todas as permutações, acredito que nada mais natural que usar a função de next_permutation.
Minha solução: http://pastebin.com/urjqnS4J

Lotto (UVa 441)

Esse problema, como tem um tamanho de conjunto fixo, pode ser resolvido com 6 fors aninhados, mas eu não pensei nisso originalmente e resolvi implementar a versão recursiva, que também garante a ordem lexicográfica, já que os números já estão ordenados no input. Ela é um pouco mais complicada que a versão iterativa, mas acho que vale a pena entender, já que grande parte dos problemas de combinatória vai usar uma estrutura parecida:
Eu tenho meu conjunto grande, s, e meu subset atual, que eu chamei de pos para aumentar a clareza do código. Para cada elemento de s, eu posso formar subsets usando ele ou não, então eu guardo duas informações na minha recursão: qual elemento que eu estou olhando para agora (eu chamei de it, para iterator) e qtd, que é a quantidade de elementos que eu tenho no meu subset. Se eu estou considerando usar o elemento corrente, eu vou para (it+1,qtd+1) e guardo o elemento corrente no vetor pos (para poder imprimir o vetor depois), caso contrário, eu vou para (it+1, qtd). Se qtd chegar no tamanho que eu quero (6), devemos imprimir o set e não precisamos mais tentar colocar ninguém (não queremos sets maiores que 6) e, se it>=n, acabaram os elementos a serem considerados no conjunto s, então eu preciso parar minha recursão também.
Veja que essa solução usa no máximo 2^13 operações, que está dentro do limite de 10^6 discutido anteriormente.
Minha solução: http://pastebin.com/WZfJBEDM

Quirksome Squares (UVa 256)

O primeiro reflexo aqui é iterar por todos os números de 2, 4, 6, 8 dígitos possíveis e checar a propriedade, mas com poucas contas, vemos que isso é caro demais computacionalmente (especialmente por causa dos números de 8 dígitos, lembre-se que eles são 10^8 números, que é bem maior que o 10^6 que tomamos como limite).
Porém, se você pensar um pouco mais, tem um corte muito bacana nisso: você só precisa ver números que são quadrados perfeitos, então basta iterar até sqrt(10^8) = 10^4 e ir elevando todo mundo ao quadrado para verificar a propriedade. No meu código, eu fiz com operadores módulo e divisão (geralmente é o jeito mais comum de fazer isso), mas você sempre pode printar o número para uma string (com sprintf) e separar ele dessa forma – aqui não me parece tão bom, mas em algumas situações é terrivelmente útil fazê-lo.
Minha solução: http://pastebin.com/cvvNRhgM

Don't Get Rooked (UVa 639)

Outro problema muito bonitinho, equivalente ao Sticker Collector Robot, pra mim: é um problema bom de treinar que não tem grandes pegadinhas e o output é muito simpático. Esse problema já é um pouco mais complicado, em termos de implementação e necessita de um pouco de paciência, assim como um pouco de pensamento sobre como é a melhor maneira. Eu pensei assim: primeiro, no tabuleiro máximo, eu posso testar até 2^16 configurações diferentes com torres (o que é equivalente a escolher para cada posição se eu vou colocar uma torre ali ou não) – vamos esquecer a validez, por enquanto, porque esse número é pequeno o suficiente para nos deixar testar todas as configurações e sua validez.
Da mesma forma que eu fiz no lotto, eu vou guardando a configuração atual na matriz e considerando as outras casas recursivamente – quando eu chego no final do tabuleiro, eu vejo se aquela configuração é válida ou não; se for válida, eu vejo se o número de torres que eu consegui botar é maior que o que eu já tinha colocado anteriormente e mantenho o máximo. Ótimo exercício de backtracking, esse problema.
Minha solução: http://pastebin.com/VcUmn1YE

Social Constraints (UVa 11742)

Aqui precisamos contar quantas configurações válidas temos, de novo, só que o conjunto solução é maior, porque a ordem das pessoas é o que está em jogo – não que isso seja um problema, já que o n máximo sendo 8 nos dá 8! possibilidades que é 40320 < 10^6. Good, se testar a validez for barato, podemos testar todas as configurações – com 20 restrições no máximo, temos um total de operações de 806400<10^6, então estamos safe (fora algumas constantes, mas geralmente consideramos 10^6 como ordem de grandeza)
Vamos usar next_permutation para testar todos os casos e, para cada caso, vamos testar a validez. Como eu não quero estrapolar o tempo, antes de verificar as restrições, eu salvo as posições de cada pessoa, o que me permite checar cada restrição em O(1) – talvez seja só paranóia minha, mas talvez você usar tempo linear para cada restrição estoure o tempo. Para cada configuração válida, aumentamos o contador e acabou o problema!
Minha solução: http://pastebin.com/8JQec5x3

Block Voting (UVa 435)

O Block Voting é o último problema do set dos calouros porque ele lida com mais uma técnica muito importante na hora de fazer complete searchs, que é iterar por bitmasks (e usar bitmasks, de forma geral), que é um skill muito importante (especialmente depois, quando formos lidar com programação dinâmica). Enfim, a idéia aqui é testar todas os conjuntos possíveis, mas p=20, o que significa que o número de conjuntos é grande é 2^20>10^6 e tem a mesma ordem de grandeza, opa… então aqui temos que ser mais cuidadosos com a implementação porque qualquer constante a mais pode nos dar um TL nesse problema. Como dizia o Fleischman, se é <=10^6, pode mandar sem medo, 10^7 é uma boa secar bem o código, 10^8 só passa na regional e 10^10, só na brasileira se você tiver sorte (desculpe, eu não resisto, depois de dois anos me ferrando com isso…).
Para cada conjunto, você precisa conferir primeiro se eles ganham – se não, esquece, não tem nem porque testar (isso é o primeiro for). Se eles ganharem, você tem que testar party por party se ela é minoria e tirando ela, o conjunto perde (isso é o segundo for). Note que aqui eu estou usando (1«i)&n para ver se o bit i está ligado na máscara n, o que é algo muito importante de se saber para entender o meu código.
Minha solução: http://pastebin.com/Em6QL7rQ

Parte dos Veteranos

CollectingPostmarks (TopCoder SRM 415, Div. 1, Level 2)

Esse problema tem uma técnica muito importante, então não deixem de fazê-lo! Como todos os problemas do TopCoder têm um editorial excessivamente bem escrito com soluções exemplo anexadas, aqui vai o link pro SRM dessa questão: http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm415 De qualquer forma, vou deixar minha solução aqui se a solução de referência dos tops estiver muito nebulosa.
Minha solução: http://pastebin.com/pQNvp49Y

Teaching (TopCoder SRM 427, Div. 2, Level 3)

O Teaching tem o TL muito apertado, então a idéia dele é você escovar bem suas bitmasks. Como eu mencionei antes, SRMs são muito bem documentados, então eis o editorial tremendamente bem escrito: http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm427
De qualquer forma, se alguém quiser ainda olhar minha implementação, vou deixá-la aqui.
Minha solução: http://pastebin.com/0Y1VbBYQ

Sudoku (LA 3304)

Ainda não fiz…

Light Up (LA 3476)

Ainda não fiz…

The Fortified Forest (LA 5211)

Ainda não fiz…

Complemento para esse treino:

Contest do Fabinho de Backtrackings na Escola de Verão de Campinas

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