Treino de 7 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 Lineland Mail
2 Berland National Library
3 Interligando a Sildávia
4 One-Dimensional Battle Ships
5 Teletransporte

Soluções

Lineland Mail

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

Como as casas estão em posições ordenadas, você pode perceber que só há no máximo duas opções para a casa mais próxima: a próxima casa e a anterior. Também só há no máximo duas opções para a casa mais distante: a primeira e a última. Assim, basta testar essas.

Você só precisa prestar atenção nos casos em que não há dois vizinhos ou duas opções para a primeira e para a última casas. Isto só acontece quando a casa ou é a primeira ou a última. Você pode testar separadamente esses dois casos.

Berland National Library

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

Este problema admite várias soluções. Uma delas é simples e baseada em simulação. Mantenha uma estrutura de dados (pode ser um set em C++ ou HashSet em Java, por exemplo) com quais pessoas estão na biblioteca. Primeiro, passe uma vez pela entrada atualizando a estrutura quando alguém entra e sai. Porém, guarde também uma lista com as pessoas que saíram sem entrar (sua estrutura de dados te dirá quando isso acontece). Ao final, você terá a lista de pessoas que estavam na biblioteca antes de os logs começarem a ser coletados. Agora, é só repetir o processo, porém inicializando sua estrutura que diz quem está na biblioteca com essas pessoas. Sempre que uma nova pessoa entrar, compare o número de pessoas na biblioteca com o número máximo de pessoas lá já observado (que pode ser antes de os logs serem coletados: cuidado!) e ao final imprima o maior número observado durante essa segunda etapa.

Como você passa somente duas vezes pela entrada, a complexidade dessa solução será $O(n \lg n)$ se você usar um set em C++, cujas operações têm custo $O(\lg n)$. É possível fazer em tempo linear, mas isto realmente não é necessário neste problema porque $n$ é bem pequeno. Até mesmo uma solução quadrática é suficiente (por exemplo, se você usar um vetor simples ao invés de um set).

Interligando a Sildávia

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

A observação crucial para este problema é a seguinte: se é possível interligar as cidades com uma distância $d$, então necessariamente é possível interligá-las com qualquer valor de distância máxima $d' > d$. Da mesma forma, se não é possível interligar as cidades com uma distância máxima $d$, também obviamente diminuir a distância máxima não fará com que as cidades possam ser interligadas.

Já vimos esta propriedade em outros problemas antes: é a monotonicidade. Basicamente, a função $f(d)$ que é $1$ se $d$ é um valor para a distância máxima que interliga as cidades ou $0$ se não é monotônica não-decrescente. Isto nos permite aplicar busca binária para achar o menor valor de $d$ para o qual $f(d) = 1$.

Tendo um valor de $d$ fixo, resta o teste: se as cidades com distância até $d$ forem interligadas, todas as cidades estarão interligadas direta ou indiretamente? Para resolver isto, basta montarmos um grafo não-direcionado com um vértice para cada cidade e uma aresta entre as cidades $u$ e $v$ se $D(u, v) \leq d$. Se este grafo for conexo, o que pode ser testado com uma busca em largura ou profundidade, então $f(d) = 1$. Caso contrário, $f(d) = 0$.

No pior caso, esta busca terá complexidade $O(N^2)$, já que para valores suficientemente grandes de $d$ o grafo será completo. Ou seja, a complexidade da nossa solução será $O(N^2 \lg d_{max})$, onde $d_{max}$ é a maior distância entre um par de cidades (para a qual obviamente $f(d_{max}) = 1$, já que assim todas as cidades estarão diretamente conectadas.

One-Dimensional Battle Ships

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

Primeiramente, vamos supor que tenhamos uma sequência contígua com $l$ células livres. Quantos navios de comprimento $a$ cabem nessas células? Como dois navios não podem se tocar, se tivermos $k$ navios, vamos usar $ka + k-1$ células ($ka$ células para os navios em si, mais $k-1$ células vazias entre eles). Ou seja, se para $k$ navios precisamos de $k(a - 1)$ células, em $l$ células livres podemos colocar no máximo $\lfloor\frac{l}{k(a - 1)}\rfloor$ navios.

Inicialmente, temos uma única sequência contígua com $n$ células livres. Ok, agora vamos pensar no efeito de um tiro no estado do problema. Se um tiro for em uma das extremidades do intervalo, o tamanho do intervalo irá diminuir de 1 (porque uma das células da extremidade foi removida). Caso contrário, o intervalo será particionado em 2: um com as células à esquerda do tiro e um com as células à direita.

Resta agora responder a pergunta: dado um conjunto de intervalos de células livres, qual intervalo contém a célula $X$ (digamos, aonde aconteceu um tiro)? Note que esses intervalos sempre serão disjuntos. Com isto, podemos usar uma estrutura ordenada (como um set em C++) para armazená-los, e nossa pergunta se resume a: qual é o último intervalo cujo limite esquerdo é menor ou igual a $X$? Esta pergunta também pode ser respondida se soubermos encontrar qual é o primeiro intervalo com início estritamente maior que $X$ (o intervalo que contém $X$ será o imediatamente anterior). Em um set em C++, o método upper_bound() nos ajudará.

Assim, podemos executar a simulação dos tiros, mantendo o conjunto de intervalos de células livres e o número de navios que cabem em todos eles. Para processarmos um tiro, removemos do conjunto o intervalo que contém o tiro e inserimos os intervalos que restarem com as células à esquerda e à direita do tiro (note que pode acontecer de nenhum desses intervalos ser gerado, já que o tiro pode atingir um intervalo de tamanho $1$, que será completamente extinto). Com isto, atualizamos também o número de navios que ainda é possível ter em todas as células: basta subtrair da nossa contagem o número de navios que cabiam no intervalo que foi removido e somar o número de navios que cabem nos intervalos inseridos, se houver. No momento em que esta contagem ficar abaixo de $k$, sabemos que Alice está mentindo, porque nas células que restam após o tiro atual não cabem $k$ navios.

Se isto não ocorrer, é possível que Alice esteja sempre falando a verdade, e a resposta será $-1$. A complexidade desta solução é $O(m \lg n)$, já que para cada operação realizamos um número constante de operações em um set com custo $O(\lg n)$ cada.

Teletransporte

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
Apenas faça o que o problema pede: primeiro, calcule a soma das notas de todos os alunos; depois, calcule a média dividindo a soma obtida pelo número de alunos. Por fim, veja quantos alunos tiraram nota acima da média e imprima este número dividido pelo número de alunos, com a formatação correta.

O número de formas de se chegar até a nave $x$ com $l$ botões, tendo começado na nave $S$, é igual à soma do número de formas de se chegar às outras naves com $l-1$ botões multiplicados pelo número de formas de ir dessas naves até a nave $x$ com um botão. Mais formalmente, seja $M_{ij}$ o número de botões da nave $i$ que levam até a nave $j$. Então, se $f(x, l)$ é o número de formas de se chegar à nave $x$ tendo apertado $l$ botões partindo da nave $S$, temos que:


$$f(x, l) = \sum_{i=1}^n M_{ix}f(i, l-1)$$

Os casos base são quando $l = 0$, em que $f(x, l)$ é $1$ se $x = S$ e $0$ caso contrário.

Isto é uma recorrência linear. Ou seja, podemos usar exponenciação de matrizes para resolvê-la. A complexidade desta solução, então, será $O(n^3 \lg L)$.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas