Analysis300612

//Essa página necessita de um extreme makeover, mas por enquanto, estou meio sem paciência de fazê-lo…

Pie:

Essa questão é bonitinha – dado que só o volume importa, você precisa achar o volume máximo que dá pra distribuir pras pessoas; observe que isso é uma função monótona: do zero até um certo valor x, dá pra distribuir pedaços iguais pra todo mundo e depois pára de dar. Funções monótonas são flag de que a questão vai sair por busca binária – de fato.
Leia o enunciado com cuidado pra saber a regra de distribuição das tortas. Ah, e uma nota de pé de página importante: muitas vezes busca binária com while (beg<end) em doubles não converge, então use um número de iterações fixas ou um cmp com um eps relativamente folgado.

Minha solução: http://pastebin.com/20JRwQLk

GPS I Love You:

A base dessa questão é checar a desigualdade triangular: se d[v]==d[u]+g[u][v], significa que a aresta g[u][v] faz parte do menor caminho, então você não precisa força-la. Mas, sed[v]<d[u]+g[u][v] e até u, todas estavam no menor caminho, você tem que forçar essa aresta. Daí, você passa a querer que as arestas estejam no menor caminho a partir de v (porque, como você forçou aquela aresta, a partir de u elas certamente não estarão), o que faz você querer um Floyd Warshall como seu algoritmo de menor caminho.
Minha solução: http://pastebin.com/XX3f5iDH

Lawn Mower:

Como essa questão lida com doubles, não dá pra usar um vetor de bools e ir marcando as posições que você já passou – é necessária uma idéia ligeiramente mais esperta, um tipo de algoritmo que é chamado line sweeper. Basicamente, você quer que todos os intervalos: 1. não tenham buracos dentro da região do campo; 2. cheguem até o final do campo. Se você ordenar os xs (a idéia é idêntica pros ys), você só não vai ter buraco se o final do último intervalo que você olhou passar do começo do intervalo seguinte. Pro caso de chegar no final do campo, você quer que o final do último intervalo chegue ou passe do final do campo.
Minha solução: http://pastebin.com/9w8qwYxk

Grapevine:

Essa questão é um clássico e tem uma solução linda. Como a matriz é não-decrescente para baixo e direita, temos que as linhas, colunas e diagonais dela necessariamente formam uma sequência monótona. Good, então dá pra encaixar uma busca binária, se necessário. A primeira idéia que vem à cabeça é possivelmente fixar um (i,j) de começo do quadrado e fazer busca binária no lado. Bom, já que isso é uma questão de brasileira, ouso afirmar que esse approach ia passar mole na prova, mas quando o Maurício comentou dele, eu codei e tomei um TL – para os curiosos, segue a implementação
Minha solução TLE: http://pastebin.com/uXW23Sx3

A outra solução, que é incrivelmente elegante e foi proposta pelo meu colega de equipe em 2011 (o Lazera, in case you're wondering) é olhar cada uma das diagonais (são 2*N) procurando o início e o final do maior quadrado possível. Basicamente, queremos o menor cara >=l e o maior <=u. Furthermore, precisamos saber se esses dois caras formam um quadrado válido, que é feito checando se o menor cara >=l é <=u também.
Aviso aos navegantes: não rola de chegar ambas as condições nas duas buscas binárias – fato que me foi advertido pelo Maurício quando, depois do meu quinto WA, eu escrevi pra lista perguntando o que estava errado. O motivo disso é que ser >=l e <=u não é monótono, é unimodal – veja que você começa não sendo, aí tem uma hora que você chega em um cara válido e depois tem risco de você sair.
Minha solução: http://pastebin.com/GrmLdkfp

Leonardo's Notebook:

Como foi o Renan que me deu o algoritmo, acho mais digno ele escrever sobre. De qualquer forma, segue minha implementação
Solução Luiza: http://pastebin.com/Xc8EbhZ9

High Score:

Esse problema é tricky e o caso que faz você sacar isso claro que não está no sample – o caso é esse aqui: NBAAAAAAAAAAA…AAAAJ Esse caso mostra que algumas vezes você quer ir e voltar, que isso fica mais barato que ir só numa direção. Observado isso, é bastante clara a observação que você quer virar uma vez só – todas as vezes que você quiser ir, voltar e ir de novo, você pode trocar por um turning point só e fica mais barato.
A partir daí, vamos supor que a gente sabe onde a gente quer virar, a gente tem que saber quanto a gente precisa andar pro outro lado. Como a gente tem que cobrir todos os caras, a gente tem que achar, a partir do turning point, o primeiro cara que precisamos mudar, ou seja, que não é 'A'. Quando formos pro outro lado, temos que alcançar até ele.
É bastante intuitivo que queremos percorrer a menor distância antes para que o custo de voltar e ir para o outro lado ser mínimo. Então queremos percorrer duas vezes o mínimo do caminho até o turning point e o caminho que até o cara que precisamos mudar, caminhando na direção inversa a partir do final mais o máximo dos dois (o que equivale a ir e volta no menor caminho e percorrer o maior).
Como é NWERC, tem a solução oficial aqui: http://2010.nwerc.eu/results/nwerc2010-solutions.pdf
Minha solução: http://pastebin.com/uR2uBpBt

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