Treino 21.1

Avoiding a disaster

Complete search; checar todas as possibilidades de PA depois de converter para minutos (lembre-se que horários são mod 60*12).
Minha solução: http://pastebin.com/iZEKfAfk

Magic Trick

Ad-hoc; o algoritmo está dito no problema, só implementar.
Minha solução: http://pastebin.com/W3kwGaYi

He is Offside!

Ad-hoc; só implementar o que ele pede.
Minha solução: http://pastebin.com/Q0PYTTS9

Help-or-else

Programação dinâmica (nível hard);
dp[i][qtd de pessoas que faltam ajudar] = mínimo de tempo gasto;
Em cada iteração, você pode escolher se vai ajudar aquela pessoa ou não. Como que você vai atender as pessoas importa, você tem que ordenar as pessoas de forma ótima – em ordem crescente de d's. A prova disso é bastante intuitiva, já que pra atender a primeira pessoa você paga (p)*d(0), pra segunda, (p-1)*d(1); então, para minimizar essa soma (p*d(0)+(p-1)*d(1)+(p-2)*d(2)+…), basta que d(0)<=d(1)<=d(2)… (se não me engano tem uma prova de um problema parecido na parte de guloso do Tardos)
A recursão fica assim:
dp[i][qtd]=min(dp[i-1][qtd]+e[i], dp[i-1][qtd+1]+(qtd+1)*d[i]);

Para a implementação, dependendo da ordem que você processar os índices, dá pra fazer n^2 ou n^3, dependendo da ordem dos índices. Dá pra fazer uma versão n^3 recursiva também, mas acredito que ela seja menos interessante que a n^2. Para a n^3 iterativa passar, acredito que você tem que fazer o corte bobo de processar o número de pessoas que você quer ajudar de n até 0, parando assim que você achar uma resposta (eu fiz isso e meu código ficou em 2.5s)

Minha solução O(n^3): http://pastebin.com/e6vCaMTr
Minha solução O(n^2) recursiva: http://pastebin.com/yTH59Nqj
Minha solução O(n^2) iterativa: http://pastebin.com/d7Vs46Jx

X-mart

2-SAT bem straight-forward - se você nunca viu um problema de 2-SAT, vale dar uma lida na apostila de 2-SAT. Depois d'eu passar esse problema, Maurício me recomendou fazer o Ministers' Major Mess, que treina a recuperação do 2-SAT (solução para ele: http://pastebin.com/ebMMrp96)
Minha solução: http://pastebin.com/BfRpi1Tw

Traveling Shoemaker Problem

http://en.wikipedia.org/wiki/Eulerian_path

Not Too Convex Hull

Will Indiana Jones Get There?

Monte o grafo do quadrado das distâncias entre segmentos (do quadrado porque aí você não precisa lidar com problemas de precisão na comparação, por exemplo – sempre melhor manter inteiros quando podemos fazer isso). Você precisa saber qual o valor mínimo de aresta que deixa 0 e 1 conexos, então busca binária no tamanho da aresta com uma dfs para testar a conexidade é a solução mais rápida de codar. Como estamos querendo a menor maior aresta, vale também fazer um kruskal e só ir de 0 a 1 (veja problema Bring Your Own Horse, Treino 22)
Minha solução: http://pastebin.com/syTieDZ0

Turkish Roulette

IOI01 Mobiles

Nota: esse problema não foi incluído no contest porque ele não é suportado pelo VOC
Utilização straight-forward de qualquer estrutura range query, point update 2D (e.g. BIT 2D ou Segtree 2D)
Minha solução com BIT 2D: http://pastebin.com/mNCjvCdk

Para a solução com segtree, bom, ela me custou uma semana e uma discussão imensa com o Maurício, que está aqui
Solução do Maurício com segtree 2D: http://ideone.com/KBgsQ

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