Treino de 20 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 K.Bro Sorting
2 Kids' Wishes
3 Bridging Signals
4 Skyscrapers
5 Go up the ultras

Soluções

K.Bro Sorting

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

Se há um elemento que aparece antes de um elemento menor que ele, necessariamente esse elemento deverá ser escolhido em alguma rodada, pois caso contrário essa inversão não será desfeita. Porém, note que sempre é possível ordenar a sequência escolhendo cada um desses elementos apenas uma vez - basta escolhê-los em ordem decreescente. Logo, basta contar quantos elementos com essa propriedade existem.

Isto pode ser feito em $O(n)$. Basta olhar os elementos da direita para a esquerda e salvar o menor elemento já encontrado. Quando processarmos o elemento $i$, basta compará-lo com o menor elemento já encontrado para saber se há algum elemento menor que ele que aparece depois no vetor, e então atualizar o menor elemento.

Kids' Wishes

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

Embora o número de crianças seja grande, o número de crianças com desejos é pequeno (da ordem de $10^5$). Basta, então, montar um grafo apenas com essas crianças que possuem desejos, e verificar se ele se enquadra em uma das duas possibilidades a seguir:

1- Ele é um ciclo de tamanho $n$. 2- Ele é um conjunto de caminhos

Caso ele contenha ciclos de tamanho menor que $n$, obviamente as restrições não poderão ser satisfeitas. No caso em que ele não seja um conjunto de caminhos e nem tem ciclos, deve ser uma árvore onde pelo menos um vértice tem grau $\geq 3$ - neste caso, essa criança também ficará insatisfeita. Assim, basta testar essas duas possibilidades.

Isto pode ser feito com uma DFS.

Bridging Signals

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

Considere que cada elemento do lado direito é substituído pelo índice do fio correspondente no lado esquerdo. Observe que uma solução válida corresponde sempre a uma escolha de elementos do lado direito cujos valores nesse vetor estão ordenados (se houver uma inversão, são dois fios que se cruzariam). Logo, a solução ótima é a maior subsequência crescente deste vetor, o que pode ser encontrado em $O(n \lg n)$ (https://en.wikipedia.org/wiki/Longest_increasing_subsequence).

Skyscrapers

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

Temos um problema bilateral: temos a contagem de prédios vistos da esquerda e da direita e desejamos saber de quantas maneiras podemos arranjar os prédios para que essas contagens sejam mantidas.

Podemos transformar o problema em um problema unilateral: após fixarmos a posição do prédio mais alto, sobram-nos dois problemas unilaterais: de quantas maneiras é possível arranjar $k$ prédios em sequência sendo que, olhando-se de um lado fixo, enxergamos $k' \leq k$ prédios. Note que esses subproblemas se mantém unilaterais, pois como o prédio mais alto já foi colocado, do outro lado todos os prédios com os quais estamos trabalhando serão invisíveis; então, só precisamos nos preocupar com um dos lados. Note que eles também são simétricos: o número de formas de arranjar $k$ prédios do lado esquerdo será o mesmo número de formas de se arranjar $k$ prédios do lado direito.

Podemos tentar definir então uma função $f(n, k)$ que corresponde ao número de formas distintas de se arranjar $n$ prédios em uma linha de forma que, olhando da esquerda, são vistos $k$ prédios.

O que nos permite armazenar apenas o número de prédios, e não quais prédios, é que todos os tamanhos são distintos. Assim, não importa quais prédios estão em questão: o maior deles sempre será visível; seguido do segundo maior que está na frente dele, e assim por diante. O número de formas de se arranjar $n$ prédios de tamanhos distintos equivale ao número e formas de se arranjar os prédios de tamanhos $1, \cdots, n$.

Voltemos a $f(n, k)$. Como os prédios têm tamanhos distintos, sabemos que um é mais alto que todos os outros. Consideremos o prédio mais à direita. Ele só será visível se for o mais alto de todos (caso contrário, o mais alto será colocado em alguma posição posterior e ele se tornará invisível). Ou seja, temos duas opções: ou colocar o prédio mais alto na posição mais à direita, ou colocar outro prédio que não o mais alto. Em todo caso, sobram $n-1$ prédios para serem colocados nas $n-1$ posições da esquerda; se colocarmos o mais alto, vamos precisar que outros $k-1$ sejam visíveis, caso contrário o prédio colocado será invisível e ainda precisaremos de $k$ outros visíveis, mas temos $n-1$ formas de escolher um prédio que não seja o mais alto. Ou seja:

$$f(n, k) = (n-1)f(n-1, k) + f(n-1, k-1)$$

O caso base é $n = 0$: $f(0, 0) = 1$ e $f(0, k) = 0$ para $k \neq 0$.

Falta-nos apenas voltar ao problema bilateral. O maior prédio pode estar em qualquer uma das posições, e cada uma nos gera dois problemas unilaterais. Resta-nos apenas escolher quais prédios vão para a esquerda e quais vão para a direita. Se colocamos o maior prédio na posição $1 \leq i \leq n$, então precisamos escolher, dos $n-1$ prédios restantes, $i-1$ para irem para a esquerda e $n - i$ para irem para a direita. Note que escolhendo os de um lado, os do outro já estão automaticamente escolhidos - são os que restaram.

Assim, se as entradas do problema são $n$, $left$ e $right$, a resposta é:

$$\sum_{i=1}^n {{n-1}\choose{i-1}} f(i-1, left - 1) f(n-i, right-1)$$

Subtraímos 1 de $left$ e de $right$ porque um prédio já está visível: o maior de todos, que já foi colocado. A complexidade desta solução é $O(n^2)$.

Observe que você pode pré-computar os valores de ${{n}\choose{k}}$ e de $f(n, k)$ e reutilizá-los em todos os casos de teste. Assim, você consegue responder cada caso em $O(n)$.

Go up the Ultras!

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

Pela definição, um ultra é um pico de altura $h$ onde o caminho desse pico até qualquer outro pico mais alto passa por um ponto de altura no máximo $h - 150000$, ou é o pico mais alto de todos e possui altura $h \geq 150000$.

A parte que nos dificulta a solução é a de considerar o caminho até "qualquer outro pico mais alto", porque podem haver vários. Podemos notar, contudo, que essa é uma complicação desnecessária. Basta que consideremos o caminho até o primeiro pico mais alto alcançado indo para a esquerda e para a direita. A razão para isto é simples. Suponha que o caminho de um pico $i$ até um dos dois picos mais altos mais próximos (para a esquerda e para a direita) não passe por um ponto de altura até $h - 150000$. Então $i$ não pode ser um ultra. Caso contrário, $i$ necessariamente é um ultra, já que qualquer caminho até outro pico mais alto começa com um desses dois caminhos, que já sabemos que contém um ponto de altura até $h - 150000$: logo, $i$ é um ultra.

Se soubermos, para cada pico $i$, o próximo pico mais alto e o pico anterior mais alto, podemos resolver o problema usando uma estrutura de RMQ (uma Segment Tree, por exemplo), fazendo o seguinte: para cada pico, verificamos se a menor altura de um ponto no caminho até o ponto anterior é no máximo $h - 150000$. Fazemos o mesmo para o próximo pico mais alto. Se ambos os testes passarem, então o pico é um ultra; caso contrário, não. Isto resolveria o problema em $O(n \lg n)$.

Para termos a solução completa, precisamos então do pico anterior mais alto e o próximo pico mais alto para cada pico. Há várias formas de se calcular isto - podemos, inclusive, usar uma árvore de segmentos novamente. Mas vamos mostrar uma solução linear.

Suponha que queiramos o pico anterior mais alto de cada pico (o caso do próximo pico é idêntico, podemos apenas inverter o vetor e fazer o mesmo). Vamos manter uma pilha que contém candidatos a serem o primeiro pico mais alto à esquerda do pico atual. Inicialmente, a pilha está vazia e vamos iterar de $0$ a $n-1$.

Dentro do loop, fazemos o seguinte:

  • Se o ponto atual não for um pico, ignore-o. Senão, continue.
  • Enquanto a pilha não estiver vazia e o pico atual for maior ou igual ao pico no topo da pilha, remova o topo da pilha.
  • Se a pilha estiver vazia depois desse loop com remoções, então o pico atual é o pico mais alto desde o primeiro pico (i.e. não há picos mais altos à esquerda).
  • Caso contrário, o primeiro pico mais alto à esquerda é o pico no topo da pilha.
  • Adicione o pico atual no topo da pilha.

Sempre que removemos um pico da pilha, sabemos que ele não será o pico à esquerda mais alto mais próximo de nenhum pico que ainda será processado, porque o pico atual é pelo menos tão alto quanto ele, e está mais próximo dos próximos picos. O pico removido também não pode ser o pico mais alto e mais próximo à esquerda do pico atual porque não é mais alto que ele (é a condição para que ele seja removido). Logo, ele não é um candidato nem para o pico atual e nem para os próximos picos. O loop de remoção para quando ou a pilha está vazia (e sabemos que apenas candidatos que podiam ser removidos foram removidos) ou encontramos um pico mais alto que o atual - neste caso, sabemos que ele é o mais próximo que é mais alto pela ordem de entrada na pilha (o topo é o elemento adicionado mais recentemente).

A complexidade desse procedimento é linear no número de pontos porque cada ponto é adicionado e removido no máximo uma vez - logo, no total, haverá $O(n)$ inserções e $O(n)$ remoções na pilha no pior caso.

O mesmo pode ser feito para encontrar o primeiro pico à direita que é mais alto que cada pico.

Combinando esta solução com o RMQ, a complexidade total da solução é $O(n \lg n)$.

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas