Treino de 14 de agosto de 2015

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

Seguimos com os treinos no novo formato. 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 Feynman
2 Amalgamated Artichokes
3 Face the mate
4 Counting Substhreengs
5 Star

Soluções

Feynman

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 contagem. Vamos separá-lo em casos. Quantos quadrados de lado $l$ cabem num quadrado de lado $n$? Desenhando o quadrado de lado $n$, você verá que existem exatamente $(n - l + 1)^2$ pontos em que o canto superior esquerdo do quadrado pode ser colocado. Por exemplo, em um quadrado de lado 3, um quadrado de lado $2$ tem exatamente $(3 - 2 + 1)^2 = 4$ possibilidades para seu canto superior esquerdo. Você pode simplesmente iterar por todos os valores de $l$ e somar $(n - l + 1)^2$ na resposta para resolver este problema em O(n).

Se o limite para $n$ fosse não $100$ mas $10^9$ (e você tivesse que calcular a soma módulo $10^9 + 7$), você poderia observar que essa soma é equivalente à soma dos quadrados de todos os números naturais entre $1$ e $n$ inclusive (são $n^2$ possibilidades para um quadrado de lado $1$, $(n-1)^2$ para um de lado $2$, ..., 1 possibilidade para um quadrado de lado $n$). Para isto, existe uma fórmula fechada simples para responder às consultas em $O(1)$.

Amalgamated Artichokes

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

Tendo um $k$, é fácil calcular o preço das ações no tempo $k$. Agora, uma queda no preço tem um início $i$ e um final $j$. Vamos fixar o final $j$. Qual é a maior queda que tem como final um determinado $j$? É fácil ver que é a queda do $i$ com maior preço com $i < j$. Ou seja, é a queda correspondente à diferença entre o maior preço que as ações já atingiram antes do dia $j$ e o preço no dia $j$.

Isto nos permite fazer o seguinte: iteramos de $1$ a $n$ mantendo o maior preço $M$ já observado (que começa com $p(1)$). Para cada $i$ entre $1$ e $n$, calculamos a maior queda até o preço atual $M - p(i)$ e atualizamos $M$ caso $p(i) > M$. A maior queda encontrada no processo é a resposta para o problema. Claramente, a complexidade desta solução é $O(n)$.

Face the mate

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

Este problema envolve a seguinte relação. Sejam $u$ e $v$ dois vetores (no caso do problema, em duas dimensões, mas isto não é necessário). Então, se $\theta$ é o menor ângulo entre esses dois vetores, temos que:

$$\cos \theta = \frac{u \cdot v}{||u||\cdot||v||} \enspace .$$

Ou seja, podemos usar a função arco-cosseno (já implementada nas bibliotecas padrão de C, C++, Java e da maioria das outras linguagens) para encontrar o ângulo $\theta$ se tivermos os dois vetores. No caso deste problema, o ângulo que um personagem terá que girar é o ângulo entre dois vetores dados: o vetor entre os pontos para o qual ele está olhando e sua posição, e o vetor entre a posição do outro personagem e a sua posição. Basta, então, calcular o ângulo para os dois personagens e compará-los, imprimindo o nome do personagem com menor ângulo, ou $0$ caso haja empate.

Counting Substhreengs

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

Como já fizemos no primeiro e no segundo problemas, vamos tentar agrupar as possibilidades fixando alguma propriedade delas. Uma substring tem um início $i$ e um final $j$: vamos fixar, novamente, o final $j$. Quantas substhreengs terminam em um determinado $j$ fixo? Bem, se o dígito em $j$ for divisível por $3$, há pelo menos uma: a que começa em $j$ também. Porém, de qualquer forma, também há todas as substrings que terminam em $j-1$, só contém dígitos e cuja soma dos seus dígitos somado ao dígito na posição $j$ for divisível por $3$. Para responder esta consulta, vamos manter em um loop uma informação simples: quantas substrings terminam no último caractere analisado e cuja soma dos dígitos deixa resto $0$ quando divisível por $3$, quantas deixam resto $1$ e quantas deixam resto $2$. Assim, se temos um dígito que deixa resto $0$ na posição $i$, precisamos completá-lo à esquerda com substrings que deixam resto $0$ também. Se o dígito na posição $i$ deixa resto $1$, precisamos completá-lo com substrings que deixam resto $2$, para que a soma seja divisível por $3$. Similarmente, se o dígito atual deixa resto $2$, precisamos completá-lo com substrings que deixem resto $1$.

Vamos dizer que estamos mantendo 3 contadores: $r_0$, $r_1$ e $r_2$, que indicam quantas substrings terminam no último caractere analisado, só contém dígitos e cuja soma dos dígitos deixa cada um dos restos possíveis módulo $3$. Inicialmente, como não analisamos caractere algum, os três iniciam em $0$. Vamos manter também um inteiro com a resposta (note que ele precisa ter $64$ bits, pois a resposta pode ser da ordem de $10^{12}$).

Procedemos da esquerda para a direita, então, fazendo o seguinte:


  • Se o caractere atual não for um dígito, não há substring que termine nele que só contenha dígitos. Então, zeramos os três contadores.
  • Senão, verificamos se o dígito atual deixa resto $0$ módulo $3$ (ou seja, é $0$, $3$, $6$ ou $9$). Se sim, somamos um à resposta, contabilizando a substring que só contém o caractere atual.
  • Se o dígito atual deixar resto $0$ módulo $3$, somamos $r_0$ à resposta (todas as substrings que deixam resto $0$ e terminam no último caractere podem ser estendidas com o caractere atual e continuam a deixar resto $0$). Se deixar resto $1$, somamos $r_2$ à resposta (mesmo raciocínio: as substrings que deixavam resto $2$ podem ser estendidas com o caractere atual e vão passar a deixar resto $0$). Caso contrário, somamos $r_1$ à resposta.
  • Agora, precisamos atualizar os contadores. A lógica seguida será a mesma do último ponto: strings que deixavam resto $r$ vão passar a deixar resto $r'$ quando estendidas com o caractere atual, dependendo de $r$ e $r'$. Por fim, temos que incrementar o contador $r_x$, onde $x$ é o resto do dígito do caractere atual módulo $3$, pois além das substrings que foram estendidas com o caractere atual há também a substring que só é composta pelo caractere atual, e esta deixa resto $x$ módulo 3.

Com isto, calculamos a resposta em $O(n)$.

Star

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

Da teoria dos números, temos que um número $n$ só é capaz de tocar em todos os números entre $1$ e $m$ se, e somente se, $n$ e $m$ forem coprimos. Ou seja, se $\text{gcd}(n,m) = 1$. Euler, com toda a sua sabedoria, já nos mostrou como calcular essas quantidades. Chamamos essa função de Totiente de Euler, e denotamos a mesma por $\phi(n)$. Para computa-la, uma das maneiras mais simples é desmembrar o número em seus diversos fatores primos que, pelo teorema fundamental da aritmética, é uma fatoração única e da forma $n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}$. Em seguida, vamos calcular efetivamente $\phi(n)$ que, como demostrado por Euler, é computada por $\phi(n) = \prod_{i=1}^{k}(p_i - 1) p_i^{(e_i - 1)}$.

Agora, como conseguimos encontrar a fatoração? Se conseguirmos listar, de maneira eficiente, todos os primos que podem ser fatores de $n$, temos nossa solução pronta. Uma das maneiras mais rápidas e conhecidas de fazer isso é por meio do Crivo de Eratóstenes. Uma boa propriedade para se ter em mente é: se nenhum número até $\sqrt{n}$ divide $n$, então $n$ é primo. Isso nos permite reduzir a quantidade de primos necessários em nossa solução para pouco mais de 5000 (número de primos menores que $\sqrt{2^{31}}$), o que confortavelmente cabe em nossa memória e ainda pode ser pré-computado caso necessário.

Por fim, devemos descobrir os primos $p_i$ e suas potências $e_i$. Para isso, testamos cada primo que obtivemos pelo crivo e, se ele for um divisor de $n$, contamos sua base. O custo desse passo é, no pior caso, proporcional à quantidade de primos que conhecemos $P$, já que podemos precisar de testar cada um deles. Com isso, somos capazes de calcular $\phi(n)$ também em $O(P)$ e responder o problema. Nossa solução é, portanto $O(P)$. Isso se pré-computarmos os mesmos (fortemente aconselhado), caso contrário teremos de pagar (uma única vez) o custo de $O(n \log \log n)$ do crivo para usá-lo.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas