XIII Contest Algar Telecom – Editorial

Nesse sábado, dia 29/03, aconteceu o XIII Contest Algar Telecom, tanto presencialmente em Uberlândia, quanto online no portal do URI.

Eu colaborei escrevendo quatro exercícios, e vou comentar a solução deles aqui neste post. Caso eu resolva os outros, eu também posso comentar eles aqui, mas sem pressa.

Clique no link abaixo para ver o resto do post.

Detetive Watson – [link]
Há duas formas bem simples de se resolver este exercício.

Se você conhece algum método de ordenação, basta ordenar os valores, de um modo que você não perca a posição original deles. Ao final, basta imprimir a posição original do segundo maior valor.

Outro modo seria implementar um método que busca pelo maior valor dentro do vetor. Execute o método uma vez, e altere o maior valor para -1. Na segunda vez que você executar o método, este será o resultado.

Arremesso de Bolas – [link]
Para resolver este exercício, é necessário testar todas as possibilidades de velocidade com a qual você pode arremessar a bola inicialmente.

Para cada velocidade escolhida, simule os pontos em que a bola quica com alguns laços de repetição, e se em algum momento a bola quicar na posição N, o resultado é “possivel”.
Se ela nunca quicar na posição N, não importando qual das velocidades permitidas com a qual você arremesse, então a resposta é “impossivel”.

Fila do Banco – [link]
Este exercício pode ser resolvido de várias maneiras. A mais direta é utilizando o conceito de Classes de Equivalência em Combinatórias.

Vamos esquecer por um segundo a ordem em que as outras pessoas na fila estão ordenadas. Vamos representar a fila como uma sequência de caracteres, sendo A o André, B o Bruno, C o Carlos, e X qualquer outra pessoa.

Dentre as seguintes combinações, quantas são válidas?

ABCXX
ACBXX
BACXX
BCAXX
CABXX
CBAXX

Apenas a primeira, pois André deve estar atrás de Bruno, e Bruno deve estar atrás de Carlos.

Então, independente da posição das outras pessoas, para cada 6 combinações, apenas 1 atende os requisitos do exercício.
Sabendo disso, o resultado pode ser obtido com a fórmula:
N! / 6

Basta agora tomar cuidado com o resto de divisão. Note que N! é divisível por 6, pois 6 faz parte da multiplicação, mas (N! Mod 10^9+7) pode não ser divisível por 6.

Como N >= 3, uma alternativa é dividir por 6 antes de calcular os outros fatoriais com a fórmula: fat[n] = n*fat[n-1].
Resultando em fat[3] = 1, fat[4] = 4, fat[5] = 20, e assim por diante.

Caso você pré-calcule os fatoriais Mod 10^9+7, em vez de dividir por 6 é possível multiplicar pelo inverso modular de 6 (a saber, 833333341), que o efeito é o mesmo. Pesquisem a respeito de inverso modular para mais detalhes.

Quadro Premiado – [link]
Este exercício pode ser resolvido utilizando-se o conceito de Programação Dinâmica. Basta descobrir quais padrões são compatíveis com quais outros padrões, e os relacionamentos entre os sub-problemas podem ser definidos.

O primeiro passo, portanto, é descobrir que padrões são compatíveis entre si. Um padrão m é compatível com um padrão k se, e somente se, para cada posição i do tamanho dos padrões, m[i] != k[i] || m[i] == “.” || k[i] == “.”.

Após isso podemos aplicar o conceito de programação dinâmica para tirar vantagem de sub-problemas que se repetem.

Seja dp[n][m] a soma máxima que é possível ser obtida utilizando o padrão m na linha n:
dp[n][m] = max(dp[n+1][k]) + soma(n, m),
para todo padrão k que é compatível com m,
e onde soma(n, m) resulta no valor obtido ao aplicar o padrão m na linha n.

Detalhe para o fato que o exercício pede “a soma máxima que é possível ser alcançada”. Isso não impede que a soma máxima seja negativa.

 

Qualquer dúvida, crítica ou sugestão, deixe um comentário abaixo.

Espero que tenham gostado dos exercícios, até mais.