OBOI 2023 - Fase 1 - Nível Sênior

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.

Para conferir a prova na íntegra, clique aqui

Baixinhos vs Lúcio

Comentário escrito por Caique Paiva

Conhecimento Prévios Necessários:

Ordenação

Vamos resolver a primeira subtask. Se $A \le B \le C$ , então, basta ver se $A+B \ge C$ . Com isso, se ordenamos $A, B, C$ , é só fazermos a solução da subtask. Portanto, vamos colocar $A, B, C$ no vetor $v[3]$ , e ordenar ele com a função sort, e então, basta ver se $v[0] + v[1] > v[2]$ , se for verdade, imprimimos "S", se não, imprimimos "N".

Clique aqui para ver o código

Martelo do Veigola

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

Digamlos que, depois de realizar as trocas, terminamos tendo $D'$ diamantes e $G'$ gravetos, então a quantidade de martelos que podem ser feitos seria $min(\floor D'/6 \rfloor,G')$ , portanto, é isso que queremos maximizar.

A ideia vai ser passar por todos os pares $D',G'$ possíveis de serem alcançados. Já que ambos $D$ e $G$ são menores ou iguais a $100$ e é fácil ver que serão feitas somente trocas de um dos dois tipos, podemos testar todas as quantidades de trocas de cada tipo.

Se realizamos $x$ trocas gravetos $\rightarrow$ diamante, então $G' = G-4*x$ e $D' = D+x$ . Perceba que se algum dos dois virarem negativos, então $min(\lfloor D'/6 \rfloor,G')$ , portanto não precisamos nos preocupar com números negativos.

Fazer $x$ trocas diamante $\rightarrow$ gravetos é a mesma coisa de fazer $-x$ trocas gravetos $\rightarrow$ diamante, então basta chegarmos o maior valor de $min(\lfloor D'/6 \rfloor,G')$ ao realizarmos $x$ trocas, para todo $-100 \le x \le 100$ , o que pode ser feito com um for.

Clique aqui para conferir o código

Fliperama do Rafaik

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

Two pointers

A ideia vai ser ir realizando as operações de "fora para dentro", simulando o que seria feito no jogo. É fácil ver que nunca vale a pena fazer $L$ ficar maior que $R$ , porém pode ser que eles se tornem iguais em algum momento. Além disso, podemos simplificar o enunciado um pouco: ao invés de ir somando no array $B$ até ele ficar igual à $A$ , vamos subtraindo no array $A$ até ele ser inteiramente $0$ .

Enquanto o intervalo $(L,R)$ for maior que $2$, ou seja, enquanto $L+1 < R$ , vamos fazer o seguinte algoritmo:

Se o valor em $L$ for igual a $0$ , então movemos $L$ para direita, realizando uma operação do tipo 1.
Se o valor em $R$ for igual a $0$ , então movemos $R$ para esquerda, realizando uma operação do tipo 2.
Se ambos os valores em $L$ e $R$ são diferentes de $0$ , então realizamos a operação do tipo $3$ nessas posições enquanto o menor deles não se tornar $0$ . Mas já que os valores podem ser muito grandes, não podemos realizar essas operações. No total, vamos fazer $OP = min(A_L,A_R)$ operações, então podemos fazer todas elas de uma vez, aumentando o número de operações em $OP$ , fazer $A_L-= OP$ e $A_R-= OP$ .

No final disso tudo, vamos ter apenas $2$ elementos possivelmente diferentes de $0$ , que são $L$ e $R$ (que agora é a mesma coisa que $L+1$ ) e podemos realizar a operação 3 até que pelo menos um deles seja igual a $0$ (assim como fizemos no algoritmo).

Agora temos 3 casos:

Ambos são $0 \rightarrow$ acabou.
$A_L = 0$ e $A_R \neq 0 \rightarrow$ movemos $L$ para a direita, realizando uma operação do tipo 1.
$A_R = 0$ e $A_L \neq 0 \rightarrow$ movemos $R$ para a esquerda, realizando uma operação do tipo 2.

No caso em que não acabou ainda, temos que verificar se o valor restando é par ou ímpar. Se ele for ímpar, então é impossível e a resposta é $-1$ . Se ele for par, então realizamos $A_L/2$ operações do tipo 3 e finalmente ganhamos. No total, a complexidade fica $O(N)$ .

Clique aqui para conferir o código

Tesouro de TurTur

Comentário escrito por Rafael Nascimento

Conhecimento prévio necessário

Parcial 1:

Perceba que nessa parcial nos podemos acessar todos os corredores, já que todos eles necessitam da chave que está presente na sala $1$ e pode ser pego logo no início. Assim, este é um problema clássico de Dijkstra, de achar o caminho mínimo entre a sala $1$ e a sala $N$ .

Parcial 2:

A partir daqui nos precisamos de vertices auxiliares.

Perceba que temos duas variáveis importantes:

A sala que estamos localizados.

O cartão que estamos carregando.

Ou seja, podemos representar os estados como d[posicao][cartao].

Depois nós podemos iterar por todos os estados da posição atual e andar nos corredores no qual nós temos acesso.

Dessa forma, nos podemos utilizar vetores auxiliares e armazenar os locais ( $2\cdot{10}^{5}$ ) e os cartões ( $100$ ), tendo no total ( $2\cdot{10}^{7}$ ) estados, sendo suficiente para conseguir acessar todas as salas. Para cada estado nos temos que computar a possibilidade de pegar o cartao no chão e iterar todas as conexões da sala, sendo assim $O(K(N+Mlog M))$ .

Parcial 3:

Essa parcial consiste em uma otimização da parcial 2.

Primeiro, deve-se observar que muitos dos estados da Parcial 2 serão inutilizados, ou seja, não é possivel alcançar a sala y com o cartao x.

Para cada sala x, nós queremos saber com quantos cartões possíveis podemos estar naquela sala. Perceba que se estivermos segurando um cartao x, nós pegamos o cartão x naquela sala ou viemos de outra sala com um corredor que requer o cartão x.

Dessa forma, em cada sala nós temos no máximo (número de corredores conectando a sala) + 1 possibilidades de cartões válidos.

Dessa forma, perceba que o numero de estados validos será no máximo $2*M+N$ .

Porém, perceba que o número de iterações para cada, ou seja, o número de conexões que iteramos em cada nó, sera (grau)*(grau +1), que é insuficiente para casos como a estrela.

Como podemos otimizar a iteração de cada nó?

Digamos que ao inves de checar todas as conexões, nós checamos apenas as conexões do cartão que temos. Dessa forma, podemos garantir que cada conexão será checada uma única vez, ou seja, apenas quando estamos segurando o seu cartão.

Na implementação,pode-se utilizar um map para armazenar tanto os estados já visitados como as conexões.

Dessa forma, a complexidade final é $O(NlogN + MlogM)$ , com os logs variando de código para código.

Clique aqui para conferir o código