OBI 2021 - Fase 2 Turno A - Programação Nível 2

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Comentário escrito por Thiago Mota, Leonardo Paes e Lúcio Figueiredo

Para conferir a prova na íntegra, clique aqui.

Média e Mediana

Conhecimento prévio necessário:

• Programação Básica: Variáveis

Para que a média seja igual a mediana, basta que a distância do elemento do meio para as pontas seja a mesma, por exemplo: $2$ $5$ $7$, a distância do $5$ para as pontas é a mesma, logo a média e a mediana ficam no mesmo ponto. Podemos demonstrar isso matematicamente:

Para resolver o problema, basta escolher qualquer número de tal forma que a diferença entre o maior e o menor seja igual o do meio. Segue o código:

Passatempo

Conhecimento prévio necessário:

• Set
• Vetores e Matrizes

Esse é um problema de simulação. O enunciado nos garante que sempre haverá um valor possível de ser descoberto. Portanto, o problema se resume em implementar cautelosamente um algoritmo que sempre encontrará pelo menos o valor de uma variável que ainda não havia sido descoberto. Uma maneira de se fazer isso é mantendo um $set<string,int>$ que guardará, para cada variável, o seu valor. Assim, simularemos o seguinte algoritmo até termos encontrado todas as variáveis:

1. Itere por cada linha e coluna da matriz. Se em nenhuma das linhas e colunas há exatamente uma variável de valor desconhecido, termine o algoritmo. Senão, realize a etapa seguinte nesta linha/coluna;
2. Para descobrirmos o valor da variável desconhecida nesta linha/coluna, utilizarmos a seguinte equação: $valor = \frac{(soma_{(linha/coluna)} - soma_{(conhecida)})}{quantidade}$, onde $soma_{(conhecida)}$ representa a soma dos valores de todas as outra variáveis, ou seja, das variáveis conhecidas, e $quantidade$ é a quantidade de vezes que a variável cujo valor ainda é desconhecido aparece na respectiva linha/coluna.
3. Armazene o valor encontrado no set e repita o passo 1.

Como utilizamos um set em cada iteração do algoritmo, a complexidade da solução é $O(N \cdot M \cdot \log_{} N)$. Confira o código a seguir para melhor entendimento:

Sanduíche

Conhecimento prévio necessário:

• Conceitos iniciais de grafos
• Bitmasks

Se interpretarmos cada ingrediente como um vértice de um grafo e cada par de ingredientes que não combinam como uma aresta, o problema se resume a encontrar a quantidade de subconjuntos $S$ de vértices tais que não existem dois vértices $u$ e $v$ tais que $u \in S$, $v \in S$ e $u$ e $v$ são ligados por uma aresta.

Para resolver o problema, vamos iterar por cada bitmask $S$ de vértices, desde $1$ até $2^N - 1$; assim, cada bitmask representa um conjunto de vértices, de modo que um bit aceso na máscara representa um vértice pertencente ao conjunto. Para saber se $S$ é um conjunto válido, resta checarmos se existem dois vértices presentes no conjunto ligados por uma aresta.

Para checar esta condição, vamos precalcular, para cada vértice $u$, a bitmask $bad[u]$. O $v$-ésimo bit $(0 \leq v \leq N-1)$ de $bad[u]$ terá valor $1$ se $u$ e $v$ são ligados por uma aresta; caso contrário, o $v$-ésimo bit terá valor $0$.

Agora, para cada conjunto (ou bitmask) $S$ de vértices, defina a bitmask $aux$ como o or binário das máscaras $bad[]$ de cada vértice presente em $S$. Em outras palavras, se $i_1, i_2, ..., i_k$ são os índices dos bits com valor $1$ em $S$, a máscara $aux$ será igual a $bad[i_1] \ | \ bad[i_2] \ | \ ... \ | \ bad[i_k]$. Ou seja, pela definição de $bad[]$, $aux$ possuirá o $i$-ésimo bit igual a $1$ se e somente se houver algum vértice $j \in S$ tal que $i$ e $j$ são ligados por uma aresta.

Portanto, para checar se $S$ é um conjunto válido, basta checarmos se $aux$ e $S$ possuem bits ligados em comum; se sim, existem dois vértices em $S$ ligados por uma aresta. Caso contrário, $S$ é um conjunto válido. Para checar se $aux$ e $S$ possuem bits ligados em comum, basta checar se $(S \ \& \ aux) \neq 0$.

Como iteramos por todas as $2^n$ possíveis máscaras de bits e calculamos $aux$ em $O(N)$ para cada máscara, a complexidade da solução é $O(2^N \cdot N)$. Confira o código abaixo para melhor entendimento:

Retângulo

Conhecimento prévio necessário:

• Somas de prefixo
• Busca Binária

Para resolver o problema, vamos utilizar a seguinte observação:

Observação: Um quadrilátero $ABCD$ demarcado em um círculo é um retângulo se e somente se as diagonais $AC$ e $BD$ são diâmetros do círculo.

Com esta observação, basta sabermos se existem quatro pontos $A < B < C < D$ no círculo tais que os segmentos $AC$ e $BD$ são diâmetros, ou seja, a soma dos arcos de $A$ a $C$ e a soma dos arcos de $B$ a $D$ ambas valem metade da circunferência do círculo.

Defina $S(i, j)$ como a soma dos arcos entre os pontos $i$ e $j$ $(i < j)$, ou seja, $L_{i+1} + L_{i+2} + ... + L_j$. Além disso, defina $D(i)$ como o ponto $j$ tal que o segmento $ij$ é um diâmetro, ou $-1$ caso não exista. Vamos computar, para cada ponto $i$, o seu valor $D(i)$. Pela definição de diâmetro, teremos que $ij$ é um diâmetro se e somente se $S(i, j)$ vale metade da circunferência, ou seja, $\frac{S(0, n)}{2}$. Portanto, para encontrar o ponto $j$ (se existir), podemos utilizar uma busca binária no intervalo $[i+1, n]$. Para calcularmos os valores $S(i, j)$ de forma eficiente, basta precalcularmos a soma de prefixo do vetor $L$; assim, se $P_x$ é a soma do $x$-ésimo prefixo, conseguimos calcular $S(i, j)$ em $O(1)$, já que $S(i, j) = P_{j} - P_{i-1}$.

Após computarmos os valores $D(i)$, resta apenas checar se existem dois pontos $A$ e $B$ tais que $D(A) \neq -1$ e $D(B) \neq -1$. Se sim, existe um retângulo demarcado no círculo formado por $A, B, D(A)$ e $D(B)$. Senão, não existe retângulo algum.

Já que realizamos uma busca binária para cada um dos $N$ pontos, a complexidade da solução é $O(N \cdot \log_{} N)$. Confira o código abaixo para melhor entendimento:

PS.: Existe uma solução com complexidade $O(N)$, utilizando a técnica de Two Pointers para encontrar os valores $D(i)$. Como exercício, tente implementar esta solução!