Aconteceu no dia 12 de Setembro em sedes espalhadas por todo o país a etapa regional da Maratona de Programação. O resultado completo pode ser conferido aqui. Em 2015 a sede Goiânia foi uma das maiores do país e recebeu 29 times de 10 instituições de todo o estado. As 10 melhores equipes podem ser vistas na imagem abaixo.
As equipes “11 balões e 3 segredos” do INF-UFG e “Turkeys” da UnB se classificaram para a fase nacional da maratona que acontecerá nos dias 13 e 14 de Novembro em São Paulo. Boa sorte!
A prova esse ano foi composta de 12 questões e pra começar a contribuir com o portal, aproveitando o clima de competição que ainda não se dissipou, nada melhor que uma breve análise da prova desse ano. Confira.
| Problema | Dificuldade | Técnica relacionada |
|---|---|---|
| A - Mania de Par | fácil | grafos, dijkstra |
| B - Bolsa de Valores | fácil/médio | programação dinâmica |
| C - Tri-du | balão++ | ad hoc |
| D - Quebra-cabeça | fácil | ad hoc |
| E - Espiral | médio | ad hoc, matemática |
| F - Fatorial | fácil | greedy, coin change |
| G - Guardiões Curiosos | difícil | grafos, programação dinâmica |
| H - Praça do Retângulo | médio | ad hoc |
| I - Ominobox | difícil++ | … |
| J - Jogo de Estratégia | balão++ | ad hoc |
| K - Palíndromo | fácil/médio | programação dinâmica |
| L - Loteria | difícil | algebra linear, eliminação gaussiana |
A - Mania de Par
Resolva este problema: Uva, URI
Se não fosse a restrição de pagar um número par de pedágios, esse problema seria facilmente resolvido usando o algoritmo de Dijkstra. Bem, acontece que mesmo com essa restrição adicional o problema continua sendo facilmente resolvido com o algoritmo de dijstra. :) Para isso basta transformar cada vértice \(u\) do grafo em dois, \(u_0\) e \(u_1\), o vértice \(u_0\) representa chegar ao vértice \(u\) pagando um número par de pedágios e o vértice \(u_1\) representa chegar ao vértice \(u\) pagando uma quantidade de pedágios impar. Cada aresta \(C1 - C2\) do grafo original dá origem a duas arestas \(C1_0 - C2_1\) e \(C1_1 - C2_0\) no nosso novo grafo. E agora para encontrar a resposta basta calcular o menor caminho entre os vértices \(1_0\) e \(C_0\).
Um exemplo de implementação segue abaixo:
B - Bolsa de Valores
Resolva este problema: Uva, URI
Ao terminar de ler o segundo problema da prova, o competidor que já conhece a técnica de programação dinâmica provavelmente fica com uma impressão de que a solução pro problema envolve o uso dessa técnica. E de fato ele está correto. Deixando a historinha de lado, temos um período de \(N \leq 2*10^5\) dias para os quais sabemos os valores de venda das ações de uma empresa e queremos saber qual seria o valor máximo que poderiamos lucrar se tivessemos investido nesse período dado que para cada compra de ações deve-se pagar uma taxa de \(C\) reais e que nunca podemos ter mais de uma ação da empresa.
Sendo assim, a decisão que precisamos tomar a cada dia é bem simples, podemos vender a ação que possuímos (caso tenhamos alguma ação) ou podemos comprar uma ação caso não tenhamos nenhuma. As informações que precisamos saber para tomar a decisão num certo dia são apenas o dia em que estamos e se possuímos ou não uma ação da empresa, e isso categoriza nosso estado. As decisões que podemos tomar são: não fazer nada, vender a ação que possuímos ou comprar uma nova ação e essas serão as nossas transições. Tanto implementações recursivas com memorização (top-down) quanto iterativas (bottom-up) dessa abordagem são bem simples e eficiente.
Um exemplo de implementação top-down segue abaixo:
C - Tri-du
Resolva este problema: Uva, URI
O problema mais fácil da prova consistia de uma lógica bem simples. Uma trinca ganha de qualquer par, então se as duas cartas forem iguais queremos que a terceira também seja. No caso delas serem diferentes queremos formar o maior par possível, então precisamos que a terceira carta seja igual a maior das duas que já temos. Acontece que a regra do maior par é suficiente para garantir que formamos uma trinca (caso as duas cartas sejam iguais) então basta imprimir o maior valor entre A e B.
D - Quebra-cabeça
Resolva este problema: Uva, URI
Esse era um problema simples mas que enganou muitas equipes. A entrada consite de um grid \(NxM\) no qual em cada célula temos o nome de uma variável. Além disso temos o valor da soma das variáveis em cada linha e em cada coluna do grid. O que o problema pede é que encontremos os valores de cada variável. A impressão que dá é a de que é necessário resolver um sistema de equações para determinar o valor das variáveis e provavelmente por isso muitas equipes deixaram esse problema de lado. Acontece que a solução pro problema na verdade está descrita no enunciado do mesmo, em um trecho que diz:
Mas como esse tipo de quebra-cabeças é para crianças, ele tem uma propriedade
que o torna mais fácil de encontrar a solução:sempre é possível encontrar uma
linha ou coluna em que há apenas uma variável cujo valor ainda é desconhecido.
Assim, uma possível maneira de resolver o problema é, a cada passo da solução,
encontrar o valor de uma variável.
Assim a solução do problema consiste basicamente em implementar essa idéia. A cada passo encontramos uma linha ou coluna em que aparece apenas uma variável com valor desconhecido e descobrimos o valor dessa variável. Como a cada passo vamos eliminar uma linha ou uma coluna das buscas, o número máximo de variáveis que pode haver no quebra-cabeça é \(N+M\). Então mesmo que e a cada passo todo o grid seja varrido na procura da linha/coluna que será usada para descobrir o valor da variável atual a complexidade da solução continua sendo da ordem de \(O(N^3)\) que é eficiente o suficiente para os limites do problema.
Segue abaixo um exemplo de implementação:
E - Espiral
Resolva este problema: Uva, URI
Um problema bem interessante que pode ser resolvido com um algumas observações simples. Inicialmente, como os limites são bem grandes, já podemos eliminar a idéia de simular a o processo de colocar os feijões no grid. Mas ainda na linha da simulação podemos tentar fazer com que ela seja mais eficiente. Podemos pensar em cada camada mais externa do grid como uma “casca”, tal que quando retiramos essas “cascas” obtemos um grid com duas linhas e duas colunas a menos. Já que o processo de colocar os feijões no grid vai preenchendo primeiramente essas cascas, se houvesse um modo de descobrir rapidamente quantas cascas serão completamente preenchidas já poderiamos eliminar boa parte da simulação começando em um ponto mais avançado do processo.
Bem, acontece que descobrir quantas celulas foram preenchidas não é uma tarefa muito complexa. Em um grid \(NxN\), o nro de celulas na primeira casca é \(4*(N-2) + 4\). Para chegar nesse valor ignoramos as celulas dos cantos, assim temos 4 segmentos idênticos com \(N-2\) células mais as 4 células dos cantos. Para a segunda casca, podemos considerar apenas o grid interno, que tem dimensões \((N-2)x(N-2)\), e usar a mesma lógica da primeira casca. Generalizando essa idéia conseguimos mostrar que o número de células na i-ésima casca é \(4*(N-2*i) + 4\).
Com essa equação em mãos podemos calcular o número de celulas presentes em \(X\) cascas como sendo:
\[\begin{gather*} \sum_{i=1}^{X} 4*(N-2*i) + 4 \\ = \sum_{i=1}^{X} 4*N-8*i+4 \\ = \sum_{i=1}^{X} 4*N + \sum_{i=1}^{X} 4 - 8 * \sum_{i=1}^{X} i \\ = X*4*N + X*4 - 8*(\frac{X*(X+1)}{2}) \\ = 4 * X *(N - X) \end{gather*}\]Bem, então se queremos saber o número \(X\) de cascas completas, como queremos que \(4 * X *(N - X) \leq B\) podemos resolver essa inequação. Ou, ser uma pouco menos matemáticos e usar busca binária para descobrir o valor. :)
Sabendo o número de \(X\) de cascas que serão completamente preenchidas podemos começar a colocar os feijões restantes a partir da posição \((X+1,X)\).
Como no pior caso nenhuma casca foi completamente preenchida podemos ter ainda um número na casa de \(2^30\) feijões para colocar, então essa parte também deve ser feita de uma maneira esperta. Mas essa etapa é bem mais simples, podemos preencher um segmento todo de uma vez já que estamos partindo do início do mesmo, sendo assim no pior caso vamos gastar apenas 4 operações para colocar os feijões restantes.
Segue abaixo uma implementação dessa idéia usando busca binária para descobrir o número de cascas completamente preenchidas:
F - Fatorial
Resolva este problema: Uva, URI
O segundo problema mais fácil da prova podia ser resolvido pelo menos de duas maneiras. Uma delas era usando uma estratégia gulosa e outra aplicando uma solução de programação dinâmica similar a usada no clássico problema do coin change.
As duas abordagens partiam de um mesmo insight inicial. O número de fatorias distintos que podemos usar é apenas 8, já que \(9! = 362880\) é maior que \(10^5\) (que era o maior valor de \(N\) possível para o problema).
A partir daí um competidor que já conhecia o problema do coin change rapidamente implementaria uma solução \(O(8*N)\). Ou com um pouco mais de observação (ou talvez) sorte a equipe poderia usar um algoritmo guloso, a cada passo subtraindo de \(N\) o maior fatorial menor que \(N\). A prova de que essa abordagem funciona usa o fato que \(N! > 1! + 2! + 3! + \dots + (N-1)!\).
Segue um exemplo de implementação usando a solução gulosa:
G - Guardiões Curiosos
Resolva este problema: Uva, URI
Esse problema pode ser resolvido com uma grande variedade de abordagens, acredito que a mais simples delas precisava de um conhecimento prévio envolvendo Prüfer sequence. Resumidamente, há uma bijeção entre as sequências de \(N-2\) elementos formadas pelos valores de \(1\) a \(N\) e as árvores rotuladas de \(N\) vértices, sendo que o grau de um vértice é igual ao número de vezes que o rótulo daquele vértice aparece na sequência + 1.
Sabendo disso, podemos reduzir o problema a contar o número de sequências com \(N-2\) elementos, formadas pelos valores de \(1\) a \(N\), tal que nenhum elemento aparece mais que \(K-1\) vezes.
Para calcular esse número podemos usar diferentes técnicas. Uma delas consiste numa programação dinâmica simples baseada na fórmula que conta o número de permutações distintas de uma sequência onde podem aparecer elementos repetidos:
\[\begin{gather*} \frac{N!}{n_1! * n_2! * \dots * n_x!} \end{gather*}\]Onde \(N\) é o número de elementos da sequência e \(n_x\) é a quantidade de vezes que cada valor aparece. A idéia então é ter no estado da pd o elemento atual e a quantidade de posições que ainda não foram preenchidas, e as transições vão variar o número de vezes que o elemento atual aparece de \(0\) a \(min(posições livres, K-1)\).$$
Interessantes abordagens alternativas para esse problema podem ser encontradas nos comentários desse post(em inglês) no Codeforces.
H - Praça do Retângulo
Resolva este problema: Uva, URI
I - Ominobox
Resolva este problema: Uva, URI
J - Jogo de Estratégia
Resolva este problema: Uva, URI
Um exemplo de implementação segue abaixo:
K - Palíndromo
Resolva este problema: Uva, URI
Um exemplo de implementação segue abaixo: