Treino de 4 de setembro 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 King's Poker
2 Cellphone Typing
3 Kyoya and Colored Balls
4 Desvio de Rua
5 Interval Product
6 A lei vai a cavalo!

Soluções

King's Poker

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

Este problema não é complicado, mas deve ser implementado com cuidado. Não há muito como fugir de tratar vários casos: um para cada tipo de mão que é dada na entrada.

Cellphone Typing

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

A chave para este problema está em como representar a lista de palavras de forma que calcular o tempo para digitar uma palavra seja eficiente. Uma estrutura que nos possibilita isso é a Trie, ou árvore de prefixos. Com isto, podemos inserir todas as palavras da entrada em uma Trie, e depois para cada nó da Trie podemos calcular o tempo médio para digitar até aquele nó: é o tempo médio para digitar até o nó pai, mais 1 se o nó pai tiver outros filhos além do nó atual (ou o nó pai for a raiz, caso em que sempre deve-se digitar o primeiro caractere, como especificado no problema), ou 0 caso contrário. Depois, basta calcular a média deste valor para os nós em que termina uma palavra. Esta solução é linear no tamanho total das strings da entrada.

Kyoya and Colored Balls

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

Vamos considerar os subproblemas com $k$ cores. Para $k = 1$, o problema é trivial: só há uma forma de posicionar as bolas, já que todas são indistinguíveis. Agora, para $k > 1$, sabemos que a última bola deve ser da cor $k$, pelo enunciado do problema (caso contrário, a última bola de alguma outra cor teria vindo antes da última bola da cor $k$). Logo, não temos opção para esta bola, mas as outras bolas estão livres: podemos inseri-las em qualquer lugar na sequência. Se a sequência tem $B_{k-1}$ bolas (ou seja, a soma do número de bolas das $k - 1$ primeiras cores é $b$), temos que contar o número de formas de inserir as demais bolas da cor $k$. A sequência final terá um número de bolas igual à soma do número de bolas com cores até $k$. Seja $B_k$ esse número. Uma bola está fixa: a última. Vamos dizer que há $C_i$ bolas da cor $i$. Temos então que escolher $C_i - 1$ posições dentre as $B_k - 1$ que estão livres para as bolas restantes da cor $k$ (e fazemos isso de $\binom{C_i - 1}{B_k - 1}$ formas distintas), e as demais posições serão preenchidas com as bolas das outras cores. Porém, já calculamos o número de sequências distintas com as bolas de cores até $k-1$: basta multiplicar os dois valores para obter o número de sequências distintas com $k$ bolas. Iteramos então de $k = 1$ até o número de bolas na entrada para obter a solução do problema.

Como o número total de bolas não excede $1000$, e portanto $B_k \leq 1000 \forall k$, podemos pré-computar uma matriz com os valores de $\binom{a}{b}$ para $a, b \leq 1000$ e utilizá-la na solução.

Desvio de Rua

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

Podemos verificar cada um dos casos da resposta da seguinte forma:

  • "-" (nenhuma alteração necessária): Esta é a resposta se o grafo for fortemente conexo. Isto pode ser verificado com um número constante de buscas no grafo, em tempo linear.
  • "*" (impossível): Esta é a resposta se, desconsiderando a direção das arestas, o grafo for desconexo.
  • "1" (possível alterando apenas a direção das ruas): Este é o caso mais difícil. Queremos saber se existe uma Orientação Forte para o grafo, ou seja, se há alguma forma de atribuir direções para as arestas de forma que o grafo resultante seja fortemente conexo. É possível provar que este é o caso se e somente se o grafo não tem pontes, que são arestas que, quando removidas, fazem com que o grafo fique desconexo (desconsiderando a direção das arestas). É possível encontrar todas as pontes em um grafo com uma busca em profundidade, em tempo linear. A Wikipedia explica o algoritmo do Tarjan que faz isto.
  • "2" (possível tornando algumas ruas como mão dupla): Bom, como não há qualquer restrição no número de ruas que podem ser convertidas para mão dupla, podemos simplesmente converter todas. Como já verificamos que é possível, este será o caso sempre que não cairmos nos casos anteriores.

Os três testes necessários (para os três primeiros casos) podem ser realizados em tempo $O(n + m)$.

Interval Product

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

Para este problema, precisamos apenas de uma estrutura de dados que seja capaz de lidar com operações em intervalos. Uma árvore de segmentos ou uma BIT são suficientes.

Uma observação que deve ser feita é que o valor absoluto dos números em si não é importante. Com isto, é melhor substituí-los por $-1$, $0$ ou $1$ para evitar overflow. Assim, todos os produtos serão também um desses valores.

Com uma árvore de segmentos, você pode guardar o produto diretamente em cada nó. Com uma BIT, uma possibilidade é guardar a contagem de elementos $0$ e $-1$ separadamente. Dado um intervalo, se há algum $0$ nele, o produto será $0$. Caso contrário, dependerá da paridade do número de $-1$s: se for par, será positivo, caso contrário será negativo.

Com isto, a complexidade da solução será $O(K \lg N)$.

A lei vai a cavalo!

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 fluxo máximo. Basta montar um grafo bipartido com um nó para cada cavalo e um para cada policial. Criamos então um nó artificial "source", que é ligado em cada policial com capacidade $1$ (pois cada policial só pode montar um cavalo) e um nó "sink" com uma aresta de cada cavalo para ele com capacidade igual ao número de policiais que o cavalo suporta. Por fim, adicionamos arestas entre cada par de policiais e cavalos que têm afinidade. A resposta será o fluxo máximo do nó "source" até o nó "sink".
Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas