Treino de 19 de junho de 2015

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Este é o quarto treino no novo formato. Esperamos que gostem. Abaixo, seguem os links para os problemas desse treino e uma descrição de uma solução possível para cada um deles. Recomenda-se não olhar os problemas antes do dia do treino (embora ninguém vá te impedir). Até lá, você pode ir treinando com outros problemas do Codeforces e de regionais passadas.

Conteúdo

Problemas

Nível Problema
1 O jogo Matemático de Paula
2 Dama
3 Megadamas
4 Mafia
5 Sum of different primes

Soluções

O jogo Matemático de Paula

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este problema é bastante direto. Basta ler os dois números e a operação e imprimir o resultado. Você pode ler a entrada como uma string, ou ler normalmente como você faria se tivesse espaços entre os números e o caractere, pois (em C) 'scanf' e (em C++) 'cin' param de ler o inteiro quando encontram um caractere que não seja um dígito.

Dama

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Podemos perceber que a resposta só pode ser 0, 1 ou 2, porque a dama consegue atingir qualquer casa do tabuleiro com dois movimentos. É fácil testar se a resposta é 0: este é o caso em que a casa de destino é igual à casa em que a dama começa. Testar se a resposta é 1 também não é difícil: ou as duas casas estão na mesma linha, ou na mesma coluna, ou é possível chegar de uma à outra com um movimento diagonal. Este último caso acontece quando o valor absoluto da diferença entre as linhas das duas casas é igual ao valor absoluto das diferenças das colunas (porque cada movimento na diagonal muda tanto a linha quanto a coluna em uma unidade). Se os dois testes falharem, saberemos então que a resposta é 2.

Megadamas

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

Para este problema, você deve perceber que não existem tantas possibilidades de movimentos assim. O tabuleiro tem tamanho fixo e depois do primeiro movimento, em que você pode ter 4 opções, você tem no máximo 3 opções (porque você nunca pode fazer um movimento de volta, já que a peça tomada será removida). Assim, este problema é resolvido com Backtracking. Você pode encontrar exemplos de backtracking em vários livros de algoritmos. Esta apresentação do pessoal da UPenn também pode ajudar.

Mafia

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.

A observação crucial para este problema é a que mostra que podemos aplicar busca binária na resposta. Se é possível satisfazer todos os jogadores com $x$ rodadas, então para qualquer $x' > x$ também será possível satisfazê-los, certo? Uma vez que todos estão satisfeitos, as rodadas adicionais podem ter qualquer um como mediador. Por outro lado, não é difícil provar que, se $x$ rodadas não são suficientes para satisfazer a todos os jogadores, diminuir o número de jogos não vai ajudar (ou seja, para qualquer $x' < x$, também não é possível satisfazer a todos com $x'$ jogos).

Isto significa que podemos fazer busca binária no número $x$ de rodadas necessárias. Basta, então, resolver o seguinte sub-problema: dado um número $x$ de rodadas que serão jogadas e os números $a_i$ de rodadas que o $i$-ésimo jogador quer jogar, é possível satisfazer a todos os jogadores?

Este problema é bem mais fácil. Uma forma de resolvê-lo é calcular em quantas rodadas poderíamos ter um mediador que está satisfeito. Se o $i$-ésimo jogador deseja jogar $a_i$ rodadas, ele então pode tranquilamente ser o mediador de $x - a_i$ rodadas, certo? Digamos que vamos combinar de antemão quais rodadas terão quais mediadores. Se chegarmos para o jogador $i$ e dissermos que ele deverá mediar $x - a_i$ rodadas e jogar as $a_i$ restantes, pelo enunciado do problema, ele sairá pulando de alegria. Precisamos então saber se temos mediadores suficientes para todas as rodadas. Ou seja, precisamos saber se

$$\sum_{i=1}^n x - a_i \geq x \enspace .$$

O único problema desta equação é que $x - a_i$ pode ser negativo e ainda assim a desigualdade ser satisfeita. Neste caso, o $i$-ésimo jogador não está sendo satisfeito. Logo, temos que verificar, além da desigualdade acima, que para todo $i$, $x \geq a_i$. Este teste pode ser feito em tempo linear. Assim, a complexidade da solução por busca binária seria $O(n \log M)$, onde $M$ é a maior resposta possível. Porém, podemos ver que $M \leq \sum_{i=1}^n a_i \leq 10^14$ pelos limites do problema, o que faz com que $log M \leq 47$.

Você pode ainda ir além e simplificar a desigualdade acima para obter:

$$\sum_{i=1}^n x - \sum_{i=1}^n a_i \geq x$$ $$nx - \sum_{i=1}^n a_i \geq x$$ $$- \sum_{i=1}^n a_i \geq x - nx$$ $$nx - x \geq \sum_{i=1}^n a_i$$ $$x(n - 1) \geq \sum_{i=1}^n a_i$$ $$x \geq \frac{\sum_{i=1}^n a_i}{n - 1} \enspace .$$

Logo, $x = \lceil \frac{\sum_{i=1}^n a_i}{n - 1} \rceil$ é a solução ótima se $x$ for maior ou igual que o maior dos $a_i$. Caso contrário, $x = \max \{a_i\}$ (já que este $x$ satisfaz as duas restrições: a desigualdade acima e ser maior ou igual a todos os $a_i$).

Sum of different primes

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Como já fizemos em vários problemas, vamos tentar retirar algumas restrições do problema para deixá-lo mais simples, e depois tentarmos tratá-las.

Primeiro, você deve ter notado que a questão de a ordem não importar complica um pouco as coisas. Vamos tornar o problema mais simples tirando esta restrição.

Para começo de conversa, como o problema envolve números primos, será útil saber todos os primos que podem ser utilizados. Neste caso, precisamos listar todos os primos até $1120$. São poucos, e você pode fazer isto no início do seu programa de diversas formas. Uma forma bastante eficiente é usar o Crivo de Eratóstenes. Para este problema, isto não é necessário, mas será útil aprender agora se você estiver disposto. O algoritmo é simples, pequeno e eficiente. Vamos dizer que temos um vetor $p$ onde $p_i$ é o $i$-ésimo número primo. Assim, $p_0 = 2, p_1 = 3, p_2 = 5, \cdots$.

Seja $f(n, k)$ o número de formas de somar $n$ usando $k$ primos, contando todas as somas em todas as ordens. Só é possível somar $0$ usando $0$ primos, e é possível fazê-lo de uma única forma. Logo, $f(0, 0) = 1$. Agora, se queremos somar $n$, vamos escolher o primeiro primo usado nessa soma. Seja esse primo $p_i$. Resta agora somar $n - p_i$ usando $k - 1$ primos: temos o mesmo problema, pois o número de formas de somar $n$ com a soma começando com $n = p_i + \cdots$ é exatamente o número de formas de somar $n - p_i$ com um primo a menos. Agora, temos que somar esses resultados para todos os $p_i$ para obter $f(n, k)$.

Assim, temos que:

$$f(0, 0) = 1$$ $$f(n, 0) = 0$$ $$f(n, k) = \sum_{i=0, p_i \leq n}^{|p|} f(n - p_i, k-1)$$

Ótimo. Podemos calcular esta função utilizando programação dinâmica, memorizando os resultados já calculados. A complexidade desta solução será $O(nk|p|^2)$. Estamos perto, mas isso ainda não resolve o problema original. Pode parecer que precisamos apenas dividir por $k!$ para obter a resposta original. Porém, isto não é verdade, porque permitimos que os primos se repitam e, por exemplo, para somar $8$, contamos a forma $2 + 2 + 2 + 2$ apenas uma vez e não $4!$ vezes.

Ok, vamos voltar então com a restrição de que a ordem não deve importar. Algo comum em programação dinâmica é adicionarmos uma restrição adicionando um parâmetro na nossa função recursiva $f$. Neste caso, faremos exatamente isto. Vamos adicionar um parâmetro $m$ e a seguinte restrição: o primo escolhido deve ser no máximo $p_m$. Assim, só estamos contando as formas de somar os números em ordem decrescente: se usamos o $7$, por exemplo, vamos permitir apenas que a solução dos subproblemas use os primos até o $5$.

Com isto, temos nossa nova função $f$ com três parâmetros:

$$f(0, 0, m) = 1$$ $$f(n, 0, m) = 0$$ $$f(n, k, m) = \sum_{i=0, p_i \leq n}^m f(n - p_i, k-1, i - 1)$$

Podemos computar esta função com programação dinâmica, mas a complexidade será $O(nk|p|^2)$. É possível fazer melhor, usando a seguinte observação: se queremos somar $n$, seja $p_m$ o maior primo menor ou igual a $n$. Só temos duas opções: ou vamos usar $p_m$ na soma, ou não. Só podemos usar o primo $p_m$ se $n \geq p_m$. Assim, conseguimos simplificar nossas transições e tirar o somatório, ficando com:

$$f(0, 0, m) = 1$$ $$f(n, 0, m) = 0$$ $$f(n, k, m) = f(n, k, m-1)\ \textbf{se}\ n < p_m$$ $$f(n, k, m) = f(n, k, m-1) + f(n - p_m, k-1, m-1) \textbf{se}\ n \geq p_m$$

Agora sim, podemos computar esta solução em $O(nk|p|)$.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas