OBI 2018 - Fase 2 - Programação Nível 2

Para conferir a prova na íntegra, clique aqui

Para ver todos os materiais incrível produzidos pela equipe NOIC para a OBI, veja a página de informática.

Fuga

Comentário Escrito por Arthur Lobo

Conhecimento prévio necessário:

• Busca em Grafos
• Matriz

Você quer derrubar armários de modo à maximizar a distância do menor caminho do ponto inicial até o final. A primeira vista, o problema pode parecer bem difícil, já que temos muitas opções para derrubar os armários e não é muito claro como podemos reduzi-las.

Primeiro, vamos dar uma olhada no exemplo:

Uma coisa que é possível perceber no exemplo é que, depois da derrubada dos armários, O Conde Olaf não somente escolhe o menor caminho do início até o fim, ele escolhe o único caminho do início até o fim, então ele não tem escolha: tem que seguir o caminho que Violet e Klaus "decidiram" que ele vai seguir.

E a ideia é justamente essa: decidir o caminho que ele vai seguir. Testando alguns casos na mão, é possível ver que podemos obrigar Conde Olaf a seguir qualquer caminho simples (que não repete nenhuma posição) que começa em $(X_e,Y_e)$ e termina em $(X_s,Y_s)$.

Basicamente, para qualquer caminho, existe uma maneira de derrubar os armários de modo que esse seja o único caminho que leva do início até o final. Confira alguns exemplos de caminhos (não necessariamente ótimos) que podem ser montados num grid $7\times 7$:

Sempre podemos ir virando or armários "enquanto" estamos fazendo o caminho. A ideia vai ser bloquear todas as opções de movimento em cada ponto e deixar apenas a desejada. Então agora o problema se reduz para encontrar o maior caminho simples que começa em $(X_e,Y_e)$ e termina em $(X_s,Y_s)$.

Novamente, não é muito claro como, e se, podemos fazer isso de uma maneira simples e dentro do tempo limite: testar todos os caminhos, à primeira vista, parece ser muito lento. Mas na verdade, a quantidade de caminhos não é tão grande assim.

Na prática, ter um grid $11 \times 11$ com os armários, é equivalente a ter um grid $5 \times 5$, porque sempre que estamos numa posição $(i,j)$ com $i$ e $j$ ímpares, vamos dar 2 passos seguidos na mesma direção, terminando em outra posição $(i',j')$ com $i'$ e $j'$ ímpares. Fazendo um código que testa a quantidade de caminhos começando em $(1,1)$ é $153745$.

Podemos testar todos os caminhos simples fazendo uma $dfs$ que desmarca um vértice como visitado toda vez que saímos dele. Será $dfs(i,j,d)$, com $i$ e $j$ sendo a coordenada dos pontos atuais e $d$ a distância percorrida desde o começo.

Nessa $dfs$, nós vamos passar apenas pelos vértices com ambas as coordenadas ímpares, ou seja, vamos dar passos de 2 em 2 em cada direção (isso dá certo, já que o início e o final estão em coordenadas ímpares).

Primeiro chamamos $dfs(X_e,Y_e,1)$ e começamos resposta = 0; dentro de $dfs(i,j,d)$ faremos:

• Marcamos $(i,j)$ como uma posição visitada: $vis[i][j] = 1$.
• Se $i = X_s$ e $j = Y_s$, fazemos $resposta = max(resposta,d)$, pois encontramos um possível caminho, e desmarcamos a posição.
• Caso contrário, vamos chamar as 4 $dfs$ correspondentes as 4 direções, se elas forem válidas, ou seja, se estão dentro do grid e não foram visitadas no caminho atual, já que ele deve ser simples:
  • Se $(i-2,j)$ está dentro do grid e $vis[i-2][j] == 0$, então chamamos $dfs(i-2,j,d+2)$.
  • Se $(i+2,j)$ está dentro do grid e $vis[i+2][j] == 0$, então chamamos $dfs(i+2,j,d+2)$.
  • Se $(i,j-2)$ está dentro do grid e $vis[i][j-2] == 0$, então chamamos $dfs(i,j-2,d+2)$.
  • Se $(i,j+2)$ está dentro do grid e $vis[i][j+2] == 0$, então chamamos $dfs(i,j+2,d+2)$.
• Por fim, marcamos $(i,j)$ como não visitado: $vis[i][j] = 0$.

Clique aqui para conferir o código

Clique aqui para conferir a solução em vídeo feita pelo NepsAcademy

Wifi

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• BIT (ou Segment Tree)
• Compressão de coordenadas

Observações e ideia

A primeira observação do problema é a seguinte: não faz sentido colocar uma antena em um quarto em que há outro quarto dentro. No exemplo abaixo, por exemplo, é fácil ver que é melhor colocar a antena no lugar circulado em vermelho do que o lugar atual da antena, pois ele vai pegar todo o espaço pego atualmente mais o quarto em branco. Sendo assim, todas as antenas a serem colocadas serão colocadas em quartos que não contém outro quarto (vamos chamar esses quartos de "vazios"). Além disso, perceba que todos os quartos vazios precisarão de uma antena, pois o sinal não vai chegar de uma antena de fora. Assim, a resposta é a quantidade de quartos vazios.

Como checar se um quarto é vazio:

Para um quarto ser vazio, não deve ter nenhum retângulo dentro dele. Vamos representar os retângulos como o ponto superior direito deles (ponto do retângulo A dentro do retângulo B <=> A dentro de B).

Para checar se um quarto Q é ou não vazio, vamos contar quantos quartos estão dentro de Q, ou seja, quantos pontos estão dentro de Q. Isso pode ser feito do seguinte modo:

A quantidade de pontos no retângulo circulado em vermelho é a quantidade de pontos em $C-A-B+D$ ($C$, $A$, $B$ e $D$ são os prefixos 2d representados pelos 4 pontos do retângulo, direito-superior, esquerdo-superior, direito-inferior, esquerdo-inferior).

Como calcular quantos pontos estão em um prefixo 2d:

Esse problema é relativamente conhecido. Ordene os pontos em ordem crescente de X. Quando estamos no ponto $P_i$, todos os pontos considerados estão antes de $P_i$ na coordenada X. Assim, todos os pontos já considerados que possuem uma coordenada Y menor que a coordenada Y do ponto $P_i$ fazem parte do prefixo de $P_i$. Inicialize um array $calc$ com INF. Quando estivermos percorrendo o array, primeiramente vamos passar pelos pontos $A$ e $D$, e vamos salvar o valor de $-A+D$ em $calc_i$. Depois disso vamos passar pelos pontos $C$ e $B$ e, se $(C-B)+calc_i = 0$, então achamos um quarto vazio. Sabemos se estamos olhando para A/D ou para C/B baseado em $calc_i$ (se $calc_i = INF$, estamos olhando para A/D, e para C/B c.c.).

Implementação da atualização e query do prefixo 2d:

Vamos manter uma BIT de soma. Quando acabamos de considerar um retângulo cujo ponto superior-direito é o ponto $P$, adicionamos o Y desse ponto ($P_Y$) na BIT. Ou seja, fazemos a operação $upd(P_Y, 1)$. Para saber quantos pontos possuem um Y menor ou igual ao do ponto atual, fazemos a query $soma(P_Y)$ da BIT. Entretanto, as coordenadas dos pontos podem ir até $10^9$. Como só queremos saber quais pontos vêm antes de quais (a ordem relativa) e as coordenadas podem ir até $10^9$, faremos uma compressão de coordenadas. Vamos criar um array $comp$, onde salvamos todas as coordenadas Y. Vamos ordenar esse array e excluir repetidos. Agora, em vez de fazer $upd(P_Y, 1)$ e $soma(P_Y)$, fazemos $upd(pos, 1)$ e $soma(pos)$, onde $pos$ representa a posição de $P_Y$ no array $comp$. $pos$ é achado usando uma busca binária em $comp$.

Complexidade:

Para ordenar os pontos a complexidade é $O(Nlog)$. Além disso, vamos fazer $N$ operações de update na BIT ($O(Nlog)$) e $2 \cdot N$ buscas binárias em um array de tamanho $N$ ($O(Nlog)$). Logo, a complexidade final é $O(Nlog)$.

Clique aqui para conferir o código

Clique aqui para conferir a solução em vídeo feita pelo NepsAcademy

Elevador

Comentário escrito por Vitor Veiga

Conhecimento prévio necessário:

• Ordenação
• Estruturas Condicionais
• Loops

No problema, nos é dado $N$ pesos referentes a caixas que devemos levar do primeiro ao segundo andar utilizando um elevador e queremos saber se é possível levar todas elas. Nesse elevador a diferença máxima entre os pesos dos dois compartimentos deve ser de 8 unidades, e quando um compartimento sobe o outro desce.

Quando é possível levar todos os pesos, a estratégia mais segura para levá-los é a seguinte:

Se temos $4$ pesos $a, b, c, d$, ordenados do menor até o maior, escolhemos levar sempre primeiro o mais pesado para cima, no caso o $d$. Para levá-lo, primeiro subimos o $a$ e descemos nada, depois subimos o $b$ e descemos o $a$, e trocamos o $a$ pelo $c$. Subimos o $c$ e descemos o $b$ e trocamos o $b$ por $d$ para finalmente subir o $d$ e deixá-lo lá. Agora que o mais pesado já está em cima, sobram 3 pesos e é só repetirmos o processo para o peso $c$, seguido do $b$, e depois $a$.

Essa estratégia é ótima, e só não funciona quando a diferença de peso entre dois pesos adjacentes, depois de ordenados, é maior que 8 unidades, pois nunca conseguiríamos subir um utilizando outro com 8 unidades a menos que ele, travando a estratégia.

Portanto, para sabermos se é possível ou não levar todos os pesos para o segundo andar, basta checar se a diferença entre quaisquer pesos adjacentes é maior que 8. Se for, não é possível levar os pesos. É importante lembrar também que o peso mais leve deve ser menor ou igual a 8, pois, caso contrário, o elevador não conseguiria levantá-lo sozinho.

No segundo caso teste, temos:
$25, 2, 6, 15, 40, 35, 35, 20$, que ordenando fica:
$2, 6, 15, 20, 25, 35, 35, 40$, onde temos, entre $15$ e $6$, uma diferença maior que 8, ou seja, não é possível levar todas as caixas.

Clique aqui para conferir o código

Clique aqui para conferir a solução em vídeo feita pelo NepsAcademy