Treino de 26 de junho de 2015

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

Este é o quinto 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 LED
2 Futebol
3 Cartões
4 Subsequence
5 Divisibility by Eight

Soluções

LED

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este problema é bem direto: para cada dígito 1 na entrada, some 2 na resposta; para cada dígito 2, some 5, e assim por diante (é só olhar o desenho). O único cuidado pedido com a implementação é de não ler o número da entrada como um inteiro, pois ele pode ter até 101 dígitos (o limite diz $V \leq 10^{100}$, que tem 101 dígitos) e não cabe em um 'int' ou em um 'long long'. Assim, use uma string para ler o valor da entrada.

Uma forma pouco trabalhosa de implementar este problema é criar e usar um vetor onde $v[i]$ é o número de LEDs necessários para montar o dígito $i$.

Futebol

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

Vamos considerar, então, quantos pontos ele pode ganhar a mais nas partidas em que ele não venceu (já que nestas não há o que fazer).

Digamos que, na $i$-ésima partida que seu time não ganhou, você precisa comprar $x_i$ gols para empatar e $x_i+1$ gols para ganhar (também é claro que nunca faz sentido ganhar de mais de um gol de diferença em uma partida em que você vai comprar gols. Humilhar o adversário não te dá pontos extra...). Se há partidas com $x_i = 0$ (ou seja, que você empatou), é claro que você deve comprar a vitória nelas (é a vitória mais barata que você irá conseguir). Depois de comprar quantas forem possíveis, só sobrarão partidas com $x_i \geq 1$. Não é difícil ver que você nunca comprará mais de um empate. O motivo é simples: se você comprou dois empates, você poderia usar um dos gols que usou no segundo empate para comprar a vitória no primeiro empate, e isso te dá um ponto a mais no total (você substitui dois empates por uma vitória e uma derrota, que é melhor). Além disso, é óbvio que se você comprar $v$ vitórias, sempre é melhor comprar as $v$ mais baratas.

O algoritmo, então, é guloso: compre as vitórias mais baratas até não mais conseguir, e então veja se consegue comprar o próximo empate. Ou seja, ordene as partidas que você não ganhou por $x_i$ em ordem crescente, e percorra-as em ordem, comprando a vitória se conseguir e, se não, tentando comprar o empate.

Cartões

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

Este é um problema clássico de programação dinâmica. Cada jogador deseja maximizar o seu número de pontos (como a soma dos pontos dos dois jogadores ao final é fixa, minimizar o número de pontos que o adversário fará equivale a maximizar seu próprio número de pontos). A recorrência é simples: vamos considerar o jogo com $n$ cartas. O jogador da vez tem duas opções: ou tirar a primeira, ou a última carta. Nos dois casos, sobra um problema com $n-1$ cartas. Ele então escolherá a melhor das duas únicas opções que tem. Tirada uma carta, temos o mesmo problema com $n-1$ cartas. Mais ainda: os sub-problemas são sempre subsequências contíguas do arranjo original de cartas. Podemos, então, representar cada subproblema pelos índices da primeira e da última cartas, e resolver o problema usando programanção dinâmica.

Seja $f(i, j)$ o maior número de pontos que o jogador da vez consegue fazer no jogo que envolve as cartas de $i$ a $j$ (inclusive, indexadas de 1 para condizer com o enunciado). Queremos encontrar $f(1, N)$ no final.

O jogador tem duas opções: ou pegar a $i$-ésima carta para si e deixar o outro jogador com as cartas $i+1$ até $N$, ou pegar a $j$-ésima carta e deixar o outro jogador com as cartas $i$ até $j-1$. Em todo caso, podemos ver que o número de pontos que ele fará é a soma de todas as cartas entre $i$ e $j$ menos o número de pontos que o outro jogador fará depois que o jogador da vez fizer sua jogada. Ou seja, se $S_ij$ é a soma das cartas entre $i$ e $j$:

$$f(i, j) = \max \{S_{ij} - f(i+1, j), S_{ij} - f(i, j-1) \}$$

Não é difícil ver que, como o termo $S_{ij}$ é fixo, queremos apenas saber quem é o menor entre $f(i+1, j)$ e $f(i, j-1)$. Ou seja:

$$f(i, j) = S_{ij} - \min \{f(i+1, j), f(i, j-1) \}$$

Podemos definir o caso base como $f(i, i) = C_i$, ou seja, se só há uma carta no jogo, a $i$-ésima, o jogador obrigatoriamente pegará ela e fará $C_i$ pontos.

A complexidade desta solução, então, é $O(N^2)$ de tempo. Para o espaço, você pode gastar também $O(N^2)$, ou reformular a recorrência para que você só precise da última linha calculada da matriz para calcular a próxima linha. Se você calcular $f(l, i)$ como o máximo de pontos que o jogador da vez consegue no jogo que usa as cartas $i, i+1, \cdots, i+l-1$ (no total de $l$ cartas), para calcular $f(l, i)$ você apenas precisa de $f(l-1, i)$ e de $f(l-1, i+1)$: dois valores da linha anterior da matriz. Com isto, você só precisa manter a última linha calculada e descartas as restantes, usando assim apenas $O(N)$ de espaço. Esta otimização é necessária para passar este problema no URI Online Judge (para o UVa, a solução $O(Nˆ2)$ de espaço é suficiente).

Note que esta complexidade depende de você saber computar $S_{ij}$ em $O(1)$. Isto pode ser feito se você pré-computar o vetor de soma de prefixos do vetor da entrada: isto é, $P_{i} = \sum_{k=1}^i C_k$. Com isto, $S_{ij} = P_j - P_{i-1}$.

Subsequence

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

Assim como no problema Mafia do último treino, a observação crucial aqui é a monotonicidade. Se existe uma subsequência contígua com $k$ elementos cuja soma seja pelo menos $S$, obviamente existem subsequências contíguas com qualquer tamanho $k' > k$ cuja soma também seja pelo menos $S$, já que os números da entrada são todos positivos, e adicionar elementos nunca diminui a soma. Da mesma forma, se não existe uma subsequência com $k$ elementos com a propriedade desejada, é claro que também não pode existir uma subsequência com $k' < k$ elementos com soma pelo menos $S$. Caso existisse, poderíamos adicionar $k - k'$ elementos a esta sequência e obter uma sequência com $k$ elementos com a soma desejada: contradição. Ou seja, podemos fazer busca binária na resposta, que é o tamanho da menor subsequência contígua cuja soma dos elementos seja pelo menos $S$.

Nosso problema agora é: dado um tamanho $k$, existe alguma subsequência contígua de $k$ elementos cuja soma seja pelo menos $S$? A primeira pergunta que devemos nos fazer sempre que temos uma pergunta do tipo "existe algum objeto que tenha uma determinada propriedade" é: quantos objetos existem? Se são poucos e se conseguimos testar a propriedade eficientemente, talvez não precisemos pensar muito: basta testar todos e verificar se encontramos algum com a propriedade desejada.

Neste caso, você pode ver que existe apenas um número linear de subsequências contíguas de tamanho $k$. Mais precisamente, existe uma subsequência que começa no elemento $i$ se o elemento $i + k - 1$ (o último da subsequência de tamanho $k$) está dentro do vetor, ou seja: $i + k - 1 \leq N$, o que equivale a $i \leq N + 1 - k$. Ou seja, se o vetor original tem $N$ elementos, existem $N + 1 - k$ subsequências contíguas de tamanho $k$. E como podemos obter a soma de uma subsequência eficientemente? Se você fez o último problema, provavelmente sabe: basta usar soma de prefixos (isto é explicado na solução do problema "Cartões").

Resumindo: fazemos busca binária no tamanho $k$ da menor subsequência contígua que tem soma pelo menos $S$. Dado um $k'$ para teste, olhamos as subsequências de tamanho $k'$ que começam nos elementos $1$, $2$, $\cdots$, $N - k'$, e verificamos se alguma delas tem soma pelo menos $S$. Se sim, então a resposta é no máximo $k'$. Caso contrário, sabemos que a resposta deve ser maior que $k'$, e atualizamos os limites da busca binária de acordo com a conclusão.

Não se esqueça de verificar se há alguma solução. Se a soma de todos os elementos do vetor não for pelo menos $S$, então a resposta impressa deve ser $0$, conforme o enunciado.

A complexidade da nossa solução é, então, $O(n \lg n)$, pois cada teste pode ser feito em tempo linear, e faremos $O(\lg n)$ testes.

Divisibility by Eight

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

Este problema tem pelo menos duas soluções. Uma é por programação dinâmica e a outra é por Teoria dos Números (ou por memória boa se você se lembra da regra de divisibilidade por 8). A segunda é mais simples; vamos começar por ela.

Um número é divisível por 8 se e somente se os seus três últimos dígitos na representação decimal formarem um número divisível por 8. A prova disto é simples usando aritmética modular: como 1000 é divisível por 8, $10^x$ é divisível por 8 para $x \geq 3$. Então, o resto da divisão de um número por 8 é o resto da divisão dos três últimos dígitos do número por 8.

Com isto, basta testarmos todos os possíveis 3 últimos dígitos do número que desejamos obter, usando dígitos do número da entrada. Podemos fazer esse teste em $O(n^3)$ mesmo, como $n \leq 100$. Se encontrarmos três dígitos $d_i$, $d_j$ e $d_k$ com $i < j < k$ tal que $100d_i + 10d_j + d_k$ for divisível por 8, imprimimos $d_id_jd_k$.

Vamos agora para a solução por programação dinâmica. Podemos tentar decompor o problema da seguinte forma: vamos fazer a pergunta: existe alguma forma de remover dígitos dos $k$ primeiro dígitos do número de forma que o número resultante seja divisível por 8? Se conseguirmos responder a esta pergunta, ótimo, podemos reconstruir a solução depois se a resposta for "sim".

Depois de um tempo pensando, você provavelmente não chegará a lugar algum. Não ajuda muito tirar o último dígito do problema para depois tentar colocá-lo de novo na solução se tudo o que temos é uma resposta de "sim" ou "não" sobre o mesmo problema nos $k-1$ primeiros dígitos. Vamos tentar outra decomposição. Tentemos generalizar o problema (muitas vezes, o problema mais geral é, de fato, mais fácil). Nossa pergunta é se existe alguma forma de remover dígitos de forma que o resto da divisão do número resultante por 8 seja 0. Vamos generalizar esta parte do resto, e perguntar se existe alguma forma de remover dígitos de forma que o número resultante deixe resto $r$ quando dividido por 8.

Agora sim, podemos chegar em uma recorrência. Se $f(k, r)$ é um predicado (ou seja, um "booleano matemático") que diz se é possível remover dígitos dos $k$ primeiros (mais significativos) dígitos de $n$ de forma que o resultado deixe resto $r$ quando dividido por 8. Seja $d_k$ o $k$-ésimo dígito de $n$. Temos duas opções: ou apagar $d_k$ ou deixá-lo lá. Temos, então, que:

$$f(0, 0) = \textbf{true}$$ $$f(0, r) = \textbf{false}, r \geq 1$$ $$f(k, r) = f(k-1, r)\ \textbf{or}\ \left(\sum_{r'=0}^7 \left[f(k-1, r')\ \textbf{and}\ (10\times r' + d_k) \mod 8 = r\right]\right) > 0$$

A notação $[x]$ é a notação de Iverson: 1 se $x$ é verdadeiro e $0$ caso contrário.

A última expressão pode ser lida assim: $f(k, r)$ é verdadeiro se é possível deixar resto $r$ apenas com os $k-1$ primeiros dígitos de $n$ (ou seja, apagando-se $d_k$) ou se é possível deixar resto $r'$ tal que $10\times r' + d_k$ deixe resto $r$ quando divisível por $8$. Isto porque se $x$ deixa resto $r$ ao ser dividido por 8, colocar um dígito $d_k$ à direita de $x$ transforma este em $10x + d_k$, que deixará resto $(10r + d_k) \mod 8$ ao ser dividido por 8. Queremos, então, saber se existe alguma forma de apagar os dígitos anteriores de forma que colocar o dígito atual dê exatamente o resto que queremos.

Ok, isto é metade do problema: falta, depois, obter um dígito possível de ser formado. Só sabemos até agora se ele existe ou não. Mas isto não é difícil: basta salvar uma matriz adicional $prev$ onde $prev(k, r)$ seja uma das transições que fez com que $f(k, r)$ fosse verdadeiro. Ou seja, basta salvarmos de onde viemos, e depois reconstruir a solução de trás para frente. Você pode ver um exemplo mais detalhado desta técnica, aplicável a todo problema de programação dinâmica, neste PDF.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas