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!