Treino de 27 de novembro 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 Vitaly and Strings
2 Tanya and Postcard
3 Cleaning Robot
4 Jupiter Attacks!
5 Attacking Rooks

Soluções

Vitaly and Strings

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

Só é preciso calcular a próxima string (lexicograficamente) a $s$ e compará-la com $t$. Se essa string for maior ou igual a $t$ lexicograficamente, não existe solução.

Para encontrar a próxima string, você pode fazer como faria para incrementar um inteiro: incrementa o último caractere; se ele era 'z', passa a ser 'a' e você incrementa o penúltimo; se este é 'z', repita.

Vitaly and Strings

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

Neste problema, se há um caractere de $t$ que pode ser usado para casar com um caractere de $s$, não há sentido em não usá-lo: ele só poderá ser usado em um outro caractere igual de $s$, mas isto não melhorará a resposta. Assim, basta proceder de maneira gulosa. Pelo tamanho das strings, uma forma de implementar isto no tempo é a seguinte: primeiro, conte quantos caracteres de cada tipo existem em $t$. Depois, passe por $s$ e, para cada caractere, veja se a contagem de $t$ é maior que zero. Se sim, decremente a contagem do caractere correspondente e incremente o número de "YAY!"s. No final, o número de "WHOOPS!"s será $n$ menos o número de "YAY!"s.

Cleaning Robots

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

Este problema é muito similar ao problema do Caixeiro Viajante. Porém, como há no máximo 10 "*" na entrada e o grid é pequeno, você pode implementar um algoritmo de força bruta. Para cada par de '*'s (e a posição original do robô), calcule com uma BFS o menor caminho no grid entre esses dois tiles. Com isto, para cada permutação dos '*'s, você consegue calcular em $O(n)$ o custo de coletar o lixo nessa ordem. Basta testar todas as permutações. Em C++, você pode usar a função 'std::next_permutation' para isto.

Complexidade: $O(n \times n!)$.

Jupiter Attacks!

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

Neste problema, precisamos trabalhar com intervalos. A questão que dificulta a simples aplicação de uma Segment Tree é que os coeficientes de cada elemento mudam de acordo com o intervalo procurado.

Porém, vamos dizer que fixamos que o elemento $k$ da direita para a esquerda (porque há uma inversão no somatório do enunciado) será multiplicado por $B^k$. Com isto, e com uma Segment Tree, conseguimos facilmente calcular agora, dados $i$ e $j$, a soma de todos os elementos entre $i$ e $j$, que é:

$$S_{ij} = \sum_{k=j}^i B^k \times f_k \enspace .$$

Estamos próximos da resposta. Falta apenas notar que, para obter o que o problema pede, só precisamos dividir $S_{ij}$ por $B^{n-1-j}$. Com isto, o último elemento será multiplicado por $\frac{B^{n-1-j}}{B^{n-1-j}} = 1$, o penúltimo por $B$, e assim por diante, exatamente como pede o problema.

Note que, para dividirmos, como estamos trabalhando módulo $P$, é necessário calcular o inverso multiplicativo de $B^{n-1-j}$ módulo $P$ e multiplicá-lo por $S_{ij}$.

Assim, com uma Segment Tree e o Algoritmo Euclidiano Extendido para calcular o inverso, obtemos uma solução $O(n \lg n)$.

Attacking Rooks

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

Este problema pode ser reduzido a Matching Máximo. Você pode entender a ideia com este tutorial do TopCoder que fala de um problema similar (Rook Attack).

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas