Treino de 12 de junho de 2015

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

Este é o terceiro 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 Guarda Costeira
2 Vanya and Cubes
3 Ir e vir
4 Contagem de Dígitos
5 DNA Alignment

Soluções

Guarda Costeira

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este é um problema de matemática simples. Você deve verificar se o guarda, percorrendo a hipotenusa de um triângulo retângulo, chegará antes ou junto com o ladrão num dos vértices, sendo que este percorre um dos catetos. Isto se reduz à seguinte condição: $$\frac{\sqrt{12^2 + d^2}}{V_g} \leq \frac{12}{V_f}\enspace .$$

Algo sempre recomendado é evitar o uso de números de ponto flutuante para que não tenhamos problema com precisão. O problema é que muitos números "simples" (como $\frac{1}{3}$) não têm uma representação exata em ponto flutuante. Assim, estamos sempre sujeito a erros quando operamos com tais números. Esses erros se acumulam em operações e podem causar problemas. Além disso, operações com inteiros são mais eficientes. Se é possível resolver o problema usando apenas inteiros, normalmente isto é preferível.

Neste caso, é. Elevando os dois lados da inequação ao quadrado e multiplicando ambos por $V_f \cdot V_g$, concluímos que a desigualdade acima equivale a:

$$V_f^2 \cdot (12^2 + d^2) \leq 12^2 \cdot V_g^2 \enspace .$$

Dados os limites da entrada, esta condição pode ser facilmente testada usando apenas inteiros.

Vanya and Cubes

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

Dados os limites deste problema, ele não tem muito segredo. Basta testar, progressivamente, quantos cubos teria uma pirâmide de altura $1$, $2$, ..., até que você encontre uma pirâmide que não pode ser feita com $n$ cubos. É evidente que esta altura limite não será grande. Afinal, $n$ é um limite (ainda bem folgado) para a altura. Pelo enunciado, vemos que o nível $i$ usa $i$ cubos a mais que o nível anterior, e o tamanho de uma pirâmide de nível $i$ é o tamanho de uma pirâmide de nível $i-1$ somado ao número de cubos no nível $i$. Assim, basta termos um loop que mantém duas variáveis: o número de cubos $L_{i-1}$ do $(i-1)$-ésimo nível e o número de cubos $S_{i-1}$ de uma pirâmide de tamanho $i-1$. Podemos inicializar $L_0 = 0$ e $S_0 = 0$, e usar que:

$$L_i = L_{i-1} + i$$ $$S_i = S_{i-1} + L_i$$

até acharmos o maior $i$ tal que $S_i \leq n$. Este valor de $i$ é a resposta.

Ir e vir

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Este problema se reduz a: dado um grafo $G$ direcionado, verificar se ele é fortemente conexo, ou seja, se existe um caminho entre cada par de vértices.

Há mais de uma forma de se testar conectividade. Uma bem simples de ser explicada é a seguinte. Pegue um vértice qualquer $v$. Use uma busca em profundidade para verificar se existe um caminho de $v$ até todos os outros vértices do grafo. Se não existe, a resposta é obviamente não, pois você vai ter encontrado um vértice não alcançável a partir de $v$. Assumindo que você achou um caminho para todos os demais vértices, inverta as arestas do grafo, obtendo o grafo transporto $G^T$. Note que um caminho de $i$ a $j$ neste novo grafo $G^T$ equivale a um caminho de $j$ a $i$ no grafo original $G$, com as arestas na direção oposta e tomadas na ordem inversa. Neste grafo $G^T$, faça o mesmo teste: verifique se é possível ir de $v$ a todos os outros vértices com uma nova busca em profundidade. Se a resposta for não, a resposta para o problema também é não, afinal você encontrou um vértice que, no grafo original, não alcança $v$.

Se os dois testes forem positivos, a resposta para o problema será sim. Não é difícil provar isto. Se as duas respostas forem positivas, significa que para qualquer vértice $u$, existe um caminho de $u$ até $v$ (caso contrário, o segundo teste falharia). Além disso, para qualquer vértice $w$, existe um caminho de $v$ a $w$ (caso contrário, o primeiro teste falharia). Unindo os dois caminhos, obtemos, para qualquer par de vértices $(u, w)$, um caminho de $u$ a $w$: o caminho de $u$ a $v$ unido ao caminho de $v$ a $w$.

A complexidade desta solução é a complexidade de executar duas buscas em profundidade, que é $O(n + m)$.

Contagem de Dígitos

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

Se você fez o último treino completo, este problema certamente não foi problema (no outro sentido da palavra problema). Ele é bastante similar ao problema Counting Ones. Porém, utilizando base 10 ao invés de base 2. A ideia é a mesma: observar os ciclos completos de cada dígito, e então contar quantos ciclos completos do $i$-ésimo dígito menos significativo acontecem até $X$, contabilizando também o possível ciclo incompleto. Se você ainda não fez isto, resolva o Counting Ones primeiro. O editorial do último treino descreve a solução em detalhes.

Curiosidade: os dois problemas, por mais similares que sejam, são ambos de finais sulamericanas: este de 2010, e o Counting Ones de 2013. Fica como exercício descobrir se existe um ciclo também no uso de problemas deste tipo. Em particular, se você vai disputar a final sulamericana de 2016 ou de 2019, é altamente recomendado saber resolver esses dois problemas.

DNA Alignment

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

O enunciado do problema é bastante denso, então vale a pena certificar-se de que entendeu tudo antes de começar a resolver o problema. Caso contrário, você corre o risco de resolver outro problema, porque não se lembrou de alguma restrição do enunciado.

Vamos lá. O personagem da história tem uma string $s$ e quer contar quantas outras strings de mesmo tamanho $n$ existem que estejam a uma distância máxima, para a definição de distância que ele deu. O tamanho da string já nos faz desconsiderar qualquer coisa que gere todas as strings, mesmo que apenas as que estejam a distância máxima.

Como o problema parece inatacável até então, vamos tentar resolver um problema mais simples e relacionado. Dadas duas strings $s$ e $t$ de tamanho $n$, computar a distância $\rho(s, t)$. O jeito mais simples seria simplesmente traduzir a fórmula do enunciado em código. Mas isto custaria $O(n^3)$. É muito! Vamos, então, tentar algo mais simples.

Vamos considerar quanto cada caractere de $t$ contribui na distância $\rho(s, t)$. Peguemos o primeiro caractere, $t_1$. No somatório de dentro, sobre todos os shifts $j$ de $t$ com $i = 0$ (ou seja, com a string $s$ inalterada), o caractere $t_1$ passa por todas as posições $t_1$, $t_2$, até $t_n$. Em cada uma dessas posições, ele contribui em $1$ para a soma quando encontra um caractere igual (ou seja, quando $s_j = t_1$). Podemos ver que o mesmo acontece com todos os demais caracteres de $t$: cada um contribui exatamente $O(s, t_i)$, onde $O(s, c)$ é o número de ocorrências de $c$ em $s$. Como as strings só contém 4 caracteres distintos no máximo, A, C, T e G, podemos ver que a soma interna quando $i = 0$ é exatamente:

$$O(s, 'A') \cdot O(t, 'A') + O(s, 'C') \cdot O(t, 'C') + O(s, 'T') \cdot O(t, 'T') + O(s, 'G') \cdot O(t, 'G')$$

Não é difícil ver que para qualquer valor de $i$, ou seja, para qualquer rotação da string $s$, ocorre o mesmo. Como testamos todas as rotações de $t$, não faz diferença qual rotação de $s$ consideramos, pois faremos, no total, as mesmas comparações. Assim, a distância entre $s$ e $t$ será $n$ vezes a expressão acima. Como esse fator $n$ estará presente independentemente da string $t$, podemos desconsiderá-lo. Ou seja, podemos então maximizar nossa função simplificada de distância:

$$d(s, t) = O(s, 'A') \cdot O(t, 'A') + O(s, 'C') \cdot O(t, 'C') + O(s, 'T') \cdot O(t, 'T') + O(s, 'G') \cdot O(t, 'G')$$

É um progresso. Agora, resta-nos saber quais strings $t$ maximizam $d(s, t)$, para que possamos contá-las. A expressão de $d(s, t)$ pode não trazer muita inspiração. Vamos tentar interpretá-la de outra forma. Para cada caractere que adicionamos em $t$, o valor de $d(s, t)$ aumentará em $O(s, 'A')$ se este caractere for um 'A', em $O(s, 'C')$ se for um 'C', em $O(s, 'T')$ se for um 'T'e em $O(s, 'G')$ se for um G. Consegue ver então qual maximiza a distância? Sim, o caracter que mais ocorre em $s$ é sempre melhor que os outros. Um argumento simples de troca prova que esta escolha será ótima.

O problema agora é: podem haver mais de um caractere com o maior número de ocorrências. Neste caso, tanto faz: qual deles escolher não afeta o valor de $d(s, t)$. Finalmente, vamos tentar atacar a pergunta do problema: quantas strings $t$ maximizam $d(s, t)$? Vamos dizer que há $k$ caracteres em $s$ que ocorrem o número máximo de vezes (por exemplo, se $n = 9$ e 'A' ocorre $3$ vezes, 'C' ocorre $3$, 'T' ocorre 2 e 'G' ocorre uma vez, $k = 2$, já que os dois caracteres com número máximo de ocorrências são o 'A' e o 'C'). Para cada caractere de $t$, podemos escolher um qualquer desses $k$ caracteres, independentemente. Temos $k$ escolhas para o primeiro caractere, $k$ para o segundo, e assim por diante até o $n$-ésimo. Logo, a resposta será $k^n \mod 10^9 + 7$. Você pode fazer esse cálculo com $O(n)$ multiplicações e divisões, mesmo. Não é necessário usar Exponentiation by squaring, embora já fique recomendado estudar essa técnica, pois será útil em outros problemas.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas