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:
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:
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:
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